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 allblack 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?
Another hat puzzle
Moderators: jestingrabbit, Moderators General, Prelates

 Posts: 155
 Joined: Mon May 18, 2009 6:11 pm UTC
 Location: Stockholm, Sweden
Re: Another hat puzzle
Just want to clarify  when you say worstcase, 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:

 Posts: 155
 Joined: Mon May 18, 2009 6:11 pm UTC
 Location: Stockholm, Sweden
Re: Another hat puzzle
Gwydion wrote:Just want to clarify  when you say worstcase, 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.
Re: Another hat puzzle
The four person scenario:
Spoiler:
 Moose Anus
 Posts: 386
 Joined: Fri Oct 14, 2011 10:12 pm UTC
Re: Another hat puzzle
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 5player scenario but still haven't found a way to easily generalize:
I've given more thought to the 5player scenario but still haven't found a way to easily generalize:
Spoiler:
 Moose Anus
 Posts: 386
 Joined: Fri Oct 14, 2011 10:12 pm UTC
Re: Another hat puzzle
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.
Re: Another hat puzzle
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.
 Moose Anus
 Posts: 386
 Joined: Fri Oct 14, 2011 10:12 pm UTC
Re: Another hat puzzle
Oh, I didn't realize that. Disregard mine then.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.
Lemonade? ...Aww, ok.
Re: Another hat puzzle
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:
Ok, ok, I'll build one as an example with 6 players, so that I don't avoid the trouble caused by symmetries.
Just to show a case where the requested number of correct guesses gives a tighter margin, here is n=7:
Spoiler:
Ok, ok, I'll build one as an example with 6 players, so that I don't avoid the trouble caused by symmetries.
Spoiler:
Just to show a case where the requested number of correct guesses gives a tighter margin, here is n=7:
Spoiler:
Who is online
Users browsing this forum: The Great Hippo and 5 guests