Another hat puzzle

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

operator[]
Posts: 155
Joined: Mon May 18, 2009 6:11 pm UTC
Location: Stockholm, Sweden

Another hat puzzle

Postby operator[] » Wed Sep 13, 2017 10:54 am UTC

The setup is pretty classical: n mathematicians stand in a circle, each gets assigned either a black or a white hat. Everyone can see everyone else's hat, and they each have to guess the color of their own hat. Everyone guesses simultaneously, without hearing the others' guesses. If you are allowed to set up a common strategy beforehand, how many guesses can you guarantee to be correct in the worst case?

However, there is a twist: everyone has to follow exactly the same strategy. Thus they can only base their guess on what hats they see in clockwise order starting from themselves, and not e.g. their position in the circle. So for instance, if you see only black hats, you'd better guess "black", or else the all-black case would have everyone guess incorrectly.

In the classical case, without symmetrical strategies, we can achieve floor(n/2) guaranteed correct guesses. However, that doesn't work in the symmetrical case. How well can we do now?

User avatar
Gwydion
Posts: 336
Joined: Sat Jun 02, 2007 7:31 pm UTC
Location: Chicago, IL

Re: Another hat puzzle

Postby Gwydion » Wed Sep 13, 2017 2:11 pm UTC

Just want to clarify - when you say worst-case, do you mean that we can assume an adversary is placing the hats so as to subvert our strategy? Does that also mean that we should treat "guess randomly" as guaranteed to fail? If so:
Spoiler:
We can start with the easy ones - for n=2, the worst case is 0 correct guesses. The options are to say the color of the other guy's hat, or say the opposite, or guess randomly. The two deterministic options can be beaten with adversarial placement - opposite colors for the former, and the same color for the latter. There is no way to use relative position to help here, because there is only one other player.

For n=3, I think the answer is 1. In order to not have all 3 fail when they all have the same color hat, anyone who sees 2 of the same color must say the same color - otherwise, 3 matching hats = 0 correct guesses. However, this leaves a trickier problem when two players see opposite colors - their options (without considering positioning) are again "always white", "always black", or "random", and an adversary could choose the color such that they must fail also. As an example of this, assume the strategy is to say the same color if you see two matching colors, and say black if you see one of each. An adversarial placement would be one black and two white hats. The one wearing the black hat would guess white, and the players wearing white would both guess black.

The better strategy for n=3 would be when you see opposite colors, choose the one on your left. This way, at least one of the two would choose correctly. Using the example above, the one standing to the right of the player with the black hat would be correct, while the other would be incorrect. This strategy guarantees at least 1 correct answer.

operator[]
Posts: 155
Joined: Mon May 18, 2009 6:11 pm UTC
Location: Stockholm, Sweden

Re: Another hat puzzle

Postby operator[] » Wed Sep 13, 2017 2:30 pm UTC

Gwydion wrote:Just want to clarify - when you say worst-case, do you mean that we can assume an adversary is placing the hats so as to subvert our strategy? Does that also mean that we should treat "guess randomly" as guaranteed to fail?

Yes, and yes.

User avatar
Gwydion
Posts: 336
Joined: Sat Jun 02, 2007 7:31 pm UTC
Location: Chicago, IL

Re: Another hat puzzle

Postby Gwydion » Thu Sep 14, 2017 3:39 pm UTC

The four person scenario:
Spoiler:
There are 4 general configurations to consider, I'll use x and y to represent the colors.

xx xy xx xx
xx yx xy yy

If a player looks across the group and sees "xxx" they must guess x, or else configuration 1 yields no correct answers. If a player sees "xyx" in that order they must guess y, or else configuration 2 yields no correct answers.

Thus, in configuration 3 the person wearing y will be wrong, and the person standing opposite y will be wrong, giving an upper bound of 2 for this scenario.

If we want the other two x's to both get it right, the last rule must be that if a player sees "xxy" or "yxx" they should guess x. However, with this rule all 4 players in the last configuration will be wrong. The best outcome of a worst-case scenario here is also only 1 correct.

