538 hats riddle

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

User avatar
Eebster the Great
Posts: 2691
Joined: Mon Nov 10, 2008 12:58 am UTC

538 hats riddle

Postby Eebster the Great » Mon Sep 04, 2017 1:54 pm UTC

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?

User avatar
jaap
Posts: 2068
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: 538 hats riddle

Postby jaap » Mon Sep 04, 2017 3:14 pm UTC

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

Postby cjr22 » Mon Sep 04, 2017 3:20 pm UTC

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.

User avatar
Eebster the Great
Posts: 2691
Joined: Mon Nov 10, 2008 12:58 am UTC

Re: 538 hats riddle

Postby Eebster the Great » Mon Sep 04, 2017 3:35 pm UTC

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.

User avatar
plytho
¡This cheese is burning me!
Posts: 125
Joined: Sun Mar 02, 2008 6:23 pm UTC

Re: 538 hats riddle

Postby plytho » Mon Sep 04, 2017 3:41 pm UTC

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

User avatar
SirGabriel
Posts: 40
Joined: Wed Jul 16, 2014 11:54 pm UTC

Re: 538 hats riddle

Postby SirGabriel » Mon Sep 04, 2017 4:43 pm UTC

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).

User avatar
plytho
¡This cheese is burning me!
Posts: 125
Joined: Sun Mar 02, 2008 6:23 pm UTC

Re: 538 hats riddle

Postby plytho » Mon Sep 04, 2017 4:46 pm UTC

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.
he him his

User avatar
SirGabriel
Posts: 40
Joined: Wed Jul 16, 2014 11:54 pm UTC

Re: 538 hats riddle

Postby SirGabriel » Mon Sep 04, 2017 5:11 pm UTC

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.

User avatar
SirGabriel
Posts: 40
Joined: Wed Jul 16, 2014 11:54 pm UTC

Re: 538 hats riddle

Postby SirGabriel » Mon Sep 04, 2017 5:27 pm UTC

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

Re: 538 hats riddle

Postby nicklikesfire » Tue Sep 05, 2017 8:09 pm UTC

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

User avatar
measure
Posts: 97
Joined: Sat Apr 04, 2015 4:31 pm UTC
Location: Time-traveling kayak

Re: 538 hats riddle

Postby measure » Tue Sep 05, 2017 9:24 pm UTC

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.

User avatar
jaap
Posts: 2068
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: 538 hats riddle

Postby jaap » Wed Sep 06, 2017 5:55 am UTC

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: 120
Joined: Tue Feb 03, 2009 2:05 pm UTC

Re: 538 hats riddle

Postby Yat » Wed Sep 06, 2017 8:20 am UTC

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.

User avatar
Bloopy
Posts: 164
Joined: Wed May 04, 2011 9:16 am UTC
Location: New Zealand

Re: 538 hats riddle

Postby Bloopy » Fri Sep 08, 2017 6:21 am UTC

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.

User avatar
patzer
Posts: 407
Joined: Fri Mar 30, 2012 5:48 pm UTC
Contact:

Re: 538 hats riddle

Postby patzer » Fri Sep 08, 2017 2:41 pm UTC

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

User avatar
patzer
Posts: 407
Joined: Fri Mar 30, 2012 5:48 pm UTC
Contact:

Re: 538 hats riddle

Postby patzer » Fri Sep 08, 2017 3:18 pm UTC

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

User avatar
Eebster the Great
Posts: 2691
Joined: Mon Nov 10, 2008 12:58 am UTC

Re: 538 hats riddle

Postby Eebster the Great » Fri Sep 08, 2017 7:58 pm UTC

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

Re: 538 hats riddle

Postby nicklikesfire » Tue Sep 12, 2017 5:44 pm UTC

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.

User avatar
Eebster the Great
Posts: 2691
Joined: Mon Nov 10, 2008 12:58 am UTC

Re: 538 hats riddle

Postby Eebster the Great » Tue Sep 12, 2017 9:37 pm UTC

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

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

Re: 538 hats riddle

Postby Demki » Tue Sep 12, 2017 10:21 pm UTC

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

Re: 538 hats riddle

Postby operator[] » Wed Sep 13, 2017 11:02 am UTC

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.)


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 5 guests