Saturday, 1 July 2017

Games and Tournaments



Games & Tournament type of questions often feature in CAT and could be of innumerable patterns. Below are some of the common ones which have been discussed with the help of an example. (As a reader feel free to request for any other type that you may want to understand, by mentioning it in the comment box below this post)

Round Robin League

Whenever ‘n’ number of teams play once against each other and the top ‘x’ proceed to the next round often the following questions are asked –

i) What is the total number of matches played in the round?
Ans. nC2

ii) What is the minimum number of points that a team should win in order to qualify for the next round (given that win = 2 pts; loss = 0 pts; tie/draw = 1 pt split between both sides)?

Ans. Let (x-1) team win maximum number of matches possible and after deducting their points distribute the balance between the rest of the teams, equally. As 1 team from the rest have to qualify for the next round this process shall give us one team with minimum points qualifying for the next round. (#1 first round)

iii) What is the maximum points with which a team doesn’t qualify for the next round?

Ans. As any team qualifying for the next round cannot get lesser points than a team failing to qualify, the maximum we can give to a team not proceeding to the next round is equal to the teams going to the next round. Here, attempt would be to give maximum points possible to (x+1) teams equally. As only x teams shall move ahead to the next round, the team which got equal points as top x teams shall have maximum points without being able to qualify for the next round. (#1 first round)

Knock-Out Tournament

When ‘n’ number of teams play a tournament (‘n’ being an even number) with every team playing a match each, such that top ranked team plays against the least ranked side and second ranked team play against the second least ranked side and so on – the number of matches in that round shall be n/2 and the sum of ranks of any two teams playing each other shall be (n+1). (#1 second round)

Coin Picking Game

When 2 players finish picking ‘n’ number of coins turn by turn by picking minimum ‘x’ and maximum ‘y’ coins in their respective turns then they choose a target number of coins to be left at end for the opponent and maintain gap of (x+y) coins. (#1 final round)


#1. 32 top players of the world participate in a multi-games tournament which would test their intelligence, fitness and physical strength. The participants are divided equally into 2 groups – A & B wherein everyone play once against each player in their respective group. The winner of every game is awarded 2 points while the loser gets 0 points. In case of a draw, both players get 1 point each. At the end of all matches in both the groups, only the top 8 players from each group proceed to the next round. In case, 2 or more players end up with same number of points they are given priority based on their ranking given to them prior to the tournament such that when two players have scored equal points the player with a better ranking gets a higher position in the points table.

A fresh ranking is given to all players reaching the second round from 1-16 based on the points scored by them and their previous rankings (this ranking shall be valid from second round, till the end of the tournament). In the second round every player competes against exactly one player in an arm wrestling duel wherein the player ranked 1st (as per fresh ranking after round 1) plays against 16th rank in the first game, 2nd against 15th in the second game and so on till 8th plays against 9th rank. Only the winners proceed to the third round. Whenever a player wins against another player ranked above it, then the lower ranked player is said to have caused an upset.

In the third round, winners of 1st, 3rd, 5th and 7th games of second round team up against another team of winners of the rest of the games in the second round for a tug of war contest. Only players of the winning side proceed to the next round.

In the fourth round all 4 players participate in a swimming contest and the top 2 qualify for the final round.

In the final round 50 marbles are left on a table and both players pick some marbles turn by turn with a minimum of 1 and maximum of 5 marbles in each turn. The person who picks the last marble wins the tournament. The first turn to pick the marbles would be decided by a toss, wherein the winner of the toss may choose to take the first turn or ask the opponent to pick first.

i) What is the minimum points with which a player can qualify the second round?

Sol. Total points from all matches in a group = 16C2 x 2 = 240
Maximum points that can be scored by a player are 15 x 2 = 30.
Similarly maximum points that can be scored by top 7 players in a group are –


15 wins
30 points
14 wins
28 points
13 wins
26 points
12 wins
24 points
11 wins
22 points
10 wins
20 points
9 wins
18 points
84 matches
168 points
 

With 168 points out of 240 already assigned to top 7 teams, the balance can be distributed equally among the rest, giving the other 9 teams 8 points each. As some team has to take the 8th position in the points table and qualify for the next round, the minimum points needed to do the same shall be 8.

ii) What is the maximum possible point scored by a team which does not qualify for the second round?

Sol. A team which doesn’t qualify must have equal or lesser points than each of the teams which qualify. In order to maximize the score of a team not making it to the second round we can maximize the points among top 9 teams (as only 8 shall qualify to second round from a particular group).

Here we can begin by eliminating those points which cannot be scored by the top 9 teams i.e. points from matches among the bottom 7 teams. The minimum points scored by bottom 7 teams together shall be 7C2 x 2 = 42 points.

The balance (240 – 42) = 198 points can be distributed equally among the rest 9 teams by letting them win 198/9 = 22 points each.

As only 8 among the 9 top teams shall proceed to the next round, the maximum points with which a team does not qualify for the second round is 22.

iii) If all even ranked players lose in the second round then what is maximum difference between the ranks of any two players qualifying for the third round?