User avatar
Moose Anus
Posts: 384
Joined: Fri Oct 14, 2011 10:12 pm UTC

Re: Another hat puzzle

Postby Moose Anus » Thu Sep 14, 2017 6:33 pm UTC

Spoiler:
I think I have the worst case at ceiling(n/2).

Rules for universal strategy:
1) On the first guess, choose the hat you see the most of. If there is a tie, choose black.
2) If there are an even number of players and the guesses were split evenly and are wrong, switch your vote.
3) Keep your vote the same if number of wrong guesses is equal to or less than the number of other colored hats you see.
4) Switch your vote if the number of wrong guesses is more than the number of other colored hats you see.


Code: Select all

Key:
Capital letter = player name
Lower case letter = player guess
i = iteration
s = solved
r = rule, number is number from rules list
k = black hat
w = white hat
. = same as above because same game

Players 1 Worst case 2
A   a   i   s   r
k   k   1   T   1
w   k   1   F   1
.   w   2   T   3

Players 2 Worst case 2
A   B   a   b   i   s   r
k   k   k   k   1   T   1
k   w   w   k   1   F   1
.   .   k   w   2   T   2
w   w   w   w   1   T   1


Players 3 Worst case 3
A   B   C   a   b   c   i   s   r
k   k   k   k   k   k   1   T   1
k   k   w   k   k   k   1   F   1
.   .   .   k   k   w   2   T   3
k   w   w   w   k   k   1   F   1
.   .   .   k   k   k   2   F   4(A)
.   .   .   k   w   w   3   T   4(B,C)
w   w   w   w   w   w   1   T   1

Players 4 Worst case 2
A   B   C   D   a   b   c   d   i   s   r
k   k   k   k   k   k   k   k   1   T   1
k   k   k   w   k   k   k   k   1   F   1
.   .   .   .   k   k   k   w   2   T   4(D)
k   k   w   w   w   w   k   k   1   F   1
.   .   .   .   k   k   w   w   2   T   2
k   w   w   w   w   w   w   w   1   F   1
.   .   .   .   k   w   w   w   2   T   4(A)
w   w   w   w   w   w   w   w   1   T   1

Players 5 Worst case 3
A   B   C   D   E   a   b   c   d   e   i   s   r
k   k   k   k   k   k   k   k   k   k   1   T   1
k   k   k   k   w   k   k   k   k   k   1   F   1
.   .   .   .   .   k   k   k   k   w   2   T   4(E)
k   k   k   w   w   k   k   k   k   k   1   F   1
.   .   .   .   .   k   k   k   k   k   2   F   3
.   .   .   .   .   k   k   k   w   w   3   T   4(D,E)
k   k   w   w   w   w   w   w   w   w   1   F   1
.   .   .   .   .   w   w   w   w   w   2   F   3
.   .   .   .   .   k   k   w   w   w   3   T   4(A,B)
k   w   w   w   w   w   w   w   w   w   1   F   1
.   .   .   .   .   k   w   w   w   w   2   T   4(A)
w   w   w   w   w   w   w   w   w   w   1   T   1

Players 6 Worst case 3
A   B   C   D   E   F   a   b   c   d   e   f   i   s   r
k   k   k   k   k   k   k   k   k   k   k   k   1   T   1
k   k   k   k   k   w   k   k   k   k   k   k   1   F   1
.   .   .   .   .   .   k   k   k   k   k   w   2   T   4(F)
k   k   k   k   w   w   k   k   k   k   k   k   1   F   1
.   .   .   .   .   .   k   k   k   k   k   k   2   F   3
.   .   .   .   .   .   k   k   k   k   w   w   3   T   4(E,F)
k   k   k   w   w   w   w   w   w   k   k   k   1   F   1
.   .   .   .   .   .   k   k   k   w   w   w   2   T   2
k   k   w   w   w   w   w   w   w   w   w   w   1   F   1
.   .   .   .   .   .   w   w   w   w   w   w   2   F   3
.   .   .   .   .   .   k   k   w   w   w   w   3   T   4(A,B)
k   w   w   w   w   w   w   w   w   w   w   w   1   F   1
.   .   .   .   .   .   k   w   w   w   w   w   2   T   4(A)
w   w   w   w   w   w   w   w   w   w   w   w   1   F   1
Lemonade? ...Aww, ok.

