## 538 hats riddle

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

Eebster the Great
Posts: 3407
Joined: Mon Nov 10, 2008 12:58 am UTC
Location: Cleveland, Ohio

### 538 hats riddle

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:

fivethirtyeight wrote: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
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

### Re: 538 hats riddle

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
Posts: 29
Joined: Thu Mar 20, 2008 12:14 pm UTC

### Re: 538 hats riddle

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
Posts: 3407
Joined: Mon Nov 10, 2008 12:58 am UTC
Location: Cleveland, Ohio

### Re: 538 hats riddle

jaap wrote: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
¡This cheese is burning me!
Posts: 176
Joined: Sun Mar 02, 2008 6:23 pm UTC

### Re: 538 hats riddle

I had the same confusion about this riddle. Thanks, Eebster, for asking that question and thanks, jaap and cjr22 for answering
Pronouns: he him his
Avatar: The High Frontier by Angus McKie

SirGabriel
Posts: 42
Joined: Wed Jul 16, 2014 11:54 pm UTC

### Re: 538 hats riddle

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
¡This cheese is burning me!
Posts: 176
Joined: Sun Mar 02, 2008 6:23 pm UTC

### Re: 538 hats riddle

SirGabriel wrote: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.
Pronouns: he him his
Avatar: The High Frontier by Angus McKie

SirGabriel
Posts: 42
Joined: Wed Jul 16, 2014 11:54 pm UTC

### Re: 538 hats riddle

plytho wrote:
SirGabriel wrote: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
Posts: 42
Joined: Wed Jul 16, 2014 11:54 pm UTC

### Re: 538 hats riddle

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
Posts: 43
Joined: Fri Sep 02, 2011 11:20 am UTC
Location: CT, USA

### Re: 538 hats riddle

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
Posts: 127
Joined: Sat Apr 04, 2015 4:31 pm UTC
Location: Time-traveling kayak

### Re: 538 hats riddle

nicklikesfire wrote:
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
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

### Re: 538 hats riddle

measure wrote:
nicklikesfire wrote:
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
Posts: 131
Joined: Tue Feb 03, 2009 2:05 pm UTC

### Re: 538 hats riddle

measure wrote: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
Posts: 215
Joined: Wed May 04, 2011 9:16 am UTC
Location: New Zealand

### Re: 538 hats riddle

jaap wrote: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
Posts: 431
Joined: Fri Mar 30, 2012 5:48 pm UTC
Contact:

### Re: 538 hats riddle

Yat wrote:
measure wrote: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.

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

The original post by fivethirtyeight wrote:Extra credit: What if instead of seven of you there are 2N−1?
If it looks like a duck, and quacks like a duck, we have at least to consider the possibility that we have a small aquatic bird of the family Anatidae on our hands. –Douglas Adams

patzer
Posts: 431
Joined: Fri Mar 30, 2012 5:48 pm UTC
Contact:

### Re: 538 hats riddle

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.
If it looks like a duck, and quacks like a duck, we have at least to consider the possibility that we have a small aquatic bird of the family Anatidae on our hands. –Douglas Adams

Eebster the Great
Posts: 3407
Joined: Mon Nov 10, 2008 12:58 am UTC
Location: Cleveland, Ohio

### Re: 538 hats riddle

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 2N-1 case by following an identical strategy, assigning numbers from 1 to N, and yielding a (2N-1)/2N probability of winning.

nicklikesfire
Posts: 43
Joined: Fri Sep 02, 2011 11:20 am UTC
Location: CT, USA

### Re: 538 hats riddle

Eebster the Great wrote: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 2N-1 case by following an identical strategy, assigning numbers from 1 to N, and yielding a (2N-1)/2N probability of winning.

That is super clever.

Eebster the Great
Posts: 3407
Joined: Mon Nov 10, 2008 12:58 am UTC
Location: Cleveland, Ohio

### Re: 538 hats riddle

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

Demki
Posts: 199
Joined: Fri Nov 30, 2012 9:29 pm UTC

### Re: 538 hats riddle

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[]
Posts: 156
Joined: Mon May 18, 2009 6:11 pm UTC
Location: Stockholm, Sweden

### Re: 538 hats riddle

Demki wrote: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.)

### Who is online

Users browsing this forum: Google Feedfetcher and 10 guests