Hat puzzles are a delightful genre of logic puzzles whose number and diversity have swelled as enthusiasts concoct variation upon variation. The general theme of hat puzzles goes as follows: There are a bunch of prisoners who have been incarcerated by an evil tribe. The captors tell the prisoners that later in the day, they will participate in an execution ceremony. They will all be placed in a circle or in row, and a hat of some color will be placed on each prisoner’s head. Each will be able to see the color of the hats atop the heads of the others (or the people ahead of them if they are in a row) but will not be able to see the color of the hat that is on their own head. Each prisoner will be asked, either simultaneously or one after the other, to state aloud the color of the hat that he thinks is on his head, based on some instructions provided beforehand and on what the other prisoners said. If a prisoner gives the wrong answer, he or she, or perhaps all of the prisoners together, are executed. If they all guess correctly, the prisoners are freed. Such a game would usually be a grisly variation of Russian roulette, but fortunately, there almost always happens to be a friendly jailer around who allows the prisoners to confer before the event to decide on their best strategy in a cooperative manner. The goal is to come up with a strategy that allows as many of the prisoners to be freed as possible.

As you can see, there are enough places inside this template where different details can be inserted — the number of prisoners, the number of hat colors, whether they have to announce their hat color one at a time or all together, whether they are allowed to pass, whether they going to be freed together or individually, whether the game is competitive or cooperative or adversarial, and so on — allowing for a great deal of variation. The charm of such hat puzzles is that when you hear the puzzle, the first thought that comes to mind is that the prisoners, or most of them, are probably done for. The odds seem stacked against them. But there is almost always a clever way to save most of them, or sometimes even all of them, that is quite unexpected and elegant. Of course, there are some hat puzzles that have extremely sophisticated solutions or are still unsolved as the number of prisoners is increased. Some such puzzles are a subject of ongoing mathematical research and doctoral theses. One class of solutions for some hat puzzles is linked to error-correcting Hamming codes, which are used in data transmission. Don’t worry, none of our puzzles require anything more than high school mathematics, and in fact one of them is based on a puzzle invented by a ninth-grader. So do try your hand at them — and don’t give up too easily. The ideas behind them are quite clever and beautiful.

We have three such hat puzzles for you in this month’s Insights column. In order to modernize the theme, we are dispensing with the evil-tribes scenario and setting it instead in a modern reality-TV show where the hat-color guessers are game-show contestants, given their instructions by the host and competing for thousands of dollars.

The three hat puzzles below are arranged roughly in order of difficulty. In all these cases, the best strategy earns the contestants more than random guessing — sometimes quite a lot more. The first puzzle is a classic.

Puzzle 1: 2 Hats, 2 ColorsThere are only two contestants. They are given instructions by the host and allowed to confer before the game to come up with a strategy. At the start of the game, a hat that may be either blue or red is chosen at random from a large number of hats and placed on each contestant’s head. As is standard, each contestant can see the other’s hat but not her own. The host then sounds a buzzer, and each contestant must write the color of her hat on her own private tablet. If either of the contestants is correct, both of them win $1,000. If there are 10 rounds, what is the maximum amount of money the contestants can expect to make? Can you explain how the strategy works?

Puzzle 2: 10 Hats, 3 Colors, 1 BugThere are 10 contestants. As before, they are given instructions by the host and allowed to confer before the game. The room, however, is bugged, and the host can overhear this plan and adapt his hat-placement choices so as to counter any attempts to win big. The contestants know this but cannot do anything about it. During the game, the contestants are lined up single-file, and colored hats that are either blue, red or yellow are placed on each of their heads. As expected, each contestant can see the colors of the hats of everyone in front of her but does not know the color of her own hat or those of anyone behind. The host, starting from the back of the line, asks each contestant to state aloud the color of her hat. The contestants are not permitted to say anything other than a color (blue, red or yellow), and they can speak it only once. All contestants hear what each one says aloud. The host then goes to the next contestant and repeats the question, continuing until all contestants have spoken. At the end, if there are