User avatar
Gwydion
Posts: 336
Joined: Sat Jun 02, 2007 7:31 pm UTC
Location: Chicago, IL

Re: Another hat puzzle

Postby Gwydion » Thu Sep 14, 2017 6:54 pm UTC

Moose Anus, that only works if you can hear other people's guesses and know who is right or wrong, then switch answers - in this game, answers are given simultaneously and only once.

I've given more thought to the 5-player scenario but still haven't found a way to easily generalize:
Spoiler:
There are only 4 layouts to consider here WLOG (listed in order rather than as circles):
1. xxxxx
2. xxxxy
3. xxxyy
4. xxyxy

As before, scenario 1 requires one of the decision rules to be "say x if you see 4 x's", so the y in scenario 2 is necessarily going to be wrong. This next part is hard for me to explain in words, but I'll do my best.

Looking at the other layouts, there are 7 pairs that each represent a player seeing the same layout relative to one another. This is hard to notate in plaintext, so I'll recreate the 4 scenarios below. Two positions that share a letter effectively see the same layout, but a correct guess for one would be incorrect for the other. I'll leave scenario 1 and the lone y in #2 as they are for now.
1. xxxxx
2. abcdy
3. efeda
4. ggcfb

The person marked a sees, for example, BBBW from left to right - if they are in scenario 2 they are wearing a black hat, but in scenario 3 it is white.
The point of all this is that any rule that enables a to get it right in one arrangement, necessarily will be wrong in another. Thus, there is at least 1 right/1 wrong answer guaranteed in #3 and #4 (e and g), and 1 guaranteed wrong in 2. There are at most 7 right answers shared among the 3 layouts, so by the pigeonhole principle 2 is our best outcome here.

User avatar
Moose Anus
Posts: 384
Joined: Fri Oct 14, 2011 10:12 pm UTC

Re: Another hat puzzle

Postby Moose Anus » Thu Sep 14, 2017 7:55 pm UTC

No, the solution I wrote doesn't depend on knowing who is right or wrong. My assumptions are that they know who said what last time, and they know whether the collective answer was wrong, and then they can all simultaneously guess again. It is also positionally independent, which is nice.
Lemonade? ...Aww, ok.

Xias
Posts: 363
Joined: Mon Jul 23, 2007 3:08 am UTC
Location: California
Contact:

Re: Another hat puzzle

Postby Xias » Sat Sep 16, 2017 7:49 pm UTC

Moose Anus wrote:My assumptions are that they know who said what last time


What is this "last time" you speak of?

I think you've confused "how many guesses can you guarantee to be correct in the worst case" to mean "how many iterations must happen before everyone is correct" when that is not what is being asked. All n people make exactly one guess at the same time, following one strategy. So there are n guesses that happen simultaneously, and only one iteration.

User avatar
Moose Anus
Posts: 384
Joined: Fri Oct 14, 2011 10:12 pm UTC

Re: Another hat puzzle

Postby Moose Anus » Mon Sep 18, 2017 1:37 pm UTC

Xias wrote:
Moose Anus wrote:My assumptions are that they know who said what last time


What is this "last time" you speak of?

I think you've confused "how many guesses can you guarantee to be correct in the worst case" to mean "how many iterations must happen before everyone is correct" when that is not what is being asked. All n people make exactly one guess at the same time, following one strategy. So there are n guesses that happen simultaneously, and only one iteration.
Oh, I didn't realize that. Disregard mine then.
Lemonade? ...Aww, ok.

Yat
Posts: 120
Joined: Tue Feb 03, 2009 2:05 pm UTC