Sol. If the even ranked players lose their respective games, then the list of winners who qualify to the third round are –

Matches
Competing players
Winners
Match 1
1
16
1
Match 2
2
15
15
Match 3
3
14
3
Match 4
4
13
13
Match 5
5
12
5
Match 6
6
11
11
Match 7
7
10
7
Match 8
8
9
9

The maximum difference the ranks of any two players qualifying to the third round is
(15 – 1) = 14

iv) What is the lowest possible rank of a player who won the tournament by beating the 1st ranked player in the final round?

Sol. As player ranked 1 reached the final round, it is clear that winners of 1st, 3rd, 5th and 7th matches must have won the third round.

The lowest rank available in the second round was 16, but as it was scheduled to play against 1 (which reached the final as per the question) it could not have reached the third round.

Player ranked 15 would have played the second match of the second round and even if it won the second round match it would feature in the opponent team of 1 in the third round of tug of war. Hence it could not have reached the final.

Player ranked 14 would have played the third match of the second round and could have reached the final and won against 1. Hence the answer is 14.

v) If the player ranked 14 won the toss in the final round and picked 1 coin in the first turn and did not make any mistake after that, will (s)he cause an upset?

Sol. As 14 could also be playing the final round against 16 (a player ranked below itself), even if (s)he goes on to win, it may or may not be an upset. Hence answer to this question can’t be determined.

vi) If the best possible ranked players reached the final round (such that sum of their ranks is lowest possible among the combination of players that could reach the final round together), and the player ranked lower among them won the toss then what must be her/his decision to ensure her/his victory? (it is to be noted that both players have to pick the number of marbles equal to their rank in their respective first turns in the final round)

Sol. The lowest possible sum total of ranks of two players who can reach finals together shall be 4, when player ranked 1 and 3 reach the final round.

As the number of marbles to be picked in respective first turns have already been defined, we know that after both players would have picked once, they would remove (1 + 3) = 4 marbles together and leave 46 on the table for the player who picked first to take the next turn.

In order to pick the last marble a player would have to leave exactly 6 coins on the table for her/his opponent at the end to ensure victory. From there no matter what number of marbles the opponent picks one can ensure its win in the last turn (refer below table):

6 marbles are left on the table
Opponent picks
Winner picks
5
1
4
2
3
3
2
4
1
5

This implies that from any position, a player can maintain a sum of 6 marbles (which is sum of minimum and maximum limit of total marbles to be picked in a turn i.e. 5 + 1) for the opponents turn followed by her/his turn.

In this case as player ranked 3 shall win the toss, (s)he can definitely ensure her/his victory only by leaving 6 or any multiple of 6 marbles for the opponent. Hence player ranked 3 shall choose to pick first, and after both players have picked the stipulated number of marbles (i.e. 3+1 = 4) in respective first turns, player ranked 3 shall pick 4 marbles to leave the opponent with 42 marbles (a multiple of 6) and ensure her/his win from there on.

Thursday, 4 May 2017

Binary Logic



Classification of persons in Binary Logic:

1. Truth Teller: Someone who always tells the truth (all statements made has to be assumed to be true).

2. Liar: Someone who always lies (all statements made has to be assumed to be false).