xcorrect answers, a purse ofxtimes $10,000 is distributed equally among all players. Note that the host is trying his best to save money for the house. For example, if all the contestants decide to announce blue as their color, on the presumption that this could guarantee a third of the prize money, the host could simply put red hats on everyone. What strategy maximizes the amount that the contestants win? What is the expected amount?

Puzzle 3: 10 Hats, 3 Colors, Pass Allowed, Forfeiture on Wrong GuessAs in Puzzle 2, there are 10 contestants and hats of the same three colors, with the contestants lined up in a row, in formal Victorian garb as shown above. They have been allowed to confer before the game, but in this game there is no bug. The hat colors are chosen at random, and the contestants know this. This time the contestants are also allowed to say “pass” instead of guessing a color. As before, the questioning starts at the back of the line and proceeds to the front. If a single contestant guesses the wrong color, or all 10 contestants pass, the purse is forfeited and no one receives any money. If any one of the contestants guesses correctly, with no wrong guesses, the entire purse of $100,000 is distributed equally among all the players.

What strategy will maximize the probability that the contestants win? How often will that be?

That completes our hat trick, which, as you probably know, is a term used to signify three of anything in various sports. The term first appeared in 1858 in cricket, to describe a bowler (pitcher, in baseball parlance) who took three wickets (retired three batters) with three consecutive deliveries (pitches). Apparently, fans held a collection for the player, H. H. Stephenson, and presented him with a hat. We have come a long way from a winning a modest prize of a hat for the hat trick to winning a sum of hundreds of thousands of dollars! Unfortunately, we cannot match the fantasy game show of our puzzles — the only thing we can offer is a *Quanta* *Magazine* T-shirt. And the joy of puzzle-solving.

Happy puzzling — and may the insight be with you!

*Editor’s note: The reader who submits the most interesting, creative or insightful solution (as judged by the columnist) in the comments section will receive a *Quanta Magazine* T-shirt. ( Update: The solution is now available here.) And if you’d like to suggest a favorite puzzle for a future Insights column, submit it as a comment below, clearly marked “NEW PUZZLE SUGGESTION” (it will not appear online, so solutions to the puzzle above should be submitted separately).*

*Note that we will hold comments for the first day to allow for independent contributions.*

Here are my attempted solutions.

Puzzle 1: The contestants can expect to make $10,000.

Explanation: Let the two contestants be P and Q. They can write down the color of their hats in the following way: P writes down the color of Q's hat, and Q always writes down the color different from P's hat.

Since either they wear hats with same color or different colors, one of them must be correct and they will always win.

Puzzle 2: I would suggest the following strategy. The contestants need to remember the color sequence: Red, Blue, Yellow (R,B,Y), or you can use 0, 1, 2 if you like, so we can say R"+1" is B, B"+1" is Y, Y"+1" is R and so on (it is cyclic). They all know their positions, and the 1st, 4th and 7th contestants (counting from the back of the line, i.e. in the order of speaking) should answer in the following way: (For the ease of expression, let P be the next contestant and Q be the contestant in front of P)

1. If P's hat color is the same as Q's hat color, then answer "Red".

2. If P's hat color "+1" is Q's hat color (e.g. Blue and Red respectively), then answer "Blue".

3. If P's hat color "+2" (or "-1") is Q's hat color (e.g. Yellow and Red, or Red and Blue respectively), then answer "Yellow".

Note that P can see Q's hat color, so P can deduce his or her own hat's color. With P's answer, Q can also answer correctly.

Hence the 1st, 4th and 7th contestants provide sufficient information for the two contestants following them to answer, $60,000 is guaranteed. The 10th contestant can just guess randomly, to add $3,333 to the expected amount.

The host knows this strategy, so they cannot earn more and the expected total amount is $63,333.3333….

Puzzle 3: I would suggest the following strategy. (For the ease of expression, let the first contestant be P.)

1. Once someone has answered, always say "pass".

2. Assuming there are three hat colors in front of P, if there are more than three hat colors in front of you, always say "pass".