Re: Another hat puzzle

Postby Yat » Tue Sep 19, 2017 11:34 am UTC

I don't have a formal proof that this will work for any n>2, but it worked smoothly for the values I tried, and it seems that increasing n just gives more margin of error when you build the strategy. Here it is:
Spoiler:
First, I have to determine in advance the lower bound of the number of correct guesses. As no matter what we do, there will always be exactly 50% correct guesses among the whole set of possible situations, the fact that the "all black" and "all white" scenarios imply wasting more correct guesses that needed, we know we can't reach n/2 correct guesses. There are 2^n scenarios, n guesses for each, half of these will be correct, 2n are already taken by "all white" and "all black", 2^n-2 remaining scenarios to dispatch the remaining n*2^n/2-2n correct guesses. For n=3 that makes exactly one correct guess, when n gets bigger, it quickly gets closer to n/2.
We can therefore say that for n>2, an optimal strategy can theoretically give a lower bound of floor((n-1)/2) correct guesses. We can notice that when n is odd, it is equal to floor(n/2), which also is the optimal strategy in the classical case without symmetrical strategies.

Now, here is how I build a strategy itself. The rule is that every player makes the assumption that he has a white hat. So, the strategy that he follows is made to ensure that the required number of correct guesses is met, taking account what the black hats mistakenly guessed. If he is wrong, then the players who actually have white hats will correct that with their own guesses.

This way, we can build the strategy recursively, based on the scenario where everybody has a white hat.
Suppose you have a strategy for a player who sees x black hats, and there are x+1 players with black hats.
Any player with a black hat will follow the strategy that is already established.
Any player with a white hat, assuming he himself has a white hat, knows exactly what every player with a black hat will guess. Therefore he knows how many additional correct guesses need to be made.

Next step is to decide who will guess black and who will guess white.
Any player can use the hats as bits, 0 being white and 1 black, find the starting position that gives the smallest value for the integer represented by the bits in the circle. For example, in a 5 players configuration, a player who sees, starting from his position, bwbw, will assume the whole table has wbwbw (adding his own assumed color at the beginning), which means 01010. Using all the possible starting positions, he gets 01010, 00101, 10010, 01001 and 10100. The smallest is 00101, so the situation every white hat player can consider is wwbwb, and every white player know where his place is (our example player who sees bwbw is in second position).
If it is not the case, meaning there is a symmetry in the table, then we will just need to make sure the strategy keeps this symmetry.
Then, the players must have agreed on a way to decide who will guess right (white) and who will guess wrong (black). Apparently, any way works fine, so let's decide that the "white" guesses are attributed to the first white players from the left. In our example, if they have one correct guess to make, then the guesses will be wbibj, i and j being the guesses of the players with black hats, derived from the known strategy with x black hats.
So as every player know where his place is, he knows what must be his guess. Our example player who sees bwbw, being in second position, guesses black.
Ok, something could go wrong here: if the number of remaining required correct guesses is higher than the number of players with a white hat, the strategy can't be built. I don't have a formal proof of why it doesn't happen, but when you actually build the strategy, you notice that at each step, the fraction of black hats that already guess black because they aimed to guess wrong only gets bigger. The bigger it is, the more correct guesses are already acquired by the previous strategy, so the more purposely wrong guess there are, which means the more actually correct guesses there will be for the next step.
So, putting aside this potential source of problems, we have a strategy for a player who sees x+1 black hats, built on the strategy for a player who sees x black hats. We also know that a player who sees 0 black hats must say white to prevent the "all white" situation from being a total failure, so we have our global strategy, for any n>2.

Ok, ok, I'll build one as an example with 6 players, so that I don't avoid the trouble caused by symmetries.
Spoiler:
Here we try to secure two correct guesses in every possible situation.

We need the all white situation to be a win for everybody, so a player who sees wwwww says w. That was the x=0 strategy.

