## Hat puzzle - 6 (or n) randomly coloured hats in a circle.

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

dudiobugtron
Posts: 1098
Joined: Mon Jul 30, 2012 9:14 am UTC
Location: The Outlier

### Hat puzzle - 6 (or n) randomly coloured hats in a circle.

Everyone loves hat puzzles, and this one is my favourite, so I thought I share it. (I don't take credit for the original puzzle, but the embellishment is mine):

There are 6 ex-prisoners who have recently escaped from a hat-puzzle-prison by beating the warden at his own game. While enjoying their new-found freedom, they happen upon a travelling milliner who has a big sign on his cart - "6 hats for the price of 1 if you can solve my hat puzzle!"
To the ex-prisoners, this sort of puzzle is 'old hat', so they jump at the chance, and rush to the milliner to take advantage of the deal.

Before they get a chance to introduce themselves, the milliner hails them in a booming voice: "Welcome, welcome. I can see you ladies have fine taste in hats - and you appear to be great thinkers as well. What luck that I just happen to have in a new shipment of 'Thinking Hats' from the great de Bono himself. They come in six colours - white, red, black, yellow, green, and blue - and they would match your complexions perfectly! And I know what you're thinking - I'll let you have 6 for the price of 1, if only you can solve my hat puzzle.

The Milliner wrote:I'll ask you each to close your eyes, and stand in a circle. On each head I'll put a thinking hat, of a colour that I choose myself. I'll choose from amongst the 6 colours available, but I won't necessarily use all 6 colours - there may be some repeats. Once you open your eyes, you'll be able to see the hats of all of your fine companions, but of course you won't be able to see what colour your own hat is. You then each get one chance to tell me (in secret) what you think your hat colour is. As you can tell, I'm a great observer - I already know each of your hat sizes, for example - so I'll certainly know if you communicate with each other and give the game away!

Now, I'm a reasonable fellow; I don't expect everyone to guess their hat colour correctly. If at least one of you correctly guesses your hat colour, then you win. You can't say fairer than that, can you? Well, I can see from your faces that you're already sold on these hats - so let me know when you're ready to take up this amazing offer!

The ex-prisoners step to the side of the road, and start to confer, since they won't get a chance after accepting the deal. What strategy should they use to maximise their chance of getting at least one correct guess?

(I know what you're thinking - there's a decent chance they'd get it right even if they just guess randomly. However, unbeknownst to the ex-prisoners, the hats are rather overpriced, so the milliner will still make money if they get it right anyway. But, then, he has to make a living somehow!)

______________________________________
Bonus puzzle: Generalise the solution to n hats (so n prisoners, n different hat colours available.)

Qaanol
The Cheshirest Catamount
Posts: 3064
Joined: Sat May 09, 2009 11:55 pm UTC

### Re: Hat puzzle - 6 (or n) randomly coloured hats in a circle

We know this as a dice-rolling puzzle. It generalizes to n in the obvious manner.

The 2-person coin flipping version is especially well suited to stretching the minds of nonmathematicians, since most people can understand the solution once they find it, but will think it impossible at first, then solve it with a few good hints.
wee free kings

dudiobugtron
Posts: 1098
Joined: Mon Jul 30, 2012 9:14 am UTC
Location: The Outlier

### Re: Hat puzzle - 6 (or n) randomly coloured hats in a circle

I didn't realise it was so well known - probably because I was searching for it as a hat puzzle rather than a dice puzzle!

And agreed about the two-person version (Although again I know it with red and blue hats, rather than with heads or tails).

jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

### Re: Hat puzzle - 6 (or n) randomly coloured hats in a circle

Qaanol wrote:We know this as a dice-rolling puzzle.

Got a mouse in your pocket?

Anyway, repeat of this golden oldy

viewtopic.php?f=3&t=348

that's 3 digits in the thread number. The number for this thread has 6 digits.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

snowyowl
Posts: 464
Joined: Tue Jun 23, 2009 7:36 pm UTC

### Re: Hat puzzle - 6 (or n) randomly coloured hats in a circle

I've seen this one before.

Variation: One of the prisoners (Dalton) is colourblind. This would not be a problem because all the hats have their colours written on them, except that another prisoner (Ash) is wearing his hat backwards. So Dalton doesn't know what colour Ash's hat is. Everyone else is fine, though.

The rest of the problem remains the same. Prove that it is now impossible for the prisoners to guarantee that one of them correctly guesses their hat's colour.
The preceding comment is an automated response.

Lopsidation
Posts: 183
Joined: Tue Oct 27, 2009 11:29 pm UTC

### Re: Hat puzzle - 6 (or n) randomly coloured hats in a circle

Cool variation, snowyowl.

Spoiler:
No matter what strategy the prisoners use, all 6 of them guess correctly exactly 1/6 of the time. Therefore, in a hypothetical winning strategy, every hat configuration must lead to exactly one of the prisoners guessing correctly.

Now, in this hypothetical winning strategy, pick a configuration where Dalton guesses correctly. Then, recolor Ash's hat to match Ash's guess. This doesn't change Dalton's guess or Ash's guess, so we found a scenario where two prisoners both guess their hat color correctly. Contradiction! This strategy can't ensure a win after all.

Adding to snowyowl's version: Now Dalton is only red/green colorblind. He can tell all the hat colors apart except for red and green. Now can the prisoners win?

Vytron
Posts: 429
Joined: Mon Oct 19, 2009 10:11 am UTC
Location: The Outside. I use She/He/Her/His/Him as gender neutral pronouns :P

### Re: Hat puzzle - 6 (or n) randomly coloured hats in a circle

Necro Bump

Spoiler:
Adding to snowyowl's version: Now Dalton is only red/green colorblind. He can tell all the hat colors apart except for red and green. Now can the prisoners win?

To know if there's a winning strategy for the prisoners of the big puzzle, all you need to do is proving it for a small puzzle. For instance, one with 4 people.

So, Ash wears their hat backwards, Brooke and Carol are fine, and Dalton sees Red and Green as Brown.

I assume that the warden isn't evil, as she could make one color brown (so that Dalton confuses 3 colors and not 2, because colorblind people can't see red or green), but instead the hat colors are Red, Green, Blue and White.

The usual strategy would be for them to number the colors:

0 - Red
1 - Green
2 - Blue
3 - White

S is the sum of the numbers mod 4 (a 4 reverts to 0, 5 to 1, etc.)

Ash will guess that his hat is S
Brook will guess that her hat is S+1
Carol will guess that her hat is S+2
Dalton will guess that his hat is S+3

Except Dalton can't see the difference between Red and Green when Ash appears to wear a brown hat.

Let's start trivial with "everyone is wearing a red hat", who guesses right in this case if Dalton isn't colorblind?

S=0, so Ash will guess 0, Brook 1, Carol 2, and Dalton 3. Ash will be right, so this case wouldn't be an issue if Dalton guessed something random.

Everyone with a green hat:

S=3, so Ash will guess 3, Brook 0, Carol 1, and Dalton 2. Carol will be right, so this case wouldn't be an issue if Dalton guessed something random.

The warden can't let this happen, so he could try everyone with red hats, but Ash with green one.

Now Ash sees S=0, but everyone else sees S=1. Ash will guess 0, Brook 2, Carol 3 and Dalton 0. This is a case where Dalton needs to see Ash's bit to guess correctly. To combat this case, Dalton needs to guess 0 when they see Ash with a brown hat when the other 2 wear a red one.

With that strategy, the warden wants Dalton to not be able to tell he's in that case. So he tries everyone with green hats, but Carol with a red one.

Here Carol sees S=3, but everyone else sees S=2. Ash will guess 2, Brook 3, Carol 1 and Dalton 1. Again, Dalton needs to be right here, so he can use a "guess 1 when Ash's hat is brown and he other 2 have green ones".

These are the bases cases, because they're the ones where Ash's hat matters (i.e. the warden needs to give Ash a green or red hat to take advantage of Dalton's color-blindness) and coloring other people's hats aren't different (Dalton can tell the color of the hats of Brook and Carol because they don't wear them backwards.)

Therefore, the prisoners can always guarantee that one of them guessed correctly their hat color (either Ash, Brooke or Carol will guess their hat correctly, or Dalton knows what to guess when Ash's hat looks brown depending on the colors of Brook and Carol's hats, because an attempt by the warden to mess them up changes Dalton's bit, which means someone else will guess correctly instead of him.)

It's still impossible for Dalton and someone else to guess correctly, because at the times they guess correctly, Dalton will be guessing wrong naturally, or he will be attempting to cover for the holes in which he needs to fix his guess, and in doing so will be wrong.

--------

In conclusion, Dalton being color-blind doesn't matter because:

-Ash doesn't need to even know that Dalton is colorblind.
-If Brook, Carol and Dalton see that Ash has a blue or white hat, using the normal strategy will work.

That means the warden has to give Ash a red or green hat, and then, the search space is reduced in half, and Brook, Carol and Dalton have enough bits to figure out what Dalton will have to guess if he's the one that will have to guess his hat color.

rmsgrey
Posts: 3530
Joined: Wed Nov 16, 2011 6:35 pm UTC

### Re: Hat puzzle - 6 (or n) randomly coloured hats in a circle

Vytron wrote:Necro Bump

I don't think your basic strategy works in the first place - consider WWWR where Dalton sees S=1 and guesses Red, while Brook sees S=2 and guesses White so both guess right...

I don't know whether your argument works if you try running it with a valid strategy, but my intuition is that it won't.

Hmmm...

If there is a solution, I can tell you one characteristic:

Spoiler:
There can't be any situation where changing Ash's hat colour between red and green changes whether it's Ash or Dalton that would be guessing right. There are systems which fail to satisfy this condition, but there are also systems where it does work provided you have at least 4 people and colours.

If changing Ash's hat colour between red and green changes whether it's Ash or Dalton who would guess right with no colour-blindness, then, since neither of them knows the difference between the two states any more (Ash can't see his own hat, and Dalton can't tell the difference between the two hats) what each of them guesses has to be the same in both cases - so either Dalton gets his hat right both times, and there's a case where they both get their own hat right, or he gets his hat wrong both times and there's a case where no-one gets their hat right...

Another way of phrasing the red/green colourblindness situation is: "In the original problem, is there an optimal strategy where there are two arrangements of hats that differ in only one place, and where the same person gets their hat right both times?" If the answer is "no" then any form of colour-blindness prevents optimality; if the answer is "yes" then it doesn't show that red-green colourblindness only affecting Dalton's perception of Ash's hat can be compensated for, but it makes it pretty plausible.

Vytron
Posts: 429
Joined: Mon Oct 19, 2009 10:11 am UTC
Location: The Outside. I use She/He/Her/His/Him as gender neutral pronouns :P

### Re: Hat puzzle - 6 (or n) randomly coloured hats in a circle

Spoiler:
I don't think your basic strategy works in the first place - consider WWWR where Dalton sees S=1 and guesses Red, while Brook sees S=2 and guesses White so both guess right...

The alternative strategy is only used when Ash's hat is red or green, otherwise they use the normal strategy, in which WWWR doesn't differentiate between Dalton being colorblind or not (he'll see 3 white hats, everyone else acts as normal, so this is the original problem where only one of them guesses right.)

Cauchy
Posts: 602
Joined: Wed Mar 28, 2007 1:43 pm UTC

### Re: Hat puzzle - 6 (or n) randomly coloured hats in a circle

First, the standard solution in a nutshell, so that everyone is on the same page as me for my modified solution. The players number the colors from 0 to n-1 and also number the players from 0 to n-1. When each player is up to guess their hat color, they guess as though the sum of all the hats is congruent to their assigned number, mod n. So Player 0 guesses as though the sum of the hats were congruent to 0 mod n; no matter what configuration of hats Player 0 sees, this is possible. Player 1 guesses as though the sum of hats were 1 mod n, and so on for the other players. The actual sum is congruent to one of 0, 1, ..., n-1 mod n, and whatever the sum is, that numbered player will have guessed their hat color correctly.

Now, to answer the red/green colorblind, only Ash's hat color is unwritten case: a solution is possible for n >= 3 players, and impossible for n = 2 players.

For n = 2 people, Dalton's disability makes the problem intractable. In this situation, Dalton and Ash are the only two players, and red and green are the only two colors, so Dalton gains no information from looking at Ash's hat. Dalton must therefore always say the same color, say red. When Dalton's hat is green, Ash must say something, and when his hat color is also wrong for this guess, then both players are wrong.

Dalton's disability can be worked around for n >= 3 players. We designate one of the players who is neither Dalton nor Ash the Switcher. Now, we number the colors on the hats so that red is 0 and green is 1, and the rest of the colors are numbered 2 to n-1 in some order. As in the standard solution, Dalton is tasked with answering as though the sum of the hats is congruent to 0 mod n, the Switcher is assigned a sum of 1 mod n, and 2 to n-1 are assigned to the other players. Now, Dalton is instructed to proceed as though whenever Ash's hat is red or green, it is red. So Dalton will make his guess in line with the standard, normally-sighted algorithm whenever Ash's hat is any color other than green: on non red/green colors, his color-blindness never comes into play, and for red, Dalton makes the red/green choice correctly. In these situations, the normal algorithm runs smoothly, and the prisoners issue their correct guess without problem. Dalton will only falter, and intervention will only be needed, when Ash's hat is green.

In the situation where Ash's hat is green, Dalton's guess will make his perceived sum be congruent to 0 mod n, but since Ash's hat has value one higher than Dalton thought, Dalton is actually guessing as though the sum of the hats were 1 mod n. This is where the Switcher comes in. When the switcher sees that Ash's hat is green (this is why the Switcher can't be Ash!), the Switcher will know that Dalton is going to guess as though the sum of the hats were 1 mod n instead of his assigned role of 0 mod n. In this case, the Switcher also deviates from his normal answer. He answers as though the sum of the hats were 0 mod n in these situations instead of his normal guess of 1 mod n, effectively switching algorithmic positions with Dalton. In this way, the n prisoners still cover the n possibilities for the sum mod n and will hence issue a correct guess.
(∫|p|2)(∫|q|2) ≥ (∫|pq|)2
Thanks, skeptical scientist, for knowing symbols and giving them to me.

rmsgrey
Posts: 3530
Joined: Wed Nov 16, 2011 6:35 pm UTC

### Re: Hat puzzle - 6 (or n) randomly coloured hats in a circle

Vytron wrote:
Spoiler:
I don't think your basic strategy works in the first place - consider WWWR where Dalton sees S=1 and guesses Red, while Brook sees S=2 and guesses White so both guess right...

The alternative strategy is only used when Ash's hat is red or green, otherwise they use the normal strategy, in which WWWR doesn't differentiate between Dalton being colorblind or not (he'll see 3 white hats, everyone else acts as normal, so this is the original problem where only one of them guesses right.)

My point was that you got the normal strategy wrong.

Cauchy's solution shows that Dalton only needs to be able to distinguish one colour from the others. If Dalton defaults to 0, which is also one of his indistinguishable colours, then Ash's number has to be the number of one of the colours Dalton can distinguish, and the people whose numbers match colours Dalton can't distinguish need to switch to 0 when Ash's hat is the colour that matches their number...

quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

### Re: Hat puzzle - 6 (or n) randomly coloured hats in a circle

@Cauchy: what is the maximum proportion of players that can be unable to distinguish between 2 colors?

Also, it would seem that they could win even if Dalton can't distinguish any color except for one. Let's say Dalton can only recognize White. Then we can assign all other players except Ash to be Switchers for each sum corresponding to Ash having each non-white color. Is this correct?

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

### Re: Hat puzzle - 6 (or n) randomly coloured hats in a circle

Vytron wrote:Necro Bump

Spoiler:
Adding to snowyowl's version: Now Dalton is only red/green colorblind. He can tell all the hat colors apart except for red and green. Now can the prisoners win?

To know if there's a winning strategy for the prisoners of the big puzzle, all you need to do is proving it for a small puzzle. For instance, one with 4 people.

So, Ash wears their hat backwards, Brooke and Carol are fine, and Dalton sees Red and Green as Brown.

I assume that the warden isn't evil, as she could make one color brown (so that Dalton confuses 3 colors and not 2, because colorblind people can't see red or green), but instead the hat colors are Red, Green, Blue and White.

The usual strategy would be for them to number the colors:

0 - Red
1 - Green
2 - Blue
3 - White

S is the sum of the numbers mod 4 (a 4 reverts to 0, 5 to 1, etc.)

Ash will guess that his hat is S
Brook will guess that her hat is S+1
Carol will guess that her hat is S+2
Dalton will guess that his hat is S+3

Except Dalton can't see the difference between Red and Green when Ash appears to wear a brown hat.

Let's start trivial with "everyone is wearing a red hat", who guesses right in this case if Dalton isn't colorblind?

S=0, so Ash will guess 0, Brook 1, Carol 2, and Dalton 3. Ash will be right, so this case wouldn't be an issue if Dalton guessed something random.

Everyone with a green hat:

S=3, so Ash will guess 3, Brook 0, Carol 1, and Dalton 2. Carol will be right, so this case wouldn't be an issue if Dalton guessed something random.

The warden can't let this happen, so he could try everyone with red hats, but Ash with green one.

Now Ash sees S=0, but everyone else sees S=1. Ash will guess 0, Brook 2, Carol 3 and Dalton 0. This is a case where Dalton needs to see Ash's bit to guess correctly. To combat this case, Dalton needs to guess 0 when they see Ash with a brown hat when the other 2 wear a red one.

With that strategy, the warden wants Dalton to not be able to tell he's in that case. So he tries everyone with green hats, but Carol with a red one.

Here Carol sees S=3, but everyone else sees S=2. Ash will guess 2, Brook 3, Carol 1 and Dalton 1. Again, Dalton needs to be right here, so he can use a "guess 1 when Ash's hat is brown and he other 2 have green ones".

These are the bases cases, because they're the ones where Ash's hat matters (i.e. the warden needs to give Ash a green or red hat to take advantage of Dalton's color-blindness) and coloring other people's hats aren't different (Dalton can tell the color of the hats of Brook and Carol because they don't wear them backwards.)

Therefore, the prisoners can always guarantee that one of them guessed correctly their hat color (either Ash, Brooke or Carol will guess their hat correctly, or Dalton knows what to guess when Ash's hat looks brown depending on the colors of Brook and Carol's hats, because an attempt by the warden to mess them up changes Dalton's bit, which means someone else will guess correctly instead of him.)

It's still impossible for Dalton and someone else to guess correctly, because at the times they guess correctly, Dalton will be guessing wrong naturally, or he will be attempting to cover for the holes in which he needs to fix his guess, and in doing so will be wrong.

--------

In conclusion, Dalton being color-blind doesn't matter because:

-Ash doesn't need to even know that Dalton is colorblind.
-If Brook, Carol and Dalton see that Ash has a blue or white hat, using the normal strategy will work.

That means the warden has to give Ash a red or green hat, and then, the search space is reduced in half, and Brook, Carol and Dalton have enough bits to figure out what Dalton will have to guess if he's the one that will have to guess his hat color.

As stated, you seem to be misstating the base strategy. None of the people know S, they know S - (their colour), and they each guess their colour to cover all possible values of S.

In any case, you say when Brook and Carol have a red hat and Ash has a red or green hat that Dalton will guess Red. What does your strategy do if the layout is RRRG? You've only stated how Dalton's strategy is different, but in this case he will be wrong and one of the others needs to be correct, which they won't be with the usual strategy.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

### Re: Hat puzzle - 6 (or n) randomly coloured hats in a circle

quintopia wrote:@Cauchy: what is the maximum proportion of players that can be unable to distinguish between 2 colors?

Assuming that the colours can be cyclically ordered in such a way that every persons indistinguishable colours are adjacent, Cauchy's strategy works for (n-1)/2 colourblind people. If the indistinguishable colours for each person all include one colour and have no other overlap then it works for n-2 colourblind people. Of course Ash can be colourblind increasing both of these by 1, but that's a redundant change.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

Vytron
Posts: 429
Joined: Mon Oct 19, 2009 10:11 am UTC
Location: The Outside. I use She/He/Her/His/Him as gender neutral pronouns :P

### Re: Hat puzzle - 6 (or n) randomly coloured hats in a circle

Spoiler:
mike-l wrote:What does your strategy do if the layout is RRRG?

So let's see:

Ash sees S=1
Brooke sees S=1
Carol sees S=1
Dalton sees S=0

Ash will guess 1 (wrong)
Brooke will guess 2 (wrong)
Carol will guess 3 (wrong)
Dalton will guess 0 (wrong)

Dalton can't distinguish from this case and the case where everyone wears red but Ash wears Green, so my strategy doesn't work.

Anyway, Lopsidation asked "Now Dalton is only red/green colorblind. He can tell all the hat colors apart except for red and green. Now can the prisoners win?" and I answered Yes, which was correct, and then provided a solution that doesn't work (thanks for your counter-example), which was incorrect. My point was that they should be able to beat the warden because they have enough bits to solve the puzzle when they're in the case that matters (Ash with a Green/Red hat), which would include Brooke and Carol to switch strategies on the critical cases, though I failed to provide such an alternative strategy.

I'm still glad I Necro-Bumped because I got to see the solution that worked by Cauchy, though.