Another Hat Problem
Source: Very interesting puzzle from http://forums.xkcd.com/
Problem:
There are 7 people standing in a circle, and each has either a red or a blue hat. The colors of the hats are chosen uniformly at random (although the problem is much the same if they're chosen adversarially). The people can't see their own hats, but can see each others'. Everyone is given a strip of paper and a pen, and simultaneously writes "red", "blue", or "abstain". Nobody can see what the other people are writing, or convey information in any other way. They win if somebody guesses his own hat color, and nobody guesses wrong.
Find a strategy (which they agree on ahead of time) that maximizes probability of winning. Obviously, it is impossible to make a strategy that wins every time, because somebody must guess and that person has no information.
To make it easier, try it first with three people.
Disclaimer: I posted this problem (in different words) 4 months back here but did not get any solution. Then I did not have a solution of my own and the solution on the source was too "non-intuitive". Try it again. Its very interesting and trying to solve it gives u a kick :P
Problem:
There are 7 people standing in a circle, and each has either a red or a blue hat. The colors of the hats are chosen uniformly at random (although the problem is much the same if they're chosen adversarially). The people can't see their own hats, but can see each others'. Everyone is given a strip of paper and a pen, and simultaneously writes "red", "blue", or "abstain". Nobody can see what the other people are writing, or convey information in any other way. They win if somebody guesses his own hat color, and nobody guesses wrong.
Find a strategy (which they agree on ahead of time) that maximizes probability of winning. Obviously, it is impossible to make a strategy that wins every time, because somebody must guess and that person has no information.
To make it easier, try it first with three people.
Disclaimer: I posted this problem (in different words) 4 months back here but did not get any solution. Then I did not have a solution of my own and the solution on the source was too "non-intuitive". Try it again. Its very interesting and trying to solve it gives u a kick :P
I think one solution with probability 0.5 of winning is very obvious - One of them writes "Red" on his paper and all others abstain. That clearly means that he is right half of the time. Is there any chance of doing better than 0.5 prob. of winning?
ReplyDelete@Abhay..
ReplyDeleteYou can find solutions here
This comment has been removed by a blog administrator.
ReplyDeleteThis comment has been removed by a blog administrator.
ReplyDelete@Chiraag.. Removing your comment as you read the problem wrong!
ReplyDelete