Induction puzzles
[4][14] 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.
There is a move by nature at the start of the game, which determines the children with and without muddy faces.
The King called the three wisest men in the country to his court to decide who would become his new advisor.
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.
[15] The King's Wise Men is one of the simplest induction puzzles and one of the clearest indicators to the method used.
Rather it relies on the fact that they are all wise men, and that it takes some time before they arrive at a solution.
In Josephine's Kingdom every woman has to pass a logic exam before being allowed to marry.
They were instructed not to speak, nor to use a mirror or camera or otherwise avoid using logic to determine their band colour.
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.
[19] One variation received some new publicity as a result of Todd Ebert's 1998 Ph.D. thesis at the University of California, Santa Barbara.
[20] It is a strategy question about a cooperative game, which has connections to algebraic coding theory.
They are to raise their hands if they see a red hat on another player as they stand in a circle facing each other.
Four prisoners are arrested for a crime, but the judge offers to spare them from punishment if they can solve a logic puzzle.
In common with many puzzles of this type, the solution relies upon the assumption that all participants are rational and intelligent enough to make the appropriate deductions.
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, and if enough prisoners resume their liberty they can rescue the others.
Starting from the beginning of the line, each prisoner must correctly identify the color of his hat or he is killed on the spot.
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.
Assuming the axiom of choice, there exists a set of representative sequences—one from each equivalence class.
They then proceed guessing their hat color as if they were in the representative sequence from the appropriate equivalence class.
The question is, what is the optimal strategy for the prisoners such that the fewest of them die in the worst case?
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.
Similarly, every later person in the line knows every digit of the sequence except the one corresponding to his own hat color.
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.
Similar strategies can be applied to team sizes of N = 2k−1 and achieve a win rate (2k-1)/2k.
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.
