Induction puzzles

There is a set of attentive children. They think perfectly logically. The children consider it possible to have a muddy face. None of the children can determine the state of their own face themselves. But, every child knows the state of all other children's faces. A custodian tells the children that at least one of them has a muddy face. The children are each told that they should step forward if they know that their own face is muddy. Hereafter, the custodian starts to count and after every stroke, every muddy child has an opportunity to step forward.[4][5][13]

Let's assume that there are just 2 children: Alice and Bob. If only Alice is dirty, she will step forward at the first stroke, because she does not see any other dirty faces. The same is true for Bob. If Alice sees Bob not stepping forward at the first stroke, she must conclude that he certainly sees another muddy child and they will step forward simultaneously at the second stroke.

Let's assume that there are just 3 children: Alice, Bob, and Charly. If there are less than 3 muddy children, the puzzle evolves like in the case with 2 children. If Charly sees that Alice and Bob are muddy and not stepping forward at the second stroke, they all together will step forward at the third stroke.

It can be proven that ${\displaystyle X}$ muddy children will step forward after ${\displaystyle X}$ strokes.[4][14]

Representation of Muddy Children Puzzle for two players in extensive form. The preliminary move by nature is colored green. Alice is colored red and Bob is colored blue. This game has only one single Nash equilibrium. Actions predicted by this equilibrium are colored black.

Muddy children puzzle can also be solved using backward induction from game theory.[13] 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:

1. 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 Charly is rational and so on and vice versa.
2. Stepping forward without having a muddy face results in a big penalty.
3. Stepping forward with a muddy face results in a reward.
4. 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 ${\displaystyle X}$ muddy children, receiving ${\displaystyle X}$ times the minor penalty is still better than the big penalty.

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?

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.

In Josephine's Kingdom every woman has to pass a logic exam before being allowed to marry.[15] 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?

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.

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

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?[16]

Alice at the convention of Logicians 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).

A number of players are each wearing a hat, which may be of various specified colours. Players can see the colours of at least some other players' hats, but not that of their own. With highly restricted communication or none, some of the players must guess the colour of their hat. The problem is to find a strategy for the players to determine the colours of their hats based on the hats they see and what the other players do. In some versions, they compete to be the first to guess correctly; in others, they can work out a strategy beforehand to cooperate and maximize the probability of correct guesses.[17]

One variation received some new publicity as a result of Todd Ebert's 1998 Ph.D. thesis at the University of California, Santa Barbara.[18] It is a strategy question about a cooperative game, which has connections to algebraic coding theory.[19]

Three players are told that each of them will receive either a red hat or a blue hat. They are to raise their hands if they see a red hat on another player as they stand in a circle facing each other. The first to guess the colour of his or her hat correctly wins.

All three players raise their hands. After the players have seen each other for a few minutes without guessing, one player announces "Red", and wins. How did the winner do it, and what is the color of everyone's hats?

First, if two people had blue hats, not everyone's hand would have been raised. Next, if player 1 had seen a blue hat on player 2 & a red hat on player 3, then player 1 would have known immediately that his own hat must be red. Thus any player who sees a blue hat can guess at once. Finally, the winner realizes that since no one guesses at once, there must be no blue hats, so every hat must be red.[20]

In the case where every player has to make a guess, but they are free to choose when to guess, there is a cooperative strategy that allows every player to guess correctly unless all the hats are the same colour. Each player should act as follows:

1. Count the numbers b of blue hats and r of red hats that you see.
2. Wait b seconds or r seconds, whichever is sooner.
3. If nobody has yet spoken, guess that your hat is blue if you can see fewer blue hats than red hats, or red if you can see fewer red hats than blue hats.
4. If you have not yet spoken, guess that your hat is of the opposite colour to that of one of the first people to speak.

Suppose that in total there are B blue hats and R red hats. There are three cases.

If B = R then those players wearing blue hats see B−1 blue hats and B red hats, so wait B−1 seconds then correctly guess that they are wearing a blue hat. Similarly, those players wearing a red hat will wait R−1 seconds before guessing correctly that they are wearing a red hat. So all players make a correct guess at the same time.

If B < R then those wearing a blue hat will see B−1 blue hats and R red hats, whilst those wearing a red hat will see B blue hats and R−1 red hats. Since B−1 < B ≤ R−1, those players wearing a blue hat will be the first to speak, guessing correctly that their hat is blue. The other players then guess correctly that their hat is red.