So if a contestant doesn't hear anyone before her anwsering, and there are only two hat colors in front of her, she can deduce the correct answer.

If there are only two hat colors in front of P, he or she can only guess randomly.

If there is only one hat color in front of P, P can say "pass". And the 2nd contestant can see only one color, so he knows that P didn't say "pass" because P sees three hat colors, and he can simply answer the hat color he sees.

The only cases they cannot win for sure is when P can only see two hat colors, with a probability [2^9 (the total number of combinations with nine contestants wearing at most two kinds of hats) – 2 (the cases with single color)] × 3 (R&B, R&Y, B&Y) ÷ 3^9 (no. of possible cases), which is about 0.077732053. But in those cases P still has 1/3 chance to answer correctly, so the probability of them NOT winning is about 0.051821369, and the chance of winning is about 0.948178631, or 94.8%.

1. Puzzle 1 has a simple strategy that guarantees a win for the players on every trial.

Strategy:

Contestant A writes the color of contestant B's hat.

Contestant B writes the opposite color of contestant A's hat.

Payoff:

In 10 trials, each contestant wins $10,000.

Analysis:

Suppose A's hat color is a. B's hat color is b.

A writes down b. B writes down a'.

Contestants win if either guess is correct.

i.e., a == b or a' == b

which is trivially true, since it says that b is red or blue, what else can it be!

2. Puzzles 2.

I guess that the best strategy for the contestants is for each contestant to randomly guess a color. Any other strategy with a better payoff can be thwarted by the eavesdropping host.

Expected winnings = 100,000/3 on each trial.

3. Puzzle 3.

Strategy:

1. If any contestant, on her turn, sees hats of only 2 colors in front, then she states the third color and everyone else passes.

2. If any contestant, except the contestant at the back of the line, sees hats of only 1 color in front, on her turn, then she states that color and everyone else passes.

3. If #1 and #2 are not true, then the contestant passes.

Payoff:

Contestants win each game with a probability of about 0.9998983895.

Analysis

If the contestant at the back of the line passes, then the players are guaranteed to win.

The players lose only if the contestant at the back of the line makes the guess and she guesses an incorrect color.

Whenever a player (except the player at the end of the line) is asked to make the guess, she knows that between her and the players in front, there are hats in 1 or 3 colors but not 2. If all players in front have 2 colors, then her hat color must be the third color. If all player in front have 1 color, then her hat color must be the same color.

If all players numbered 4 and above pass, then player #3 will make the winning guess, because one of the rules 1 or 2 will apply.

The contestants lose if the first 9 players have hats in 2 colors only and player 10 makes a wrong guess. The probability that the first 9 players have hats in 2 colors ~= probability that none of the 9 hats are yellow + probability that none of the 9 hats are red + probability that none of the 9 hats are blue = (1/3)^9 + (1/3)^9 + (1/3)^9 = 0.000152416. The probability of making an incorrect guess is 2/3, hence the probability of failure = 0.0001016105.

Addendum for puzzle #2.

Strategy 1: Each player guesses randomly. Payout = 3.333 * 10000 per trial. Host cannot do anything to reduce the payout.

Strategy 2: Even numbered players state the color of the hat in front of them. Odd numbered players repeat what the previous player said.

There will be 5 correct answers, the answers for even numbered players will be incorrect, thanks to the host. Payout = 5 * 10000 per trial. Host cannot do anything to reduce the payout.

One could loosely argue that the players cannot do better than strategy 2. In any non-random strategy, there will be N players that provide information, and M players that use the information to correctly guess the color. Each guesser needs 1.5 bits of info, each provider provides 1.5 bits of info. N has to be >= M.

* 2 hats, 2 colors

| | rr | rb | br | bb |

|—-+—-+—-+—-+—-|

| rr | ✓ | ✓ | ✓ | ❌ |

| rb | ✓ | ✓ | ❌ | ✓ |

| br | ✓ | ❌ | ✓ | ✓ |

| bb | ❌ | ✓ | ✓ | ✓ |

| rr | ✓ | ✓ | ✓ | ❌ |

