Hats in a circle
Source: Puzzle Toad, CMU
Problem: Each hat is black or white. The people are standing in a circle. Now our n hat wearing friends are standing in a circle and so everyone can see everybody else's hat. The hats have been assigned randomly and each allocation of hat colors is equally likely. At a certain moment in time each person must simultaneously shout "my hat is black'' or "my hat is white'' or "I haven't a clue''. The team wins a big prize if at least one person gets the color of his hat right and no one gets it wrong (saying "I haven't a clue'' is not getting it wrong). Of course, if anyone gets it wrong, the whole team is eliminated and this is painful. The prize is big enough to risk the pain and so devise a strategy which gives a good chance of success.
Update (29/01/10): Solution: Posted in comments by me.
Update (06/02/10): Previous solution deleted. Solution reposted with more explanation. :)
Problem: Each hat is black or white. The people are standing in a circle. Now our n hat wearing friends are standing in a circle and so everyone can see everybody else's hat. The hats have been assigned randomly and each allocation of hat colors is equally likely. At a certain moment in time each person must simultaneously shout "my hat is black'' or "my hat is white'' or "I haven't a clue''. The team wins a big prize if at least one person gets the color of his hat right and no one gets it wrong (saying "I haven't a clue'' is not getting it wrong). Of course, if anyone gets it wrong, the whole team is eliminated and this is painful. The prize is big enough to risk the pain and so devise a strategy which gives a good chance of success.
Update (29/01/10): Solution: Posted in comments by me.
Update (06/02/10): Previous solution deleted. Solution reposted with more explanation. :)
Of course one algorithm is obvious:
ReplyDeleteLeading to a win with probability half. Everyone decides that they all would consider parity of number of whites to be even and shout their hat color accordingly.Since, everyone will be correct half of the time, we are doing well in half of the cases.
Can we do better?
Another strategy yields a correct solution with the probability 1-O((ln n)/n).
Let the hats be represented as {0,1}/ Suppose we partition the set {0,1}^n into two sets W and L which has the property that L is a cover, that is if s belongs to W, all strings which have hamming distance 1 from s (that is have exactly one bit different from s) are in L.
A person knows colors of all the hats except his. There is a unique value that he can "assign" to his hat so that the bit string would belong to W.
If the bit string indeed belongs to W, then all people who shouted their colour would do it correctly as if anyone did wrong, the string would not be in W.
So, the question to be answered now is what is the size of W.
Probability of winning = 1 - (size of L)/2^n
We will prove that from our construction, maximum size of cover L possible = (2^n)*(2ln n)/n
So, Prob of winning >= 1-(2ln n)/n
Making a small cover:
Let p = (ln n)/n. Choose L1 randomly by placing y ∈ {0,1}^n into L1 with probability p. Then let L2 be those z ∈ {0,1}^n which are at Hamming distance > 1 from some member of L1 . Clearly L = L1 union L2 is a cover and E(|L|) = (2^n)p + (2^n)(1 − p)^(n+1) <= 2^n (p + e^(−np)) <= 2^n(2ln n)/n.
So, We have a strategy of winning with prob 1-(2ln n)/n :) :)
Another solution for the problem in case n = 2^k - 1
ReplyDeleteSay n = 7
for each arrangement where all 7 get it wrong, there can be 7 where one gets it right, and the rest abstain... there are 2^7 = 128 possible arrangements, so this means identifying 16 different arrangements for everyone to be wrong on, allowing for the remaining 112 arrangements to have 1 person right and 6 people abstaining. If such a set of 16 arrangements exists, then they will have a chance of 7/8 of surviving, which is the theoretical maximum.
Number yourselves 1 to 7, or A to G, or whatever, and memorise these 16 arrangements:
RRRRRRR
RRRRBBB
RRBBRRB
RRBBBBR
RBRBRBR
RBRBBRB
RBBRRBB
RBBRBRR
BRRBRBB
BRRBBRR
BRBRRBR
BRBRBRB
BBRRRRB
BBRRBBR
BBBBRRR
BBBBBBB
(in colour because the letters B and R are so hard to tell apart at a glance)
If if looks like you might be in one of these 16 arrangements (that is, the other 6 hats you can see match one of the rows, in the order you picked earlier) then guess the opposite of what your row says. For example if you're person 3 and you see RB?RBRR then you should guess Red, because the row above lists Blue for that position.
If what you see doesn't match any of the above arrangements, abstain.
That way, if it's one of those 16, then everyone gets it wrong, if it's one of the other 112, then exactly one person will get it right. You can check if you want, but all 112 other rows differ from exactly one of the above 16 by one position (so the person in that position will guess, and noone else will).
Hamming code is useful for error correction. You send one of those 16 combinations, and even if any bit gets flipped, you can figure out which one it was, and correct the error.
Hi,
ReplyDeleteA very wonderful problem, and unique approaches, especially the second one.
I am having difficulty understanding your first method, could you please clarify with an example partition of set into W & L with |W| large?
I personally thought that largest size of W such that all its one-hamming distance partners in L, is 2^(n-1), i.e., all configurations with no. of red caps being even(or odd).
Line of reasoning was that, if W had any odd configs, we can exchange those with even ones formed by flipping first bit which should be in L.
Both the solutions are essentially the same.
ReplyDeleteSecond one is just the first solution taking a special case. The basic idea is that you do not need to understand that since all of you can see n-1 hats, and you all know about it, you have lots of information. The more the people, the more information everyone has. We try to distribute 2^n possibilities into different sets and on the basis of n-1 hats that you see, you can pick your set. Now, everyone is really picking the same set. So, now it essentially boils down to what's the size of the set. Hoping that would help. Cheers!