Induction puzzles

Induction puzzles are logic puzzles which are solved via the application of the principle of induction. In most cases, the puzzle's scenario will involve several participants with reasoning capability and the solution to the puzzle will be based on identifying what would happen in an obvious case, and then repeating the reasoning that: "as soon as one of the participants realises that the obvious case has not happened, they can eliminate it from their reasoning, so creating a new obvious case".

Typical tell-tale features of these puzzles include any puzzle in which each participant has a given piece of information about all other participants but not themselves. Also, usually some kind of hint is given to suggest that the participants can trust each other's intelligence.

Examples

The King's Wise Men: The King called the three wisest men in the country to his court to decide who would become his new advisor. He placed a hat on each of their heads, such that each wise man could see all of the other hats, but none of them could see their own. Each hat was either white or blue. The king gave his word to the wise men that at least one of them was wearing a blue hat; in other words, there could be one, two, or three blue hats, but not zero. The king also announced that the contest would be fair to all three men. The wise men were also forbidden to speak to each other. The king declared that whichever man stood up first and correctly announced the colour of his own hat would become his new advisor. The wise men sat for a very long time before one stood up and correctly announced the answer. What did he say, and how did he work it out?

Josephine's Problem: In Josephine's Kingdom every woman has to pass a logic exam before being allowed to marry. Every married woman knows about the fidelity of every man in the Kingdom except for her own husband, and etiquette demands that no woman should be told about the fidelity of her husband. Also, a gunshot fired in any house in the Kingdom will be heard in any other house. Queen Josephine announced that at least one unfaithful man had been discovered in the Kingdom, and that any woman knowing her husband to be unfaithful was required to shoot him at midnight following the day after she discovered his infidelity. How did the wives manage this?

Alice at the Convention of Logicians: At the Secret Convention of Logicians, the Master Logician placed a band on each attendee's head, such that everyone else could see it but the person themselves could not. There were many different colours of band. The Logicians all sat in a circle, and the Master instructed them that a bell was to be rung in the forest at regular intervals: at the moment when a Logician knew the colour on his own forehead, he was to leave at the next bell. They were instructed not to speak, nor to use a mirror or camera or otherwise avoid using logic to determine their band colour. In case any impostors had infiltrated the convention, anyone failing to leave on time would be gruffly removed at the correct time. Similarly, anyone trying to leave early would be gruffly held in place and removed at the correct time. The Master reassured the group by stating that the puzzle would not be impossible for any True Logician present. How did they do it?^[1]

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 there was one blue hat. The person with that hat would see two white hats, and since the king specified that there is at least one blue hat, that wise man would immediately know the colour of his hat. However, the other two would see one blue and one white hat and would not be able to immediately infer any information from their observations. Therefore, this scenario would violate the king's specification that the contest would be fair to each. So there must be at least two blue hats.
• Suppose then that there were two blue hats. Each wise man with a blue hat would see one blue and one white hat. Supposing that they have already realized that there cannot be only one (using the previous scenario), they would know that there must be at least two blue hats and therefore, would immediately know that they each were wearing a blue hat. However, the man with the white hat would see two blue hats and would not be able to immediately infer any information from his observations. This scenario, then, would also violate the specification that the contest would be fair to each. So there must be three blue hats.

Since there must be three blue hats, the first man to figure that out will stand up and say blue.

Alternative solution: This does not require the rule that the contest be fair to each. Rather it relies on the fact that they are all wise men, and that it takes some time before they arrive at a solution. There can only be 3 scenarios, one blue hat, two blue hats or 3 blue hats. If there was only one blue hat, then the wearer of that hat would see two white hats, and quickly know that he has to have a blue hat, so he would stand up and announce this straight away. Since this hasn't happened, then there must be at least two blue hats. If there were two blue hats, than either one of those wearing a blue hat would look across and see one blue hat and one white hat, but not know the colour of their own hat. If the first wearer of the blue hat assumed he had a white hat, he would know that the other wearer of the blue hat would be seeing two white hats, and thus the 2nd wearer of the blue hat would have already stood up and announced he was wearing a blue hat. Thus, since this hasn't happened, the first wearer of the blue hat would know he was wearing a blue hat, and could stand up and announce this. Since either one or two blue hats is so easy to solve, and that no one has stood up quickly, then they must all be wearing blue hats.

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 do not, they know their own husband was the nth.

This problem is also known as the Cheating Husbands Problem, the Unfaithful Wives Problem, the Muddy Children Problem. It is logically identical to the Blue Eyes Problem

This problem also appears as a problem involving black hats and white hats in C.L.Liu's classic textbook 'Elements of Discrete Mathematics'.

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 did not, that can only be because your own band is the same colour, so you can leave at the second bell.
• Therefore, every logician would watch until a group of a given colour that they expected to leave failed to leave. Then they would know that they had that colour, and would leave on the next bell.
• When only one colour remained, that colour would all leave on the next bell, because they would know that they could not have any other colour (since then it would be impossible for them to know their colour).

See also

• Prisoners and hats puzzle — in-depth look at this induction puzzle
• Epistemic logic

References

1. Charatonik, Włodzimierz J. (2010). "Alice at the logicians convention" (PDF). Missouri University of Science and Technology. Archived (PDF) from the original on 2010-07-05. Retrieved 2015-07-31.