538 hats riddle

[Eebster the Great]

This week's Riddler Classic on 538 confuses me. To be clear, I have no intention of submitting an answer to the site, I just want to know what I am missing. The question is copied below:

You and six friends are on a hit game show that works as follows: Each of you is randomly given a hat to wear that is either black or white. Each of you can see the colors of the hats that your friends are wearing but cannot see your own hat. Each of you has a decision to make. You can either attempt to guess your own hat color or pass. If at least one of you guesses correctly and none of you guess incorrectly then you win a fabulous, all-expenses-paid trip to see the next eclipse. If anyone guesses incorrectly or everyone passes, you all lose. No communication is possible during the game — you make your guesses or passes in separate soundproof rooms — but you are allowed to confer beforehand to develop a strategy.

What is your best strategy? What are your chances of winning?

Extra credit: What if instead of seven of you there are 2N−1?

It seems sort of obvious that no strategy can beat assigning one person to guess arbitrarily and the rest to pass, giving a 0.5 probability of winning. After all, if hats are assigned randomly and no communication is allowed, it is impossible to get any information about your own hat whatsoever. If more than one person guesses, the odds get strictly worse. What am I missing?

I've seen problems similar to this before, but generally there is *some* sort of communication involved, like allowing one player's decision to be known to other players. But here, there is *nothing*. How can seeing other hats be useful if they are all random?

[jaap]

It is not stated clearly in the question, but I assume that each hat's colour is chosen independently, 50:50 either colour.

What you say is true if you make a fixed choice beforehand about who is going make a guess. However, you don't have to do that.

For example, consider the smaller version of the game with only 3 people (i.e. you and two friends). You can then decide on the rule "If you see two hats of the same colour, say the other colour". In that case you would win whenever both colours are present, i.e. with probability 6/8. Only one of the three of you would make a guess, and it depends on the hat colours who it is going to be.

[cjr22]

The key to solving this one is to see what's different from the usual type of hats question when some form of communication is ok.

Here, the important thing is that ONLY ONE person needs to guess right to win, as long as everyone else passes. You're right that each individual person, when they choose to make a guess, will be right 50% of the time. So what can you do?

I think it's a bit mean that they've specified 7 people. You can get the perceptual leap with just 3 people, but the actual solution is much harder with 7.

This is the key insight:

Spoiler:

You need to arrange it so that everyone guesses wrongly at the same time, but that when someone guesses correctly, they're the only one not to pass.

Solution for 3 people:

Spoiler:

If you see two hats the same colour, guess the opposite. Otherwise pass.

[Eebster the Great]

It is not stated clearly in the question, but I assume that each hat's colour is chosen independently, 50:50 either colour.

What you say is true if you make a fixed choice beforehand about who is going make a guess. However, you don't have to do that.

For example, consider the smaller version of the game with only 3 people (i.e. you and two friends). You can then decide on the rule "If you see two hats of the same colour, say the other colour". In that case you would win whenever both colours are present, i.e. with probability 6/8. Only one of the three of you would make a guess, and it depends on the hat colours who it is going to be.

Ah, I see now. No matter what, whenever I guess (even using your strategy), I have a 50/50 chance of being right. However, in cases where I am wrong, everyone guesses wrong, while in cases where I am right, I am the only one who guessed. Therefore if we played repeatedly, I would guess right 1/4 of the time (and win), guess wrong 1/4 of the time (and lose), and pass half the time (and win), giving me and the group a 3/4 chance to win.

It makes sense but is very unintuitive. Scaling up to 7 does indeed seem like a serious challenge, but I'm happy that it at least seems possible now.

[plytho]

I had the same confusion about this riddle. Thanks, Eebster, for asking that question and thanks, jaap and cjr22 for answering

[SirGabriel]

I think I have the optimal solution:

Spoiler:

Assign each person a number, from 1 to 7. When it's time to guess, everyone guesses in order based on their number.