| rb | ✓ | ✓ | ❌ | ✓ |

| br | ✓ | ❌ | ✓ | ✓ |

| bb | ❌ | ✓ | ✓ | ✓ |

| rr | ✓ | ✓ | ✓ | ❌ |

| rb | ✓ | ✓ | ❌ | ✓ |

|—-+—-+—-+—-+—-|

| | 8 | 8 | 7 | 7 |

Expected value = 7.5 * $1,000 = $7,500

This works because the players tie the result to the truth-table of "or", which is true for 3 out of 4 possible inputs.

* 10 hats, 3 colors, 1 bug

This scenario can be generalized to any number of colors and any number of hats greater than 1.

If there is 1 hat, its wearer's optimal strategy is to guess at random (so that the host can't outmaneuver the guess), which succeeds with 1/n chance (where n is the number of colors).

For any other scenario, the contestants can guarantee that all but 1 guess will succeed. Proceed as follows: assign each color a number 0 through n-1; the first player to guess adds up all the hats they see modulo n and calls that color; the next player now knows the color of their hat, since they can add up all the hats they see and subtract that from the color they just heard; each subsequent player can follow this approach to guess their own color.

The host can, at best, cause the first player's guess to be wrong, leading to a guaranteed $9,000 for each player.

* 10 Hats, 3 Colors, Pass Allowed, Forfeiture on Wrong Guess

As far as I can tell, the best strategy is, "Pass if you see red or if someone has guessed; guess red otherwise" (or equivalently for another color). If and only if any of the hats is red, they win. Here's how: if none of the hats is red, they can't win, since they will only guess red; otherwise, the first (in guessing order) contestant who doesn't see red will guess red; they must be wearing red because by assumption at least one hat is red, and by the strategy, the contestant behind them would only have passed if they saw red.

This strategy wins with 1 – (2/3)^10 probability, a 98% chance.

Don't think I have seen Puzzle 3 before, so thanks for that.

Believe the team can achieve 1 – (2/3)^10 ~ 98.268% winning probability. The strategy is to fix one particular color when they confer, e.g., blue. During the game, each participant would say "pass" if she/he sees at least one blue hat or someone has already guessed a color, and say "blue" if she/he doesn't see any blue hat.

Note (1) once someone guesses "blue", the game effectively ends and there is no gain for the contestants in front to make a guess; (2) For the contestant all the way in front, who by definition sees nothing, so she would need to say "blue" if everyone behind her all have said "pass".

Here is a brief argument of the optimality: the hat colors are chosen at random, so there are total 3^10 distinct configurations. Consider again the contestant all the way in front, the one and only one piece of info she has is 9 passes, so the best she can achieve is to get one correct color, which covers at most 1/3 of the total configurations which is 3^9 (i.e., her hat is indeed of that color, no matter what other contestants wear); now go backward and consider the 2nd contestant, again for the remaining 2 * 3^9 configurations, at best she could get 1/3 of the configurations correct, which is 2 * 3^8; carrying the argument till the end of line, one ends up with an upper bound of the probability: (3^9 + 2 * 3^8 + 2^2 * 3^7 + … + 2^9) / 3^10, which is 1 – (2/3)^10 and we already have constructed a strategy that achieves it.

The first two puzzles are relatively common and in some way are both related to parity:

Puzzle 1: one contestant guesses the same color as what she sees and the other contestant guesses the opposite color of what she sees, which gives 100% winning probability thus 2 * $1000 * 100 = $200k total winning;

Puzzle 2: checksum (mod 3)

e.g., replace red = 0, blue = 1 and yellow = 2, due to the bugged room, last contestant would guess wrong for sure, but she would be able to convey the sum of all colors she sees (mod 3). then all the contestants in front would be able to guess correctly one by one, by simply subtracting the sum of all colors she sees, thus 9 * $10000 = $90k total winning.

My analysis of the solution to puzzle #3 was incorrect.

