8
$\begingroup$

This is yet another hat puzzle, but not one of the usual ones! Key differences/commonalities between other hat puzzles are emphasized.

Five friends are going to go on a game show. When the game begins, a red or blue hat will placed on each player's head, the colors randomly chosen by independent coin flips. They stand in a circle, and the stage is set so each player can only see the hats of the players on their immediate right and left. Everyone then simultaneously guesses red or blue. If everyone is correct, they win the jackpot; if anyone is wrong, they get nothing.

As usual, before the game begins, they may devise a strategy, but after it begins, they cannot communicate in any way.

Help these players find the best strategy, and convince them they can't do better.

As a warmup, it may be helpful to try this puzzle with three players, instead of five. In that case, there is a strategy with probability $1/2$ of success (which is better than the $1/8$ chance they get by guessing randomly).

|improve this question
$\endgroup$
  • $\begingroup$ Does each player need to guess his own hat correctly, or do they need to get the correct number of red/blue hats. (I don't know if it matters - just making sure I know the rules.) $\endgroup$ – J.T. Grimes Apr 1 '15 at 3:15
  • $\begingroup$ Each player needs to guess his own hat's color correctly. $\endgroup$ – Mike Earnest Apr 1 '15 at 3:16
  • 2
    $\begingroup$ Gah, I've always sucked at probability... Surely if the hats are chosen randomly (with one not influencing another) and they have to choose simultaneously (so there's no opportunity to glean any info) then there's nothing they can do? In the 3 hat scenario, seeing two blue hats doesn't tell me anything about my own, it's still 50/50 red/blue... $\endgroup$ – Alconja Apr 1 '15 at 6:06
  • 2
    $\begingroup$ @Alconja Consider the situation with just two players, who can see each others hat, but not their own. It seems like they can't do better then $(1/2)^2=1/4$. However, if each guesses the hat color they see, they will be correct as long as their colors are the same, which happens with probability $1/2$. $\endgroup$ – Mike Earnest Apr 1 '15 at 6:34
  • 2
    $\begingroup$ @Alconja it's not really about getting a more likely pattern (the two haberdashers could equally well guess the hat colour they don't see), it's about coordinating the guesses so they will all be consistent with each other. $\endgroup$ – frodoskywalker Jun 19 '15 at 14:38
6
$\begingroup$

A weak partial answer.

The players can achieve a chance of 5/32. Each player guesses blue, unless they see two blue hats, in which case they guess red. This works for the cyclic permutations of BRBRB.

The players cannot achieve more than 1/4. First, randomly select the hat colors of all but two players that are not adjacent. Then, have those two players guess on what they see. Then, pick their hats at random. Their guesses cannot depend on each others' hats, so they simply have a 1/4 chance of both being right.

|improve this answer
$\endgroup$
  • $\begingroup$ Excellent start! $\endgroup$ – Mike Earnest Apr 1 '15 at 3:16
  • 1
    $\begingroup$ I've realized this comes down to finding the size of the max-clique in a 32-vertex graph. I tried to attack it taking advantage of symmetries, but goes bogged down in casework. $\endgroup$ – xnor Apr 1 '15 at 5:17
  • $\begingroup$ And anyone can plug the graph into a computer program, yeah. I personally want a result for general odd $n$. (BTW, computer answers for n=5, 7, 9, 11, 13 are 5, 8, 16, 32, 64, all over the denominator $2^n$. Looks like 5 is a special case?) $\endgroup$ – Lopsy Apr 2 '15 at 20:46
  • $\begingroup$ @Lopsy Interesting, so this suggests that for odd n>5, you can't do better than dividing people into groups of 2 and one group of 3, and having each group guess their groupmate's color. $\endgroup$ – xnor Apr 2 '15 at 21:23
3
$\begingroup$

We know that a probability of $5/32$ is possible (with the strategy "if you see two reds, guess blue, otherwise guess red"), so let's prove they can't do better.

Suppose there was a strategy with 6 hat combinations $c_1,\dots,c_6$ for which the players win. Let's just look at $c_1,\dots,c_5$ for now.

Connect two combinations with an edge labeled $i$ if player $i$ sees the same thing in both of them. Then two patterns which are connected agree in 3 places: the two places that player $i$ sees, and player $i$'s hat, since what he guesses is determined by what he sees.

  1. Then there must be at least one edge of each label, since player $i$ can only see 4 possible things, and there are 5 patterns, so there must be two where player $i$ sees the same thing.

  2. If two combinations agree on 4 places, they agree on the fifth, since the last hat is forced by surrounding ones.

  3. There can't be more than one edge between any pair of combinations. Otherwise, they would agree in four places, and differ in the fifth, which is impossible by (2).

  4. There are at most two edges out of each combination. If there were 3, there would have to be to edges labeled by adjacent numbers, $i$ and $i+1$; without loss of generality, $i=1$, so we have the below scenario: $$ c_1\stackrel{1}{\longleftrightarrow}c_2 \stackrel{2}{\longleftrightarrow} c_3 $$ This means $c_2$ and $c_3$ have the same hats on players $1,2,3$. If $c_2$ and $c_3$ also were the same for player 4, then by (2) they would be the same; since $c_2\neq c_3$, they must differ on 4. Similarly, $c_2$ and $c_3$ differ on 4, so it must true that $c_1$ and $c_3$ are the same on 4 (they are opposites of the same thing). So $c_1$ and $c_3$ agree on $1,2$ and $4$, which means they agree on all, which contradicts (3).

