Induction puzzles are logic puzzles, which are examples of multi-agent reasoning, where the solution evolves along with the principle of induction.
A puzzle's scenario always involves multiple players with the same reasoning capability, who go through the same reasoning steps. According to the principle of induction, a solution to the simplest case makes the solution of the next complicated case obvious. Once the simplest case of the induction puzzle is solved, the whole puzzle is solved subsequently.
Typical tell-tale features of these puzzles include any puzzle in which each participant has a given piece of information (usually as common knowledge) 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 — they are capable of theory of mind (that "every participant knows modus ponens" is common knowledge). Also, the inaction of a participant is a non-verbal communication of that participant's lack of knowledge, which then becomes common knowledge to all participants who observed the inaction.
The muddy children puzzle is the most frequently appearing induction puzzle in scientific literature on epistemic logic. Muddy children puzzle is a variant of the well known wise men or cheating wives/husbands puzzles.
Hat puzzles are induction puzzle variations that date back to as early as 1961. In many variations, hat puzzles are described in the context of prisoners. In other cases, hat puzzles are described in the context of wise men.
Muddy Children Puzzle
Description
A group of attentive children is told that some of them have muddy faces. Each child can see the faces of the others, but cannot tell if his or her own face is muddy. The children are told that those with muddy faces must step forward, but any child with a clean face who steps forward will be punished. At the count of three, every child who believes that his or her face is muddy must step forward simultaneously; any child who signals to another in any way will be punished. If any child with a muddy face has not stepped forward, the process will be repeated. At a given iteration, all muddy children and only them step forward. What is their thought process and on which turn does it happen?
Logical solution
Assuming that each child has—and knows each of the others to have—perfect logic all children with muddy faces () will step forward together on turn . The children have different information, depending on whether their own face is muddy or not. Each member of sees muddy faces, and knows that those children will step forward on turn if they are the only muddy faces. When that does not occur, each member of knows that he or she is also a member of , and steps forward on turn . Each non-member of sees muddy faces, and will not expect anyone to step forward until at least turn .
Assume there are two children, Alice and Bob, and that only Alice is muddy (). Alice knows that "some" children have muddy faces but that nobody else's face is muddy, meaning that her own face must be muddy and she steps forward on turn one. Bob, seeing Alice's muddy face, has no way of knowing on turn one if his own face is muddy or not so he does not step forward for fear of punishment (only after Alice having stepped forward and the game being ended does Bob understand that his face must be clean). If both Alice and Bob are dirty (), each is in the position of Bob when : neither dare step forward on turn one. However, by turn two Bob knows that Alice must have seen that his face is muddy (because she did not step forward on turn one), and so he steps forward on turn two. Using the same logic, Alice also steps forward on turn two.
Assume that there is a third child, Charlie. If only Alice is muddy (), she will see no muddy faces and will step forward on turn one. If both Alice and Bob are muddy (), neither can step forward on turn one but each will know by turn two that the other saw a muddy face—which they can see is not Charlie's—so their own face must be muddy and both will step forward on turn two. Charlie, seeing two muddy faces, does not know on turn two whether his own face is muddy or not until Alice and Bob both step forward (indicating that his own face is clean). If all three are muddy (), each is in the position of Charlie when : when two people fail to step forward on turn two, each knows that the other sees two muddy faces meaning that their own face must be muddy, and each steps forward on turn three.
It can be proven that muddy children will step forward at turn .
Game-theoretic solution
Muddy children puzzle can also be solved using backward induction from game theory. Muddy children puzzle can be represented as an extensive form game of imperfect information. Every player has two actions — stay back and step forwards. There is a move by nature at the start of the game, which determines the children with and without muddy faces. Children do not communicate as in non-cooperative games. Every stroke is a simultaneous move by children. It is a sequential game of unlimited length. The game-theoretic solution needs some additional assumptions: All children are rational and all children's rationality is common knowledge. This means that Alice is rational, Alice knows that Bob is rational and Alice knows that Bob knows that Charlie is rational and so on and vice versa. Stepping forward without having a muddy face results in a big penalty. Stepping forward with a muddy face results in a reward. Every stroke results in minor negative penalty aka discount factor for every child until any of them stepped forward. Any multiple of the minor penalty is always a lesser evil than the big penalty. If only Alice is muddy, the last assumption makes it irrational for her to hesitate. If Alice and Bob are muddy, Alice knows that Bob's only reason of staying back after the first stroke is the apprehension to receive the big penalty of stepping forward without a muddy face. In the case with muddy children, receiving times the minor penalty is still better than the big penalty.
The King's Wise Men hat puzzle Description
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?
Solution
The King's Wise Men 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 three scenarios: one blue hat, two blue hats or three 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, then 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 no one has stood up quickly, then they must all be wearing blue hats.
Josephine's Problem
Description
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?
Solution
Josephine's Problem 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.