The probability that the first 9 players have hats in 2 colors ~= probability that none of the 9 hats are yellow + probability that none of the 9 hats are red + probability that none of the 9 hats are blue = (2/3)^9 + (2/3)^9 + (2/3)^9 = 0.078036885. (We need to subtract the probability of all hats being of the same color, but that makes a very minor difference.) The probability of making an incorrect guess is 2/3, hence the probability of failure = 0.05202459. Probability of success is 0.94797541.

The solution provided by Alex and Wiley is obviously superior.

.

It is interesting that kayue and I developed the same solution to puzzle 3, which has a lower probability of success than the solution by Alex and Wiley.

But if we were to change the payout rule, so that the reward is higher if a person towards the back of the line answers first, then the average payout values change.

Let's assume that the payout is $10 if the 10th person in the line (the person at the back of the line) provides the right answer, $9 if the 9th person in the line provides the right answer and so on, the average payout in the Alex and Wiley solution is 2.774560 and the average payout in the kayue and Anil solution 4.825636. (I used a simple simulation to compute the values).

#1

They can expect to win $10,000.

I will write down the color of the hat I see.

If the colors are the same, we win.

The other person will write down the color they don't see.

If the colors are different, we win.

That's it. We win.

#2

They can expect to win $70,000.

7 people are expected to win.

The colors can be used as codes. You have three colors, so 3 codes.

The First, Fourth and Seventh person will speak a code allowing the rest of the people to say the correct colors.

Blue means the two hats in front are the same color.

Since the person in front of the speaker can see the next hat, then he knows his color

The next person, hearing the one behind, then knows his color

Red means the two hats differ in color by one in alphabetical sequence (Blue–>Red–>Yellow–>Blue–>Red–>etc)

Since the person in front of the speaker can see the next hat, then he knows his color by going back one in the sequence.

The next person, upon hearing the person behind, goes forward one in the sequence.

Yellow means the two hats differ in color by one in reverse alphabetical sequence.

Since the person in front of the speaker can see the next hat, then he knows his color by going forward one in the sequence.

The next person, upon hearing the person behind, goes back one in the sequence.

Author's updateHere’s a new variation of Puzzle 3

Puzzle 4The game is played the same way as in puzzle 3, but the purse is multiplied by the number of correct guesses. So if 4 people guess correctly, the total purse is $400,000. A single wrong guess still forfeits as before.How can the players maximize the average expectation per game, and how much will it be?

I think it should be possible (with a little work) to calculate this manually using a table or spreadsheet, without having to write a program or simulation.

@Anil,

I agree that the method described by you and kayue has a nice symmetry among the colors. Your suggested payout is interesting and reflects this. Try out its natural extension in the above variation!

Best solution for puzzle 4 that I found is to use a variation of the check-sum trick that works in problem 3, as follows. Players are numbered from the first player to speak, who sees all the remaining hats, to the 10th player to speak.

Players 1-3 pass if the sum of players 4-10 is 0 mod 3. Otherwise, players 1-2 pass if the sum of players 3-10 is 0 mod 3. Otherwise, player 1 passes if the sum of 2-10 is 0 mod 3. Otherwise, player 1 encodes the sum of players 2-10, and takes a 1/3 chance of losing everything. The expected payoff is about $643000.

Ben’s solution to puzzle #4 looks optimal. The modulo-sum technique seems appropriate for this problem.

The description has a few details missing, but they can be filled in by the astute reader.

The payout, using simulation, comes out to 633,333.

Other variations of Ben’ solution give lower payouts – using fewer than 3 or more than 3 players at the end of line for the special rules.

A simple extension of the kayue and Anil solution to puzzle #3 gives a payout of 234,578 only. Maybe, there is a better extension …

Thanks, Anil.

There is a typo in my post above – "1/3 chance of losing everything" should be "2/3…".

The calculation for expected value is

(1/3)7 + (2/3)(1/3)8 + (2/3)^2(1/3)9 + (2/3)^3(1/3)10.

Ben – your expression for the expected value is of course correct and elegant. The payout is indeed 643,210. There was a small error in my simulation.

@Ben,

Brilliant solution to Puzzle 4, congratulations!