3. Alternator: Someone who alternately lies and tells the truth in any order (any two statements in a row will consist of exactly one true and one false statement).

Some typical statements and their implications:

i) I am a liar – no liar and truth teller will ever make this statement as it would end up becoming a true and false statement respectively. Hence if such a statement is given, we can conclude that the speaker is definitely an Alternator and the given statement is false. Also statements immediately preceding and following it from the same speaker will be true statements.

ii) I am not a truth teller – like previous example this statement too can only be made by an Alternator and the nature of the statement shall be true. Also statements immediately preceding and following it from the same speaker will be false statements.

iii) I am an alternator – this can either be a true statement of an Alternator or a false statement of a Liar. In both cases the immediately preceding and following statements of the same speaker will be false.

iv) I am not an alternator – this can be a false statement of an Alternator or a true statement of a Truth Teller. In both cases the immediately preceding and following statements of the same speaker will be true.

In case one of the above types of statements is given, then one can start with them and work out few definitely correct/false statements which shall allow solving the set (eg #1). In the absence of such direct clues, one has to work out different possibilities to get to the answer (eg #2).

#1. Each of three friends A, B and C are fond of exactly one of the three fruits – apple, banana and orange with no two of them liking the same fruit. Also it is known that each of them can be any of truth tellers, liars and alternators. On being asked about their choice of fruits and talking patterns they gave the following answers –

A:
I like apple

B does not like banana

C is an alternator


B:
I like orange

A is a liar

C likes apple


C:
I like banana

I am not an alternator

B likes apple

The person who likes apple is a:

a) Truth Teller     b) Liar     c) Alternator     d) Either b or c

Sol. After browsing through all statements made by A, B and C one can make out that C’s second statement is either a true statement of a truth teller or a false statement of an alternator – irrespective of which C’s first and third statement have to be true. This gives us the following result –

A
Orange
B
Apple
C
Banana

Based on above we can determine that A’s first statement is false and the second one is true. As the three of them have to be one of truth tellers/liars/alternators; we can also conclude that A is an alternator and her third statement is hence false (which means C is not an alternator). This leads us to the conclusion that C is a truth teller; thus C’s second statement also can be marked as true.

Hereafter when we analyse B’s statements we realise they all are false; so B must be a liar. With ‘T’ standing for True and ‘F’ for False the nature of statements will be as follows:

A:
I like apple
F

B does not like banana
T

C is an alternator
F



B:
I like orange
F

A is a liar
F

C likes apple
F



C:
I like banana
T

I am not an alternator
T

B likes apple
T

Ans. Option b


#2. There is exactly one truth teller, one liar and one alternator among A, B and C. When asked about their identities they gave the following responses –

A:
I am a truth teller

C is an alternator

B is a liar


B:
I am not a liar

C is an alternator

A is a liar


C:
I am a truth teller

B is not a liar

A is not a truth teller

Given that there are only two males among them - the truth teller and liar; who is the only female among the three?

a) A     b) B     c) C     d) Anyone of them
 
Sol. Here as none of the statements can be termed as definitely true or false just by reading them, we can start by assuming each one of them as truth teller respectively.

Let A be the truth teller in case 1, B in case 2 and C in case 3; then we get the following result –



Case 1
Case 2
Case 3
A:
I am a truth teller
T
F
F

C is an alternator
T
T
F

B is a liar
T

F





B:
I am not a liar
F
T
T

C is an alternator
T
T
F

A is a liar

T
T





C:
I am a truth teller


T

B is not a liar


T

A is not a truth teller


T

In case 1 as A’s all statements are true, B is supposed to be a liar. However B’s second statement concurs with that of A’s and becomes true. As a liar cannot make a true statement, case 1 is not correct.

Similarly case 2 can also be eliminated as B is assumed to be a truth teller and his third statement terms A as a liar. However they both make same second statements and the assumed liar (A) ends up making a correct statement.

With case 1 & 2 eliminated we can conclude case 3 has to be correct which means C is the truth teller. As per C, B is not a liar, hence B must be an alternator and also A must be the liar.
As the female has to be the alternator here, B is the only female among the three.

Ans. Option b