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 (typically people) 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 others 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 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 take 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 tell another about the fidelity of her husband. A gunshot fired in any house in the Kingdom will be heard in any other. Queen Josephine announced that unfaithful men 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 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, 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. Anyone who left at the wrong bell was clearly not a true Logician but an evil infiltrator and would be thrown out of the Convention post haste; but the Master reassures the group by stating that the puzzle would not be impossible for anybody present. How did they do it?

olutions

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 the king specified that there were at most two white hats, 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.

Note also that, in all the rules above, it is only possible for a person wearing a blue hat to win. Thus, since the king said that the contest would be fair to all three men, that must be the configuration in use - and the wise man announced that his hat was blue.

Note finally 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 (lack of) action he sees in the other two wise men? This ugly flaw is rightly eliminated in the statement of Josephine's Problem (aka the 'marital infidelity' problem, with its midnights) and the Alice at the Convention of Logicians problem (with its 'regular intervals'). The flaw 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 hasbands, 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-1"th day. When they don't, they know their own husband was the "n"th.

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.

* Suppose that you are one of the Logicians. Looking around the circle, you see another colour only once. Since you know each colour must exist at least twice around the circle, your own band must be the same colour, so you can leave at the first bell.

* Now suppose that you see a colour twice. You would know that the case above ought to apply, and thus these two Logicians ought to leave at the first bell. If they don't, that can only be because your own band is the same colour - so you can leave at the bell "after" that one.

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

ee also

* Prisoners and hats puzzle — in-depth look at this induction puzzle