It is interesting to see the modulo-3 checksum method of puzzle 2 becoming superior to the conservative low risk method of puzzle 3, in spite of the relatively higher risk of forfeiting.

@Anil,

It seems to me that the payoff for an extension of your technique should be higher. Whenever there are 3 colors (>94% of the time), there should be at least 3 correct guesses (on the last occurrence of each color), plus extra correct guesses whenever the last color is repeated at the end of the sequence. I suspect that the average number of correct guesses should be 4 or more.

So it could still be a viable option for players who don't mind taking home a little less (I'm guessing maybe 35-40K per player), but with a very much lower probability of going home empty handed compared to the checksum method which has almost a 20% chance of forfeit.

It is interesting that Ben's solution can be applied to the original puzzle #3.

Player #1 at the back of the line passes if at least one of the sums for players 2-10, 3-10, 4-10, …, 10-10 is zero. Otherwise she makes a guess. Players 2-10 use similar logic to pass, else they compute and state a correct color assuming that the sum of all colors in front of her and including her color is zero. Once a player states a color, all other players pass. Note that player #1 is the one at the back of the line.

Probability of success = 1 – (2/3)^9 * 2 / 3 = 0.98265847, which is the same as that for the solution by Alex and Wiley.

@Pradeep

Of course you are right, there was an error in my calculation. It did not account for the fact that the guess by the player at the front of the line is always correct, assuming the player at the back of the line did not make an incorrect guess.

With that correction, the payoff increases by ~100,000 to to 329,396, not quite 400,000 and far from the payout by Ben's solution.

Anil – Nice observation about extending my strategy to handle puzzle 3.

I think there is a common generalization of problem 3,4, and the observation offered by Pradeep that players might prefer a higher chance of getting something, even if it reduces the overall expectation.

Take the setup of problem 3. The "hat value" of a particular strategy on a particular sequence of hats is the number of people who guess their own hat; if any person guesses the wrong hat color, the "hat value" is 0.

The players have a utility function that assigns a utility to each hat value – we assume that the players never prefer a lower hat value to a higher one. In problem 3, the utility function assigns 1 (or $100k) to hat values 1 or more, and $0 to hat value 0. In problem 4, the utility function assigns utility k to hat value k. If the contestants follow Pradeep's advice, and would give up some expected winnings in exchange for an increased probability of winning, the utility function might be strictly concave (i.e., increases quickly for low hat values, and more slowly for higher hat values). We could also imagine a case where the players have to get a hat value of 10 to get any payoff at all.

Consider the natural generalization of the strategy I proposed for problem 4 as follows; S_k is the first j<=k players pass if the last 10-j players sum to 0 mod 3 (priority given to the largest such j). So, the strategy I proposed for problem 4 is S_3, Anil's solution to problem 3 is S_9, and the solution to the all-or-nothing situation where the players need to get all of the hats right to obtain any reward is S_0.

I believe that one of these strategies – S_0 to S_9 – is always an optimal solution to this hat game, no matter what (monotonically increasing) utility function used. I won't give a full proof, but a brief sketch of one.

First, note that, if anyone makes a wrong guess, it might as well be the first player. Second, we assume that the only reasonable sequence of guesses is a number of passes, followed by a sequence of colors (guaranteed to be correct, unless the first player guesses a color). Note that the probability that there are exactly k passes can be at most 1/3, since otherwise there is no way for player k+1 to know for sure what his color is. Suppose that S_k is optimal among all strategies such that the last 10-k players always say a color. Let T be a strategy such that the last 9-k players always say a color. As noted above, the probability that the first k players all pass in T is bounded above by 1/3. Hence the total utility of T is bounded by (2/3)U(S_k) + (1/3)U(9-k), where U(S_k) is the utility of an optimal strategy where the last 10-k players say colors, and U(10-k) is the utility of hat value 9-k. This is the same as the utility of S_{k+1}, which establishes the inductive step of the proof. The base case (i.e. S_0 is optimal among strategies where everyone says a color) is easy, since either the first player is wrong, or everyone is right.

