Induction Puzzles - Solutions

Solutions

The King's Wise Men: This is one of the simplest induction puzzles and one of the clearest indicators to the method used.

• Suppose that you are one of the wise men. Looking at the other wise men, you see they are both wearing white hats. Since there are only three hats in total and the king specified that there was at least one blue hat, you would immediately know that your own hat must be blue.
• Now suppose that you see the other wise men, and one is wearing a white hat and the other is wearing a blue hat. If your own hat was white, then the man you can see wearing the blue hat would be himself seeing two white hats and would - by the logic above - have immediately declared his hat colour. If he doesn't do this, it can only be because your hat isn't white, therefore it must be blue.
• Now suppose that you see the other wise men and both are wearing blue hats. You can't work anything out from this. However, if your own hat was white, then one of the two other wise men would be seeing a blue and a white hat, and would have declared his hat colour by the rule above. Thus, if he hasn't done so, he must also be seeing two blue hats and thus your hat must be blue.

Please note, that this problem has a subtle but major flaw: time. Exactly how long should one of the King's Wise Men wait before inferring anything from the other wise men's lack of action? This flaw is rightly eliminated in the statement of Josephine's Problem (with its midnights) and the Alice at the Convention of Logicians problem (with its regular intervals). It can also be eliminated by the men realising only someone wearing a blue hat could win, and thus all hats must be blue for it to be a fair test.

Josephine's Problem: This is another good example of a general case.

• If there is only 1 unfaithful husband, then every woman in the Kingdom knows that except for his wife, who believes that everyone is faithful. Thus, as soon as she hears from the Queen that unfaithful men exist, she knows her husband must be unfaithful, and shoots him.

• If there are 2 unfaithful husbands, then both their wives believe there is only 1 unfaithful husband (the other one). Thus, they will expect that the case above will apply, and that the other husband's wife will shoot him at midnight on the next day. When no gunshot is heard, they will realise that the case above did not apply, thus there must be more than 1 unfaithful husband and (since they know that everyone else is faithful) the extra one must be their own husband.

• If there are 3 unfaithful husbands, each of their wives believes there to be only 2, so they will expect that the case above will apply and both husbands will be shot on the second day. When they hear no gunshot, they will realize that the case above did not apply, thus there must be more than 2 unfaithful husbands and as before their own husband is the only candidate to be the extra one.

• In general, if there are n unfaithful husbands, each of their wives will believe there to be n-1 and will expect to hear a gunshot at midnight on the n-1th day. When they don't, they know their own husband was the nth.

This problem is also known as the Cheating Husbands Problem, the Unfaithful Wives Problem or the Muddy Children Problem.

Alice at the convention of Logicians: This is general induction plus a leap of logic.

• Leap of logic: Every colour must appear at least twice around the circle. This is because the Master stated that it would not be impossible for any Logician to solve the puzzle. If any colour existed only once around the circle, the Logician who bore it would have no way of knowing that the colour even existed in the problem, and it would be impossible for them to answer.

• Each of the Logicians can look around the circle and count the number of times they see each colour. Suppose that you are one of the Logicians and you see another colour only once. Since you know each colour must exist at least twice around the circle, the only explanation for a singleton colour is that it is the colour of your own band. For the same reason, there can only be one such singleton colour, and so you would leave on the first bell.

• Likewise any Logicians who see another colour only once should be able to determine their own colour, and will either leave with dignity or be thrown out as an infiltrator. Equivalently, any colour for which there are only two bands of that colour will be eliminated after the first bell has rung. Thereafter there must be at least three bands of any remaining colour.

• Suppose you do not see any colour once, but you do see a colour twice. If these were the only bands of this colour, then these two Logicians ought to have left at the first bell. Since they didn't, that can only be because your own band is the same colour, so you can leave at the second bell.

• The induction proceeds following the same pattern as used in Josephine's Problem.