Combining (1), (3) and (4) proves that the graph is a 5 cycle, where the edges appearing in the order $1,3,5,2,4$. Thus, $c_1$ uniquely determines $c_2$ through $c_5$. But the same reasoning applied to $c_1,c_2,c_3,c_4,c_6$ shows that $c_6$ must be one of $c_1,\dots,c_5$, so the six combinations were not distinct.

|improve this answer
$\endgroup$
0
$\begingroup$

Players will see either two hats of the same colour or two hats of different colours. The strategy to maximize chance of winning is then:

Say a random colour.
Because two hats have no bearing on the colour of the hat between them, it is equally likely to be red as it is blue.

Edit: with your claim that they could do better, my gut tells me:
(no mathematical evidence to back it up)

If you see two of the same colour, say the opposite colour.
If you see two of different colours, say a random colour.
The likelihood that three in a row are the same colour is less than for the middle one to be different.

|improve this answer
$\endgroup$
  • 1
    $\begingroup$ They can do better than this $\endgroup$ – Mike Earnest Apr 1 '15 at 0:53
  • $\begingroup$ Hmm. Okay let me think. $\endgroup$ – Ian MacDonald Apr 1 '15 at 1:54
0
$\begingroup$

Based on the logic of the OP's comment responding to @Alconja, perhaps

If you see all red, guess red. If you see all blue, guess blue. If you see one of each, guess randomly. For the 3 person scenario, the chances of all hats being red is (1/2)^3, and the chance of all being blue is (1/2)^3 as well.

So the probability of being correct is 1/8 + 1/8 = 1/4. This is higher than their chances of just guessing randomly (1/8). This is still lower than the 1/2 that the OP mentions.

|improve this answer
$\endgroup$
0
$\begingroup$

For 3 haberdashers

  • There are 4 possible states: 0, 1, 2 and 3 blue hats.
  • 1 and 2 each have 3 ways of occurring
  • Any strategy that gets a given state right will necessarily get the 'adjacent' state(s) wrong.
  • We may choose to have, at most, one of the 0/3 states correct and the non-adjacent state from 2/3, giving us 4 out of 8 correct.

Let us choose to be correct for 0 and 2 blue hats:

  • If you see 2 red hats, pick red
  • If you see 1 red hat, pick blue
  • If you see 0 red hats, pick red

Still working on 5...

|improve this answer
$\endgroup$
0
$\begingroup$

The key is the consistency of the strategy so that you increase the chances not just of me being right about our hats, but about all of us being right.

One person can guess red or blue and has a 50-50 chance of being right. But that's not enough to win, the other people have to be right as well. In the case of two people, a strategy of "always guess red" or "always guess blue", applied by both people, has only a 1 in 4 chance of them both being right. Whereas "guess the colour you see" or "guess the colour you don't see" each have a 2 in 4 chance of them both being right. So that's a better strategy for the two player variant.

There are 32 possible combinations - 00000 all blue, 00001 four blues and a red, 11111 all red. Say the rule is "guess what you see on your left". They will win for 00000 and 11111 but lose for all the others. That's clearly a bad strategy, but it's better than "guess red" or "guess blue."

Working on the strategy they should use now...

|improve this answer
$\endgroup$
-1
$\begingroup$

Lets say we have players 1 to 5 then obviously if the player sees 2 of the same hats they would say the opposite color. Otherwise if the player saw one of each then they would alternate the colors they would say from 1 to five. For example if player one saw alternate colors they would say red and player 2 would say blue and player 3 would say red... This is the best strategy because lets say player 1 saw alternates and was correct then if player 2 had alternates they would have 75% of being correct if they said blue because if they were wrong then that would mean three out of 4 were red. This same logic would apply up through player 5. So to sum up strategy is if player sees 2 of same color they say opposite otherwise the players would say opposite colors from 1 to five. So if player 1 was gonna say red if they saw alternates then player 2 would say blue if they saw alternates and would alternate from there.

|improve this answer
$\endgroup$
  • $\begingroup$ I don't follow. The hats were chosen by independent coin flips. How would their neighbours' hat colours have any bearing on their own? $\endgroup$ – BenM Apr 1 '15 at 2:09
-1
$\begingroup$

I think there is no strategy possible here ..

Every hat was selected independently and randomly. No matters if you can see 2 hats of the same color, the probability of having a blue or red hat is 1/2 (because of the coin flip). You can't plan any strategy during the game because the answers have to be given simultaneously.

I think the probability to win will be 1/2^5 ... Did i miss something ?

PS : Sorry for my bad english ._.

|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.