In problem 4, this finds a maximum at S(3), because U(7) = $700k > U(S_2), but U(6) = $600k < U(S_3) = $643k. We can similarly find an optimal strategy (among S_0, …, S_9) for any given utility function.

For puzzle 2, I think the following strategy can ensure at least $60,000 is paid each time.

Arrange the colours on a clockface, blue at 12, red at 4 and yellow at 8.

Assign a signal as blue for the same, red for clockwise, yellow for anticlockwise.

The first player can signal the second player that his colour is either the same, anticlockwise or clockwise from the third players colour. The third player can infer what colour he has based on the colour the second player says and whether that colour is the same or clockwise or anticlockwise from his own colour ( based on the first players signal).

The 4th player signals for the 5th and 6th players. The 7th player signals for the 8th player and 9th player. The 10th player just has to guess.

As written, puzzle 1 describes each round as pertaining to one hat only, placed on each of two people's heads (presumably in turn). Since each contestant can see the hat when the other contestant's wearing it, each contestant can tell exactly the colour of the one hat in use at each round. $10,000

Puzzle 1: 100% winnings

One of you always 'guesses' that you have the same color hats, the other always 'guesses' that you have different color hats: one of you (and only one) must be correct. In the youtube, they alternate which person 'guesses' which way, to obfuscate it.

Puzzle 2: (n-1)/n winnings (=90% for 10 players)

Modulo arithmetic is the key. Decide on a value for each color(red = 0, blue = 1, yellow = 2)

The back player adds up all the hats he can see, modulo 3, and announces that number/color. Then the next player adds up the hats he/she can see, but instead, announces the color needed to make the sum what the guy behind him announced, as that must be the missing part. Each subsequent player performs similar calculations.

Puzzle 3/4: (n-1) correct answers (90% for 10 players = $900,000)

Decide on a value for each color(red = 2, blue = 4, yellow = 6) Each player keeps a silent count of seconds. Each player waits to answer the question until the number of seconds corresponding to the next player's hat have passed. The first player must announce "Pass".

Puzzle #3 contains a loophole that allows the contestants to win $100,000 100% of the time.

Strategy:

Contestants agree that the word "pass" should be spoken with different inflections / characteristics to encode in that response the color of the last contestant's. For example, a yelled "pass" means that the last contestant is wearing a blue hat; whispered "pass" means red; normal spoken "pass" means yellow.

Each player then passes in sequence while indicating which hat the last contestant is wearing. That last contestant then declares the color of his/her hat.

The loophole could be closed by requiring each contestant to click a button, unseen by others, that displays that contestant's choice (pass or a color) on a board visible to all, the display of which shows responses at a fixed interval rather than in real time.

That takes some of the fun out of the question, but rules are rules.

I tried working out the general case of puzzle 4:

(general case of puzzle 3 is rather simple: 1-[(m-1)/m]^n)

For n players with m colors (n,m>=1), with Ben's strategy S_k, i.e., the last n-k players would always guess while the first k players would either pass or make a guess based on what she sees (0<=k<=n-1), the average payoff is:

n+m-1-[(n+m)(1-1/m)^(k+1)+k]

units, where one unit is the total prize in puzzle 3. Minimize the term within the square brackets with respect to k, the optimal k is either floor(x) or ceiling(x), where x=min(n-1, log[(n+m)*y]/y-1) and y=log(m)-log(m-1).

Understand this is a puzzle column, so the actual proof is likely not a necessity, but as Ben commented above, the two crucial steps are

(1) it suffices to consider strategies for which except the first player, any guess made by other players has to be correct;

(2) find the optimal strategy within this restricted set.

Without loss of generality, we can consider deterministic strategies only. For (1), the key is that the payoff is zero once a guess is wrong. By reductio ad absurdum, since the first player to guess can see every hat in front of her and knows the exact configurations that would lead to a wrong guess later, she could take the chance in these cases and make a guess while improving the payoff; For (2), fix m and use induction on n by considering the following cases (a) first player guesses; (b) first player passes and second player guesses correctly; (c) both passes.