When it's your turn to guess:
1. If someone has already made a guess rather than passing, pass.
2. If everyone before you has passed, and at least one person with a higher number than you has a black hat, pass.
3. If everyone before you has passed, and no one with a higher number than you has a black hat, guess that your hat is black.

This strategy only falls when no one has a black hat (1/128 chance).

[plytho]

I think I have the optimal solution:

Spoiler:

Assign each person a number, from 1 to 7. When it's time to guess, everyone guesses in order based on their number.

When it's your turn to guess:
1. If someone has already made a guess rather than passing, pass.
2. If everyone before you has passed, and at least one person with a higher number than you has a black hat, pass.
3. If everyone before you has passed, and no one with a higher number than you has a black hat, guess that your hat is black.

This strategy only falls when no one has a black hat (1/128 chance).

Spoiler:

This does not work because participants don't know what the others said.

[SirGabriel]

I think I have the optimal solution:

Spoiler:

Assign each person a number, from 1 to 7. When it's time to guess, everyone guesses in order based on their number.

When it's your turn to guess:
1. If someone has already made a guess rather than passing, pass.
2. If everyone before you has passed, and at least one person with a higher number than you has a black hat, pass.
3. If everyone before you has passed, and no one with a higher number than you has a black hat, guess that your hat is black.

This strategy only falls when no one has a black hat (1/128 chance).

Spoiler:

This does not work because participants don't know what the others said.

Thanks, I somehow missed that part.

[SirGabriel]

In that case, I suspect the best solution is

Spoiler:

Three of the people ignore the other four and use the 3-person strategy shown above, and the other four pass, for a 3/4 chance of success.

[nicklikesfire]

Spoiler:

With 7 people you can use two rules.

Rule one - If you see four people with the same color, then you must guess that you have the opposite color.
Win - 70/128
Lose - 42/128

Rule two - If you see six people with the same color, then you must guess that you have the opposite color
Win - 14/128
Lose - 2/48

Total wins - 84/128
Total losses - 44/128

[measure]

Spoiler:

With 7 people you can use two rules.

Rule one - If you see four people with the same color, then you must guess that you have the opposite color.
Win - 70/128
Lose - 42/128

Rule two - If you see six people with the same color, then you must guess that you have the opposite color
Win - 14/128
Lose - 2/48

Total wins - 84/128
Total losses - 44/128

It may be possible to do better with two rules than SirGabriel has with one, but your posted win rate is less than his.

[jaap]

Spoiler:

With 7 people you can use two rules.

Rule one - If you see four people with the same color, then you must guess that you have the opposite color.
Win - 70/128
Lose - 42/128

Rule two - If you see six people with the same color, then you must guess that you have the opposite color
Win - 14/128
Lose - 2/48

Total wins - 84/128
Total losses - 44/128

It may be possible to do better with two rules than SirGabriel has with one, but your posted win rate is less than his.

SirGabriel's answer assumes that you see who is wearing each hat. nicklikesfire's solution works with just the hat colours regardless of who is wearing them. The puzzle statement fails to specify this one way or the other. It is rather imprecisely worded, as it also failed to specify that the hat colours were chosen uniformly and independently.

[Yat]

It may be possible to do better with two rules than SirGabriel has with one, but your posted win rate is less than his.

To keep the thread alive, I think it is relevant to confirm that it is indeed possible to do better than SirGabriel, under the assumptions pointed out by jaap.

Spoiler:

For any number of prisoners 2^n-1, it is possible to maximize the outcome perfectly, just like in the 3 prisoners situation.

[Bloopy]

SirGabriel's answer assumes that you see who is wearing each hat.

No communication rules out the possibility of seeing their faces. However, the puzzle neglects to mention anything that would prevent you from identifying the chosen 3 by height. Or alternatively by their position in the studio relative to the compass or a particular wall if you're able to study it in advance.

[patzer]

It may be possible to do better with two rules than SirGabriel has with one, but your posted win rate is less than his.

To keep the thread alive, I think it is relevant to confirm that it is indeed possible to do better than SirGabriel, under the assumptions pointed out by jaap.

Spoiler:

For any number of prisoners 2^n-1, it is possible to maximize the outcome perfectly, just like in the 3 prisoners situation.

I was a bit confused by your spoiler, so I had a look at the original fivethirtyeight article and found out that Eebster's opening post contains an unfortunate typo in the quote.

Extra credit: What if instead of seven of you there are 2N−1?

Extra credit: What if instead of seven of you there are 2^N−1?

[patzer]

I thought I'd found a good solution:

Spoiler:

A: if B and C have the same color hat, and exactly two of D, E, F, and G are black, then guess that you have the opposite color to B and C. Else pass.
B: if A and C have the same color hat, and exactly two of D, E, F, and G are black, then guess that you have the opposite color to A and C. Else pass.
C: if A and B have the same color hat, and exactly two of D, E, F, and G are black, then guess that you have the opposite color to B and C. Else pass.
D: if exactly two of A, B, and C are black, and exactly two of E, F, and G are black, then guess that you are white. if exactly two of A, B, and C are white, and exactly two of E, F, and G are white, then guess that you are black. Else pass.
E: if F and G have the same color hat, and exactly two of A, B, C, and D are black, then guess that you have the opposite color to F and G. Else pass.
F: if E and G have the same color hat, and exactly two of A, B, C, and D are black, then guess that you have the opposite color to E and G. Else pass.
G: if E and F have the same color hat, and exactly two of A, B, C, and D are black, then guess that you have the opposite color to E and F. Else pass.

But a quick calculation makes me think the chances of this strategy succeeding are 90/128, so less than Gabriel's solution.
I think my solution could maybe be twerked for improvement, though.

[Eebster the Great]

The solution has been posted here.

Spoiler:

While strategizing, the players agree on an assignment so each player is given a unique number between 1 and 7. While playing, each player bitwise XORs the numbers of all other players wearing black hats. If the result is 0, that player guesses "black;" if the result is that player's number, that player guesses "white;" if the result is anything else, that player passes.

The result is that, in every case, either exactly one player guesses and is correct (which happens 7/8 of the time), or all players guess and are wrong (which happens 1/8 of the time). This generalizes to the 2^N-1 case by following an identical strategy, assigning numbers from 1 to N, and yielding a (2^N-1)/2^N probability of winning.

[nicklikesfire]

The solution has been posted here.

Spoiler:

While strategizing, the players agree on an assignment so each player is given a unique number between 1 and 7. While playing, each player bitwise XORs the numbers of all other players wearing black hats. If the result is 0, that player guesses "black;" if the result is that player's number, that player guesses "white;" if the result is anything else, that player passes.

The result is that, in every case, either exactly one player guesses and is correct (which happens 7/8 of the time), or all players guess and are wrong (which happens 1/8 of the time). This generalizes to the 2^N-1 case by following an identical strategy, assigning numbers from 1 to N, and yielding a (2^N-1)/2^N probability of winning.

That is super clever.

[Eebster the Great]

I was pretty impressed by it. Apparently it is related to Hamming distance, which I can sort of understand.

[Demki]

That solution reminds me of another riddle, where each of n participants is given a hat with a random color out one of n different colors(and what color one person gets is independent of what the rest get) and they need to form a strategy such that at least one of them must guess their own color correctly, but the catch is that they are unable to communicate at all once the hats are given(they do see each other), and they don't know what other people have guessed.(say, they are all in the same room when getting the hats, but are then sent to separate rooms to make the guesses)
They are able to form a strategy ahead of time, and any number of them may guess wrong so long as at least one guesses correctly.

The main difference here is that this riddle has a solution that guarantees someone guesses correctly, and that they only lose if everyone guesses wrong.

Also everyone has perfect color vision(much unlike myself T_T)

[operator[]]

Also everyone has perfect color vision(much unlike myself T_T)

We had two very nice variations a while back where they didn't: see viewtopic.php?p=3811937#p3374392 and the post following it.

(Also, I just posted viewtopic.php?f=3&t=123441 with another somewhat difficult hat puzzle variation.)