The case where R < B is similar.

Four prisoners, four hats and a screen

According to the story, four prisoners are arrested for a crime, but the jail is full and the jailer has nowhere to put them. He eventually comes up with the solution of giving them a puzzle so if they succeed they can go free but if they fail they are executed.

The jailer seats three of the men into a line. A faces the wall, B faces A, and C faces B and A. A fourth man is put behind a screen (or in a separate room). The jailer gives all four men party hats. He explains that there are two black hats and two white hats, that each prisoner is wearing one of the hats, and that each of the prisoners see only the hats in front of him but neither on himself nor behind him. The fourth man behind the screen can't see or be seen by any other prisoner. No communication among the prisoners is allowed.

If any prisoner can figure out what color hat he has on his own head with 100% certainty (without guessing) he must then announce it, and all four prisoners go free. If any prisoner suggests an incorrect answer, all four prisoners are executed. The puzzle is to find how the prisoners can escape.

The prisoners know that there are only two hats of each color. So if C observes that A and B have hats of the same color, C would deduce that his own hat is the opposite color. However, if A and B have hats of different colors, then C can say nothing. The key is that prisoner B, after allowing an appropriate interval, and knowing what C would do, can deduce that if C says nothing the hats on A and B must be different; able to see A's hat, he can deduce his own hat color.

In common with many puzzles of this type, the solution relies upon the assumption that all participants are totally rational and intelligent enough to make the appropriate deductions.

After solving this puzzle, some insight into the nature of communication can be gained by pondering whether the meaningful silence of prisoner C violates the "No communication" rule (given that communication is usually defined as the "transfer of information").

In this variant there are 3 prisoners and 3 hats. Each prisoner is assigned a random hat, either red or blue. In all, there are three red hats and two blue. Each person can see the hats of two others, but not their own. On a cue, they each have to guess their own hat color or pass. They win release if at least one person guessed correctly and none guessed incorrectly (passing is neither correct nor incorrect).

This puzzle doesn't have a 100% winning strategy, so the question is: What is the best strategy? Which strategy has the highest probability of winning?

If you think of colors of hats as bits, this problem has some important applications in coding theory.

The solution and the discussion of this puzzle can be found here (also a solution to the analogous 7-hat puzzle) and other 3 variants are available on this Logic Puzzles page (they are called Masters of Logic I–IV).

In a variant of this puzzle, the prisoners know that there are 2 black hats and 2 white hats, and there is a wall in between A and B, yet the prisoners B, C & D can see who's in front of them i.e. D sees B, C and the wall, B sees the wall, and C sees B & the wall. (A again cannot be seen and is only there to wear one of the black hats.) How can they deduce the colours of all of them without communicating?

There are two cases: in the trivial case, two of the four prisoners wear the black hats. Each of the other two prisoners can see that one prisoner is wearing the off-colour hat. In the non-trivial case, two of the four prisoners wear hats of the same colour, while A and C wear the black hats. After a while, all four prisoners should be able to deduce that, because D and B were not able to state the colour of their own hat, A and C must be wearing the black hats.

In another variant, only three prisoners and five hats of known colours (in this example two black and three white) are involved. The three prisoners are ordered to stand in a straight line facing the front, with A in front and C at the back. They are told that there will be two black hats and three white hats. One hat is then put on each prisoner's head; each prisoner can only see the hats of the people in front of him and not on his own. The first prisoner that is able to announce the color of his hat correctly will be released. No communication between the prisoners is allowed.

Assume that A wears a black hat:

• If B wears a black hat as well, C can immediately tell that he is wearing a white hat after looking at the two black hats in front of him.
• If B wears a white hat, C will be unable to tell the color of his hat (because there is a black and a white). So B can quickly deduce from A's black hat and C's lack of response that he (B) is wearing a white hat.

So if A wears a black hat there will be a fairly quick response from B or C.

Assume that A wears a white hat:

• C does not see two black hats, so he is unable to tell his hat color.
• B sees only a white hat, so he can't tell anything about his hat.

In this case A, B and C would remain silent for some time, until A finally deduces that he must have a white hat because C and B have remained silent for some time.