Now, with x=1, there is only one possibility, wwwwwb. The player with a black hat will guess white, so we need two additional correct guesses. I arbitrarily chose the first two white players, so the guesses will be wwbbbw, which gives the following rules for what players see: wwwwb and wwwbw guess w. wwbww, wbwww and bwwww guess b.

With x=2, there are three possibilities: wwwwbb, wwwbwb and wwbwwb.
wwwwbb: The black players respectively guess b and w, following the previous rules. We need one additional correct guess, we put it on the first white player, giving wbbbbw. In other words, wwwbb guesses w, wwbbw, wbbww and bbwww guess b.
wwwbwb: black players guess b and w, one correct guess to get, answer is wbbbbw. wwbwb guesses w, wbwbw, bwbww and bwwwb guess b.
wwbwwb: Both black players guess b. We're all set, everybody can say b, no need to worry about the symmetry. wbwwb and bwwbw guess b.

x=3, four possibilities:
wwwbbb: We already have two correct guesses, everybody says b. wwbbb, wbbbw and bbbww guess b.
wwbwbb: Same thing, wbwbb, bwbbw and bbbww guess b.
wwbbwb: Same thing, wbbwb, bbwbw and bwwbb guess b.
wbwbwb: bwbwb guesses b.

for x=4, no need to get into detail, every black player seeing three other black players will guess black, that already makes 4 correct guesses, the white players guess b.

Of course, the reasonning is the same for x=5 and x=6.

To sum up, if a player sees wwwww, wwwwb, wwwbw, wwwbb or wwbwb, he guesses w. In any other case, he guesses b.

Just to show a case where the requested number of correct guesses gives a tighter margin, here is n=7:
Spoiler:
3 correct guesses required.

x=0
wwwwww guesses w.

x=1
wwwwwwb: the black hat guy guesses w, we need 3 correct guesses, so wwwbbbw.
wwwwwb, wwwwbw and wwwbww guess w, wwbwww, wbwwww and bwwwww guess b

x=2
wwwwwbb => wwbbbwb
wwwwbb and wwwbbw guess w, wwbbww, wbbwww and bbwwww guess b.
wwwwbwb => wwbbbbw
wwwbwb and wwbwbw guess w, wbwbww, bwbwww and bwwwwb guess b.
wwwbwwb => wwbbbbw
wwbwwb and wbwwbw guess w, bwwbww, wbwwwb and bwwwbw guess b.

x=3
wwwwbbb => wbbbbbw
wwwbbb guesses w, wwbbbw, wbbbww and bbbwww guess b.
wwwbwbb => wbbbbbw
wwbwbb guesses w, wbwbbw, bwbbww and bbwwwb guess b.
wwwbbwb => wbbbbbw
wwbbwb guesses w, wbbwbw, bbwbww and bwwwbb guess b.
wwbwwbb => wbbbbbw
wbwwbb guesses w, bwwbbw, wbbwwb and bbwwbw guess b.
wwbwbwb => wwbbwbwb
wbwbwb and bwbwbw guess w, bwbwwb and bwwbwb guess b.

x=4
wwwbbbb => wbbwbbw
wwbbbb guesses w, wbbbbw and bbbbww guess b.
wwbwbbb => bbbbbbw
wbwbbb, bwbbbw and bbbwwb guess b.
wwbbwbb => wbbwbbw
wbbwbb guesses w, bbwbbw and bbwwbb guess b.
wwbbbwb => bbbbwbb
wbbbwb, bbbwbw and bwwbbb guess b.
wbwbwbb => wbbbbww
bwbwbb guesses w, bwbbwb and bbwbwb guess b.

x=5
wwbbbbb => bbbbbbw
wbbbbb and bbbbbw guess b.
wbwbbbb => bbbbbwb
bwbbbb and bbbbwb guess b.
wbbwbbb => bbbbbbw
bbwbbb and bbbwbb guess b.

x=6
wbbbbbb => bbbbbbb
bbbbbb guesses b.

x=7
bbbbbbb => bbbbbbb
Nothing new here.


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 1 guest