12 Balls, 1 Defective

You have 12 balls, 11 of which have the same weight. The remaining one is defective and either heavier or lighter than the rest. You can use a balance scale to compare weights in order to find which is the defective ball and whether it is heavier or lighter. How many measurement do you need so that will be surely able to do it?

It is easy to see that if we have more than 9 balls, we need at least 3 measurements. We will prove that 3 measurements are enough for 12 balls.

We place 4 balls on each side of the scale. Let balls 1, 2, 3, 4 be on the right side, and balls 5, 6, 7, 8 on the left side.

CASE 1. The scale does not tip to any side. For the second measurement we place on the left side balls 1, 2, 3, 9 and on the right side balls 4, 5, 10, 11.

If the scale again does not tip to any side, then the defective ball is number 12 and we can check whether it is heavier or lighter with our last measurement.

If the scale tips to the left side, then either the defective ball is number 9 and is heavier, or it is number 10/11 and is lighter. We measure up balls 10 and 11 against each other and if one of them is lighter than the other, then it is the defective one. If they have the same weight, then ball 9 is the defective one.

If the scale tips to the right side, the procedure is similar.

CASE 2. Let the scale tip to the left side during the first measurement. This means that either one of the balls 1, 2, 3, 4 is defective and it is heavier, or one of the balls 5, 6, 7, 8 is defective and it is lighter. Clearly, balls 9, 10, 11, 12 are all genuine. Next we place balls 1, 2, 5, 6 on one side and balls 3, 7, 9, 10 on the other side.

If the scale tips to the left, then either one of the balls 1, 2 is defective and it is heavier, or ball 8 is defective and lighter. We just measure up balls 1 and 2 against each other and find out which among the three is the defective one.

If the scale tips to the right, the procedure is similar.

If the scale does not tip to any side, then either the defective ball is 4 and it is heavier, or the defective ball is 8 and it is lighter. We just measure up balls 1 and 4 against each other and easily find the defective ball.

Gods of Truth

You encounter three Gods in a room – the God of Truth, the God of Lie and the God of Uncertainty. You don’t know which one is which, but know that the God of Truth always says the truth, the God of Lie always says the lie and the God of Uncertainty sometimes lies and sometimes says the truth. You can ask in succession each of the Gods a unique question, to which they can reply only with “Yes” or “No”. However, their responses will be in their native language – “Da” or “Ne”, and you don’t know which translation to which answer corresponds. Your task is to figure out what questions to ask the Gods, so that will recognize which one of them is the God of Truth, which one is the God of Lie and which one is the God of Uncertainty.

Label the gods with numbers – 1, 2, and 3.

First, ask god 1 “If I ask you whether god 2 is random, would you say ‘Da’?”. If he responds “Da”, then god 3 is not the god of uncertainty. If he responds “Ne”, then god 2 is not the god of uncertainty. In both cases we will be able to find a god which is not the god of uncertainty, let without of generality that is god 3.

Next, ask god 3 “If I ask you whether you are the God of Lie, would you say ‘Da’?”. If he says “Da”, then he is the God of Truth. If he says “No”, then he is the God of Lie.

Finally, ask god 3 whether god 1 is the God of Uncertainty and conclude the identities of all gods.

Friends and Enemies

Show that in each group of 6 people, there are either 3 who know each other, or 3 who do not know each other.

Let’s call the people A, B, C, D, E, F. Person A either knows at least 3 among B, C, D, E, F, or does not know at least 3 among B, C, D, E, F.

Assume the first possibility – A knows B, C, D. If B and C know each other, C and D know each other, or B and D know each other, then we find a group of 3 people who know each other. Otherwise, B, C, and D form a group in which no-one knows the others.

If A doesn’t know at least 3 among B, C, D, E, F, the arguments are the same.

Gun Duel

Mick, Rick, and Nick arrange a three-person gun duel. Mick hits his target 1 out of every 3 times, Rick hits his target 2 out of every 3 times, and Nick hits his target every time. If the three are taking turns shooting at each other, with Mick starting first and Rick second, what should be Mick’s strategy?

Clearly, Mick should not aim for Rick, because if he kills him, then he will be killed by Nick. Similarly, Nick should not aim for Mick, because if he kills him, then he also will be killed by Nick. Therefore, if Nick ends up against alive Mick and Rick, he will aim at Rick, because would prefer to face off a weaker opponent afterward. This means that if Rick is alive after Mick shoots, he will shoot at Nick.

Now if Mick shoots at Nick and kills him, then he will have to face off Rick with chance of survival less than 1/3. Instead, if he decides to shoot in the air, then he will face off Rick or Nick with chance of survival at least 1/3. Therefore Mick’s strategy is to keep shooting in the air, until he ends up alone against one of his opponents.