As mentioned, there are three white hats and two black hats in total, and the three prisoners know this. In this riddle, you can assume that all three prisoners are very clever and very smart. If C could not guess the color of his own hat that is because he saw either two white hats or one of each color. If he saw two black hats, he could have deduced that he was wearing a white hat.

In this variant there are 10 prisoners and 10 hats. Each prisoner is assigned a random hat, either red or blue, but the number of each color hat is not known to the prisoners. The prisoners will be lined up single file where each can see the hats in front of him but not behind. Starting with the prisoner in the back of the line and moving forward, they must each, in turn, say only one word which must be "red" or "blue". If the word matches their hat color they are released, if not, they are killed on the spot. A sympathetic guard warns them of this test one hour beforehand and tells them that they can formulate a plan where by following the stated rules, 9 of the 10 prisoners will definitely survive, and 1 has a 50/50 chance of survival. What is the plan to achieve the goal?

The prisoners agree that if the first prisoner sees an odd number of red hats, he will say "red". This way, the nine other prisoners will know their own hat color after the prisoner behind them responds.

As before, there are 10 prisoners and 10 hats. Each prisoner is assigned a random hat, either red or blue, but the number of each color hat is not known to the prisoners. The prisoners are distributed in the room such that they can see the hats of the others but not their own. Now, they must each, simultaneously, say only one word which must be "red" or "blue". If the word matches their hat color they are released, and if enough prisoners resume their liberty they can rescue the others. A sympathetic guard warns them of this test one hour beforehand. If they can formulate a plan following the stated rules, 5 of the 10 prisoners will definitely be released and be able to rescue the others. What is the plan to achieve the goal?

The prisoners pair off. In a pair (A, B) of the prisoners A says the color he can see on the head of B, who says the opposite color he sees on the head of A. Then, if both wear hats with the same color, A is released (and B is not), if the colors are different, B is released (and A is not). In total, 5 prisoners answer correctly and 5 do not. This assumes the pair can communicate who is A and who is B, which may not be allowed.

Alternatively, the prisoners build two groups of 5. One group assumes that the number of red hats is even, the other assumes that there is an odd number of red hats. Similar to the variant with hearing, they can deduce their hat color out of this assumption. Exactly one group will be right, so 5 prisoners answer correctly and 5 do not.

Note that the prisoners cannot find a strategy guaranteeing the release of more than 5 prisoners. Indeed, for a single prisoner, there are as many distributions of hat colors where he says the correct answer than there are where he does not. Hence, there are as many distributions of hat colors where 6 or more prisoners say the correct answer than there are where 4 or fewer do so.

In this variant, a countably infinite number of prisoners, each with an unknown and randomly assigned red or blue hat line up single file line. Each prisoner faces away from the beginning of the line, and each prisoner can see all the hats in front of him, and none of the hats behind. Starting from the beginning of the line, each prisoner must correctly identify the color of his hat or he is killed on the spot. As before, the prisoners have a chance to meet beforehand, but unlike before, once in line, no prisoner can hear what the other prisoners say. The question is, is there a way to ensure that only finitely many prisoners are killed?

If one accepts the axiom of choice, and assumes the prisoners each have the (unrealistic) ability to memorize an uncountably infinite amount of information and perform computations with uncountably infinite computational complexity, the answer is yes. In fact, even if we allow an uncountable number of different colors for the hats and an uncountable number of prisoners, the axiom of choice provides a solution that guarantees that only finitely many prisoners must die provided that each prisoner can see the hats of every other prisoner (not just those ahead of them in a line), or at least that each prisoner can see all but finitely many of the other hats. The solution for the two color case is as follows, and the solution for the uncountably infinite color case is essentially the same:

The prisoners standing in line form a sequence of 0s and 1s, where 0 is taken to represent blue, and 1 is taken to represent red. Before they are put into the line, the prisoners define the following equivalence relation over all possible sequences that they might be put into: Two sequences are equivalent if they are identical after a finite number of entries. From this equivalence relation, the prisoners get a collection of equivalence classes. Assuming the axiom of choice, there exists a set of representative sequences—one from each equivalence class. (Almost every specific value is impossible to compute, but the axiom of choice implies that some set of values exists, so we assume that the prisoners have access to an oracle.)

When they are put into their line, each prisoner can see all but a finite number of hats, and can therefore see which equivalence class the actual sequence of hats belongs to. (This assumes that each prisoner can perform an uncountably infinite number of comparisons to find a match, with each class comparison requiring a countably infinite number of individual hat-comparisons). They then proceed guessing their hat color as if they were in the representative sequence from the appropriate equivalence class. Because the actual sequence and the representative sequence are in the same equivalence class, their entries are the same after some finite number N of prisoners. All prisoners after these first N prisoners are saved.

Because the prisoners have no information about the color of their own hat and would make the same guess whichever color it has, each prisoner has a 50% chance of being killed. It may seem paradoxical that an infinite number of prisoners each have an even chance of being killed and yet it is certain that only a finite number are killed. The solution to this paradox lies in the fact that the function employed to determine each prisoner's guess is not Measurable function.

To see this, consider the case of zero prisoners being killed. This happens if and only if the actual sequence is one of the selected representative sequences. If the sequences of 0s and 1s are viewed as binary representations of a real number between 0 and 1, the representative sequences form a non-measurable set. (This set is similar to a Vitali set, the only difference being that equivalence classes are formed with respect to numbers with finite binary representations rather than all rational numbers.) Hence no probability can be assigned to the event of zero prisoners being killed. The argument is similar for other finite numbers of prisoners being killed, corresponding to a finite number of variations of each representative.

This variant is the same as the last one except that prisoners can hear the colors called out by other prisoners. The question is, what is the optimal strategy for the prisoners such that the fewest of them die in the worst case?

It turns out that, if one allows the prisoners to hear the colors called out by the other prisoners, it is possible to guarantee the life of every prisoner except the first, who dies with a 50% probability.

To do this, we define the same equivalence relation as above and again select a representative sequence from each equivalence class. Now, we label every sequence in each class with either a 0 or a 1. First, we label the representative sequence with a 0. Then, we label any sequence which differs from the representative sequence in an even number of places with a 0, and any sequence which differs from the representative sequence in an odd number of places with a 1. In this manner, we have labeled every possible infinite sequence with a 0 or a 1 with the important property that any two sequences which differ by only one digit have opposite labels.

Now, when the warden asks the first person to say a color, or in our new interpretation, a 0 or a 1, he simply calls out the label of the sequence he sees. Given this information, everyone after him can determine exactly what his own hat color is. The second person sees all but the first digit of the sequence that the first person sees. Thus, as far as he knows, there are two possible sequences the first person could have been labeling: one starting with a 0, and one starting with a 1. Because of our labeling scheme, these two sequences would receive opposite labels, so based on what the first person says, the second person can determine which of the two possible strings the first person saw, and thus he can determine his own hat color. Similarly, every later person in the line knows every digit of the sequence except the one corresponding to his own hat color. He knows those before him because they were called out, and those after him because he can see them. With this information, he can use the label called out by the first person to determine his own hat color. Thus, everyone except the first person always guesses correctly.

Ebert's version of the problem states that all players who guess must guess at the same predetermined time, but that not all players are required to guess. Now not all players can guess correctly, so the players win if at least one player guesses and all of those who guess do so correctly. How can the players maximise their chance of winning?

One strategy for solving this version of the hat problem employs Hamming codes, which are commonly used to detect and correct errors in data transmission. The probability for winning will be much higher than 50%, depending on the number of players in the puzzle configuration: for example, a winning probability of 87.5% for 7 players.

Similar strategies can be applied to team sizes of N = 2^k−1 and achieve a win rate (2^k-1)/2^k. Thus the Hamming code strategy yields greater win rates for larger values of N.

In this version of the problem, any individual guess has a 50% chance of being right. However, the Hamming code approach works by concentrating wrong guesses together onto certain distributions of hats. For some cases, all the players will guess incorrectly; whereas for the other cases, only one player will guess, but correctly. While half of all guesses are still incorrect, this results in the players winning more than 50% of the time.

A simple example of this type of solution with three players is instructive. With three players, there are eight possibilities; in two of them all players have the same colour hat, and in the other six, two players have one colour and the other player has the other colour.

The players can guarantee that they win in the latter cases (75% of the time) with the following strategy:

1. Any player who observes two hats of two different colours remains silent.
2. Any player who observes two hats of the same colour guesses the opposite colour.

In the two cases when all three players have the same hat colour, they will all guess incorrectly. But in the other six cases, only one player will guess, and correctly, that his hat is the opposite of his fellow players'.[21]