[Guest]

This is my favourite brain teaser, and one of the most difficult that I know. I apologize if it has been posted before and I missed it.

A team of 15 takes part in a contest. They know each other and all the rules of the contest, and they have time to make their strategy before the actual contest starts.

The rules of the contest are:

1. The players sit in a circle, so that everybody sees everybody. Then the players are blindfolded.

2. On each player's head, either a red or a blue cap is placed. The colour of the cap is determined completely arbitrarily, e.g. by coin toss.

3. The blindfold is removed, and everybody has to write on a piece of paper the answer to the question "What is the colour of your cap?". The answer must be "RED", "BLUE" or "---". Everybody has to write down their answer at the same time.

4. Everybody shows the paper at the same time.

5. The players do not cheat. (They do not exchange information through words, utterances, signs, facial expressions, delays in writing their answer, etc.)

The procedure of the contest is done only once. The team wins the contest if at least one answer is correct and no answer is incorrect. "---" is considered a neutral answer, neither right nor wrong.

Examples:

if team member #12 correctly answers RED, and everybody else answers "---", they win.

if all members answer correctly (RED/BLUE), except for member #12 (who said RED and had blue), they lose.

Which is the strategy with the biggest chance to win, and how high is that chance?

Have fun!

[P.S.] For those who know Romanian, this and many other brainteasers are to be found at www.chichitza.com and www.chichitza.com/forum

As for chess, a section in English is www.chichitza.com/chess.html . It contains puzzles and studies. Some studies may be more difficult for computers than for humans

[Guest]

assume they are sitting in a circle.

with 5 we have the following combos.

BBBBB BBRRB BBRRR RRBRB

BBBBR BRBBR BRBRR RRRBB

BBBRB BRBRB RBBRR BRRRR

BBRBB BRRBB BRRBR RBRRR

BRBBB RBBBR RBRBR RRBRR

RBBBB RBBRB RRBBR RRRBR

BBBRR RBRBB BRRRB RRRRB

BBRBR RRBBB RBRRB RRRRR

if you see 4 of the same color, gueess that color

if you see 2 red, 2 blue, abstain.

if you see 3 of the same color, guess the oppisite color.

22/32 wins, 68.75%, is there a way to get it higher?

[k-man]

never mind...

Edited December 8, 2010 by k-man

[Guest]

I might not be 100%, but I'm onto it.

It's Hamming code.

There are two combinations you gotta know.

RRRRRRRRRRRRRRR

BBRBRRRBRRRRRRR

Well, really, those, and their exact opposites, IE:

BBBBBBBBBBBBBBB

RRBRBBBRBBBBBBB

If you look around the circle and everyone looks like one of those patterns, guess the opposite of what should be next. Otherwise, don't guess.

So, if you see the below, starting from your left and ending at you, you'd guess B.

RRRRRBBRBRRRBR_ (=> BBRBRRRBR_RRRRR)

Either one person gets it right or everyone gets it wrong.

The probability of it being correct is then 15/16, giving you a 93.75% of getting it right.

...Or something like that.

[bushindo]

I might not be 100%, but I'm onto it.

It's Hamming code.

There are two combinations you gotta know.

RRRRRRRRRRRRRRR

BBRBRRRBRRRRRRR

Well, really, those, and their exact opposites, IE:

BBBBBBBBBBBBBBB

RRBRBBBRBBBBBBB

If you look around the circle and everyone looks like one of those patterns, guess the opposite of what should be next. Otherwise, don't guess.

So, if you see the below, starting from your left and ending at you, you'd guess B.

RRRRRBBRBRRRBR_ (=> BBRBRRRBR_RRRRR)

Either one person gets it right or everyone gets it wrong.

The probability of it being correct is then 15/16, giving you a 93.75% of getting it right.

...Or something like that.

It is possible to get above 90%

This approach uses hamming code as well, but in a different manner.

First, let all the prisoners agree on the following hamming code matrix (image copied from wikipedia),

Given a random arrangement of the 16 hats (which we could imagine as a 16-dimensional vector of 0's and 1's), the chance that it satisfies the requirements of hamming code is 2⁴ = 1/16. This is because the hamming code basically assumes that 12 hats (or data as they call it) can independently vary, and the remaining 4 hats are linear combinations (error checking bits) of those 12. Our strategy is to bet against the possibility that the hamming requirement is actually true.

The strategy goes as follows:

1) During the game, everyone looks at the remaining 15 hats. From the hamming matrix, we can see that every person can evaluate the true/false state of 3 of 4 linear combinations. For instance, look at the person in column 1. He can evaluate the truth status of row 2,3, and 4. If we look at the person in column 3, he can evaluate the truth status of row 3 and 4, and do some linear algrebra on row 1 and 2 to get a third statement.

2) If a person gets 1 or more FALSE statement, abstain from guessing.

3) If a person gets 3 TRUE statements, then either the hamming code applies (probability 1/16), or that it doesn't apply and his hat is actually the opposite of what the code predicts (probability 15/16). In this case, the person should apply the hamming code to get his hat state, and then guess the OPPOSITE of it.

This should yield a winning rate of 15/16. One more observation is that if the hamming code requirement does not apply, there is bound to be at least 1 person who will get 3 TRUE statements. I haven't shown this yet, but I think it could be derived by looking at the null space of these individual truth/falsehood maps.

Edited December 9, 2010 by bushindo

[Guest]

It's a Hamming code.

The probability of it being correct is then 15/16, giving you a 93.75% of getting it right.

It is accomplished by guessing the opposite of what would constitute a valid codeword.

However, his approach to the actual code is new to me.

defining a parity check matrix H and computing the syndrome s = H*v' mod 2, where

v' is the column vector of hats, of which your hat is unknown, and

mod 2 is the modulo 2 operation.

As both said, the goal is to create an erroneous codeword, and to indicate the error (by exactly one not-abstaining team member).

If the codeword happens to be correct, everybody would think the error is at his position and would try to indicate it.

Furthermore, being a perfect code, this winning chance of 15/16 is the absolute maximum that could be accomplished.

Nice work Carbon1nTheRough!

[araver]

Allow me to present a close related solution/explanation for this problem, because of the following three arguments below (spoilers were needed for arguments too since they reference the posts above). I admit I was still searching for a solution but could not quite put my finger on it and I ceased to look for one and read the spoilers. I do not claim to have found a solution on my own, but I claim to not be entirely satisfied with the explanations I read above. I admire your insigths and I hope you won't mind my contribution to the topic, since it might reconcile some of your viewpoints (or at least provide some minor insights on the problem itself).

First of all, bushindo's and Kornrade's terminology in their solutions/explanations are not necessarily clear to all of us, since not all BrainDen readers are familiar with coding theory. Carbon1nTheRough's approach is correct in that the problem can be viewed as an application of the Hamming code, but most of the strategy/reasoning does not require the notion of Hamming code (except for constructional purposes). I like Coding Theory, understand Hamming code and the quick syndrome explanation/algorithm. I admit this solution has a certain elegance, however most of this problem can be solved/explained without resorting to these notions. Also refering to 16 hats is very confusing when reading your explanations since there are only 15 players.

Secondly, I think Carbon1nTheRough's solution is only partially correct / incomplete. He has a set of 4 static strings (000000000000000, 111111111111111, 110100010000000, 001011101111111). He includes shifting/rotation which yields 14+14=28 more strings (since 2 of his strings are impervious to rotation). A minimal base for a partition of the set of 2^15=32768 strings in radius-1 Hamming balls requires 2^(15-4)=2^11= 2048 strings (explanation in the proposed solution below). This makes his solution incomplete since there are many cases in which ALL would abstain because they don't see any such pattern around them. E.g. 1010101010101 (or the opposite). It is however possible to generate such a base starting from these strings and using both bitwise addition and multiplication (of which rotation/cyclic shift is a particular case). More to the point, constructing a cyclic code as an ideal in a certain ring (polynomial ring R = A[x] / (x^n - 1) where A is a finite field characteristic 2, more precisely A=F_2)

Thirdly, I think the reason why both bushindo and Kornrade don't see that they share the exact approach of Carbon1nTheRough is because of the cyclicity. Hamming code is presented in a form in which it does not seem (and isn't) cyclical, but it is closed under addition and can be used to generate a set of bases in the space of n-bit strings. Therefore one might find rotation/shift very counter-intuitive when thinking about the Hamming code since it generally presented as a linear code (hence Kornrade's syndrome explanation) and most of the equivalent forms presentation are not cyclic (although some are actually e.g. b1b2b3b4p134p123p234 for Hamming(7,4)).

A "meta" disclaimer first: Only specific notion I will use in this solution is the Hamming distance. I consider it's definition to be very natural for anyone, just labelling it with Hamming's name does not diminish its simplicity. IMHO Hamming was just the one to propose a practical use, the notion itself can be (re)discovered by any kindergarden child out there. Albeit a smart not-easily-bored kindergarden child

Hamming distance between 2 n-bit long strings is the number of positions where the bits at which the corresponding symbols are different or equivalently, the minimum number of substitutions required to change one string into the other.

It it straightforward that for each n-bit string, there are n other strings at Hamming distance 1. These different strings are obtained by flipping exactly one bit from the original string. These strings form a ball of radius 1 around the original string. Therefore, radius-1 balls have n+1 strings (including the original word).

For n=2^m-1 (n=3,7,15,31,63..) a nice statement holds: "The set of n-bit strings can be partitioned in radius-1 balls".

Key point in this is that the number of n-bit strings is 2^n and a radius-1 ball has n+1=2^m strings. Since 2^m is a divisor of 2^n, if you manage to find 2^(n-m) radius-1 balls which don't overlap, there is no string left outside of these balls.

Several key notes can be made on the composition of A:

1) The 2 centers cannot be at distance 1 from one another i.e. one "graviting" around another one since the radius-1 balls around each other would collide.

2) Moreover, since the balls don't touch, two centers cannot be at distance 2 from one another. In that case, the balls would share at least a string (two strings in fact) that can be found in the middle of the two-step flipping transition which gets us from one center to another (definition of distance 2).

3) Two centers cannot be too much apart either or more precisely, for each center there must be at least one center at ditance 3 from it (for n>=2). Just imagine center A - a string B gravitating around A (at distance 1) and a string C obtained by flipping another bit from B (not the one that differentiates between A and B). Distance between A and C is 2 so C is not a center. However, C must gravitate around a center since this a partition after all.

Finding such a set A falls out of the scope of this solution. It does exist. The next spoiler presents some thoughts on how one can construct such a set of non-overlapping 2^(n-m) balls or equivalently how to find a set A of 2^(n-m) centers.

Returning to our problem, we have n=15=2^4-1 people in a circle. Because n=2^m-1, there exists a Hamming partition with radius-1 balls. Assume they all agree on one such partition beforehand and denote A the set of centers. Assume they also agree on a convention beforehand e.g. 0=Blue, 1=Red.

It is also crucial in the following that they all agree on a leader/starting position beforehand.

Each sees 14 bits from the others hats so each can form 2 different 15-bit strings (starting from the predetermined leader) by considering both possibilities of their own bit. Let's denote them a (with 0 in your position) and b (with 1 in your position) . It is trivial that a and b are at Hamming distance 1. Then there are only 2 possibilities:

1) Either a or b belongs to A in which case the other one is graviting around it in the Hamming partition.

2) Neither a nor b belong to A in which case they are both graviting around two different centers (at distance 3 from one another, as seen above).

Assume the following strategy/algorithm for each person:

Strategy A.

Step 1. Compute a and b from the 14 bits you see.

Step 2. If neither a nor b belong to A - ABSTAIN else go to step 3.

Step 3. Exactly one of a and b belong to A, so choose the one that doesn't belong to A. 

        Assume this is true distribution and say the colour that corresponds to that distribution 

        (the colour on your position in that string). So choose 0=Blue if a is in A and 1=Red if b is in A. 

Denote the actual distribution of the hats as the n-bit string d. To compute the chances of success, note that there are only two cases: Case 1) If the distribution of the hats is in A, when computing a and b, they would all choose the wrong colour in Step 3. Case 2) If the distribution of the hats is not in A, then it is graviting around a center in A. Denote with c the string in A at Hamming distance 1 from the actual distribution that is in A. Denote i the position in which the distribution of hats and c differs. The person in position i can clearly compute in Step 1 a_i=c (in A) and b_i=d. So in step 3 he chooses (correctly) d avoiding the centers in A. The other persons compute similar a_j and b_j. The trick is that one of them is d (which is not in A) and the other differs by d in one position different than i. Let's call this other one as candidate alpha. Now, alpha cannot be in A since it is not c (which is different than d on position i and i is not equal to j) and both alpha and c being in A would mean their balls both share d, which is impossible in a radius-1 ball partition. Therefore, since neither d nor alpha is in A, they would choose in Step 2 to abstain. Since exactly one person votes correctly and the rest abstain, the game is won. Note that there are 2^n possible strings each with equal probability to be the actual distribution in the contest, of which 2^(n-m) are in A (remember n=2^m-1) and the other 2^n-2^(n-m) aren't. Therefore the winning probability is [2^n-2^(n-m)]/2^n = 1-1/2^m. For n=15, m=1 this means 15/16=93.75%, which may seem surprising or counter-intuitive at first. Winning with this deterministic strategy is possible because of the beauty of the Hamming partition itself.

The key element in this perfect-strategy is that any set A / any Hamming partition established beforehand by the players will do. Arriving at such a set A can be done: I) Either by exhaustive tables shared by all members before hand. (for n=15, 2^(n-m)=2048 strings). Granted sharing/memorizing so much information before hand is a stretch. II) Sharing a seed/generator and a generating mechanism of A. Memorizing the seed and generation mechanism allows each player to recompute all A's elements in O(2^(n-m)) time and then use them in III) Sharing a particular property of elements in A such that a quick algorithm (optimal would be O(n)) exists for determining if a string is in A. Comments: - I personally don't like approaches of type I, but they do work. And their complexity is O(2^(n-m)) since two lookups in the table are required in step 2 of the strategy. - bushindo's and Kornrade's solutions are based on Hamming codes as a generating mechanism that allows a quick algorithm (O(n)) for determining if a string is in A. Excellent choice indeed, but setting for a particular Hamming codes-presentation such as the one in Wikipedia (presentation = choosing the parity bits' positions in the string e.g. as 1,2,4,8 as in the wikipedia classical definition and how these bits are computed) doesn't cover all solutions. In particular, choosing a presentation means choosing a way to compute the parity bits (and a particular position of them, but this is resolved by shifting so only the relative distances between the parity bits' positions determine a unique Hamming code-presentation). All Hamming partitions determine a Hamming code (with a different presentation). So, a type III set A construction is the following (algebraic relations for the elegant algorithm for constructing a particular Hamming code

presented by Wikipedia): - For each 15-bit string a denote a1...a15 it's bits. - Choose A such that all the bits except a1, a2, a4 and a8 can be chosen freely and bits a1,a2,a4,a8 are bound to the following equations:

a1=a3+a5+a7+a9+a11+a13+a15

a2=a3+a6+a7+a10+a11+a14+a15

a4=a5+a6+a7+a12+a13+a14+a15

a8=a9+a10+a11+a12+a13+a14+a15

Visual matrix representation:

   a1	a2	a3	a4	a5	a6	a7	a8	a9	a10    a11	a12	a13	a14	a15

a1  		X		X		X		X		X		X		X	

a2  	 	X			X	X			X	X			X	X	

a4  			 	X	X	X					X	X	X	X	

a8	    						 	X	X	X	X	X	X	X	

- Approaches of type II are what Carbon1nTheRough had in mind. Choose a minimum number of seeds (11010001000000 in his case, which is actual easy to remember 1 if position is a power of 2 and 0 otherwise) and choose addition between elements in A and multiplication between one element in A and any other element as generating mechanisms i.e. generating a cyclic code as an ideal in a certain ring. As I said, choosing rotation/cyclic shift as a generating mechanism is not enough since rotation/cyclic shift is only multiplication by a particular element - polynomial p(X)=X or 0100..00. So you basically need at least an additive group (e.g. additive group generated by 4 strings with only one bit as 1, on positions 1,2,4 and 8) as seeds and then allow for full-multiplication (modulo 2) to grow/generate the set A. Rotation/cyclic shift is not sufficient.

I think the different viewpoints come from different interpretations for the n=3 case. n=3=2^2-1 so 2 balls are in the Hamming partition. There are also 2-partitions of the same space which do not follow construction by Hamming distance one of which is given as example.

The following are different 2-partitions with a "center (set of elements graviting the center)" notation for Hamming :

- Linear/Hamming: 000 (100, 010, 001) and 111 (011, 101, 110).

- Cyclic partition: (110, 101, 011, 000) and mirror (001, 010, 110, 111).

All Hamming codes are notorios to being closed under addition (as any linear code) and although not all Hamming code presentations are cyclic themselves, they are equivalent to a Hamming code presentation that is a cyclic code.

In my opinion, the cyclic view is much harder to grasp for n>3. Although such a cyclic partition does exist (as Hamming codes are equivalent to a cyclic code), it's not that simple as choosing a minimal seed and reconstructing the rest with rotation/mirroring/addition as it looks like for n=3.

For n=7, one can indeed construct such a (cyclic) set easily (roughly following Carbon1nTheRough ideas) using mirroring and rotation. For n=15 and above, I don't see an easy construction (for n=15, a partition has 2048 elements so less than log(2048) would sound as a nice seed set).

I personally like a star/planets analogy view on Hamming partitions which I will use in the following. Assume a finite universe of size 2^n in which all points are either stars or planets. All centers in the Hamming partition are stars and all points not in A are planets which revolve around exactly one star.

Recall some of the previous notes on how centers in A relate to one another:

1) (Local sparsity) Two centers are at a distance of at least 2 from one another: The 2 centers cannot be at distance 1 from one another i.e. one "graviting" around another one since the radius-1 balls around each other would collide. Moreover, since the balls don't touch, two centers cannot be at distance 2 from one another. In that case, the balls would share at least a string (two strings in fact) that can be found in the middle of the two-step flipping transition which gets us from one center to another (definition of distance 2).

2) (Global density) Two centers cannot be too much apart either or more precisely, for each center there must be at least one center at distance 3 from it (for n>=2). Just imagine center A - a string B gravitating around A (at distance 1) and a string C obtained by flipping another bit from B (not the one that differentiates between A and B). Distance between A and C is 2 so C is not a center. However, C must gravitate around a center since this a partition after all.

3) The Hamming distance is also a metric on the n-bit space - the triangle inequality d(A,C) <= d(A,B) + d(B,C) holds for the Hamming distance. It's easy to see that equality is reached if and only if the set of positions in which A and B are different is disjoint from the set of positions in which B and C are different.

So, starting from s=null-string which has 0 1-bits (call it our Sun), we find all strings with 1 1-bit graviting around this center (call them planets) and the all 2 1-bit strings (planets in another solar system) graviting around other centers (stars). Since these neighbor stars cannot have one 1-bit, then reaching them from one of the 2 1-bit planets means flipping one of the other bits from them - a bit which is 0 for planets. Hence these neighboring stars have 3 1-bits = are at distance 3 from our sun (seed).

However not all 3-bit strings can be stars since for example 11100..0 and 01110..0 are at distance 2 from one another.

Choosing a set of stars from these 3-bit strings is certainly not unique, since rotation/shifting for example can lead to alternative partitions. There are nC3 combinations of 3 1-bit strings.

First, let's see how many we need. For n=7, m=3 so we need 2^(7-3)=16 stars in A.

Taking s=0000000 and non-s=1111111 in A, 14 pairs remain. nC3=7C3=7*6*5/2*3=35 points at distance 3 from s. Similarly, only 35 points have 4 1-bits and thus lie at distance 3 from non-s and therefore distance n-3=4 from s. It is then clear that the only stars other than s and non-s must lie at either distance 3 or 4 from s, otherwise they would be too close from s or non-s. The symmetry involved in the Hamming hypercube shows that there are as many stars at distance 3 from s as stars at distance 4 from non-s so 14/2=7=n stars are in each category. Moreover, choosing 7 stars at distance 3 from s (which lie at least at distance 3 from each other) forces us to consider their mirrors as the other set of stars.

Note that if you get lucky and choose a stars whose rotations are all at distance at least 3 from one another, your job is finished since there are 7 rotations possible. Since these are stars with 3 1-bit, achieving a distance of at least 3 means that when rotating, no more than 1 pair of these 3 1-bits can overlap (2 pairs of 1-bits overlapping determine a Hamming distance of 2 - remaining 1-bits can be flipped to go from one star to another - as seen in the following counter example: 1110000 and 01110000).

A beautiful (easier to prove) seed for the 3-bit stars is the one involved in all strategies in the other posts - one in which the 1-bits are on positions that are powers of 2. For n=3 this means 1101000.

So, for n=3 a simple set A can be found by taking s=0000000, p=1101000, all the strings that can be obtained from p by shifting (1+1+6=8 so far) and all their mirror strings (totaling 16 so far).

For n=15 the problem is not that simple. Consider Carbon1nTheRough's partial solution. He chooses s=000000000000000, p=110100010000000 and their mirrors and cyclic shifts (because he does not consider a predetermined fixed position i.e. a leader). Problem is that d(s,p)=4 and no shifting modifies the number of 1's (1-bits) in a string. So there is no star at distance 3 from s which contradicts the Global density property of Hamming partitions. Therefore it is at best incomplete/partial in achieving a Hamming code/Hamming partition, no matter how you look at it.

For n=15, I do not see such an easy-to-explain construction using mirroring/shifting and maybe addition (n=15=2^4-1, m=4, 2^(n-m)=2^11=2048 stars needed). From an algebraic point of view, a binary linear cyclic code can be generated by the polynomial g(x)=1+x+x^4.

Completely classifying/constructing 1-error correcting codes of length n is not so simple as it may seem. If one defines two codes to be equivalent if one can turn one code into the other by permuting the coordinates and adding a constant vector, then characterization of equivalence clases is non-trivial for n>=15. For example there are 5983 non-equivalent perfect codes of length 15 (while there is a unique perfect code for n=3, n=7). Several recent results can be found here and here . n=31 is still an open challenge I think.

Edited December 9, 2010 by araver

[Guest]

Yeah, araver pretty much nailed mine down. I tested what I did on a team of 3 and 7 people and it worked, so I just kinda threw it out there for 15. Way too lazy to do all that math. But, kudos to the rest of you.

[superprismatic]

Allow me to present a close related solution/explanation for this problem, because of the following three arguments below (spoilers were needed for arguments too since they reference the posts above). I admit I was still searching for a solution but could not quite put my finger on it and I ceased to look for one and read the spoilers. I do not claim to have found a solution on my own, but I claim to not be entirely satisfied with the explanations I read above. I admire your insigths and I hope you won't mind my contribution to the topic, since it might reconcile some of your viewpoints (or at least provide some minor insights on the problem itself).

First of all, bushindo's and Kornrade's terminology in their solutions/explanations are not necessarily clear to all of us, since not all BrainDen readers are familiar with coding theory. Carbon1nTheRough's approach is correct in that the problem can be viewed as an application of the Hamming code, but most of the strategy/reasoning does not require the notion of Hamming code (except for constructional purposes). I like Coding Theory, understand Hamming code and the quick syndrome explanation/algorithm. I admit this solution has a certain elegance, however most of this problem can be solved/explained without resorting to these notions. Also refering to 16 hats is very confusing when reading your explanations since there are only 15 players.

Secondly, I think Carbon1nTheRough's solution is only partially correct / incomplete. He has a set of 4 static strings (000000000000000, 111111111111111, 110100010000000, 001011101111111). He includes shifting/rotation which yields 14+14=28 more strings (since 2 of his strings are impervious to rotation). A minimal base for a partition of the set of 2^15=32768 strings in radius-1 Hamming balls requires 2^(15-4)=2^11= 2048 strings (explanation in the proposed solution below). This makes his solution incomplete since there are many cases in which ALL would abstain because they don't see any such pattern around them. E.g. 1010101010101 (or the opposite). It is however possible to generate such a base starting from these strings and using both bitwise addition and multiplication (of which rotation/cyclic shift is a particular case). More to the point, constructing a cyclic code as an ideal in a certain ring (polynomial ring R = A[x] / (x^n - 1) where A is a finite field characteristic 2, more precisely A=F_2)

Thirdly, I think the reason why both bushindo and Kornrade don't see that they share the exact approach of Carbon1nTheRough is because of the cyclicity. Hamming code is presented in a form in which it does not seem (and isn't) cyclical, but it is closed under addition and can be used to generate a set of bases in the space of n-bit strings. Therefore one might find rotation/shift very counter-intuitive when thinking about the Hamming code since it generally presented as a linear code (hence Kornrade's syndrome explanation) and most of the equivalent forms presentation are not cyclic (although some are actually e.g. b1b2b3b4p134p123p234 for Hamming(7,4)).

A "meta" disclaimer first: Only specific notion I will use in this solution is the Hamming distance. I consider it's definition to be very natural for anyone, just labelling it with Hamming's name does not diminish its simplicity. IMHO Hamming was just the one to propose a practical use, the notion itself can be (re)discovered by any kindergarden child out there. Albeit a smart not-easily-bored kindergarden child

Hamming distance between 2 n-bit long strings is the number of positions where the bits at which the corresponding symbols are different or equivalently, the minimum number of substitutions required to change one string into the other.

It it straightforward that for each n-bit string, there are n other strings at Hamming distance 1. These different strings are obtained by flipping exactly one bit from the original string. These strings form a ball of radius 1 around the original string. Therefore, radius-1 balls have n+1 strings (including the original word).

For n=2^m-1 (n=3,7,15,31,63..) a nice statement holds: "The set of n-bit strings can be partitioned in radius-1 balls".

Key point in this is that the number of n-bit strings is 2^n and a radius-1 ball has n+1=2^m strings. Since 2^m is a divisor of 2^n, if you manage to find 2^(n-m) radius-1 balls which don't overlap, there is no string left outside of these balls.

Several key notes can be made on the composition of A:

1) The 2 centers cannot be at distance 1 from one another i.e. one "graviting" around another one since the radius-1 balls around each other would collide.

2) Moreover, since the balls don't touch, two centers cannot be at distance 2 from one another. In that case, the balls would share at least a string (two strings in fact) that can be found in the middle of the two-step flipping transition which gets us from one center to another (definition of distance 2).

3) Two centers cannot be too much apart either or more precisely, for each center there must be at least one center at ditance 3 from it (for n>=2). Just imagine center A - a string B gravitating around A (at distance 1) and a string C obtained by flipping another bit from B (not the one that differentiates between A and B). Distance between A and C is 2 so C is not a center. However, C must gravitate around a center since this a partition after all.

Finding such a set A falls out of the scope of this solution. It does exist. The next spoiler presents some thoughts on how one can construct such a set of non-overlapping 2^(n-m) balls or equivalently how to find a set A of 2^(n-m) centers.

Returning to our problem, we have n=15=2^4-1 people in a circle. Because n=2^m-1, there exists a Hamming partition with radius-1 balls. Assume they all agree on one such partition beforehand and denote A the set of centers. Assume they also agree on a convention beforehand e.g. 0=Blue, 1=Red.

It is also crucial in the following that they all agree on a leader/starting position beforehand.

Each sees 14 bits from the others hats so each can form 2 different 15-bit strings (starting from the predetermined leader) by considering both possibilities of their own bit. Let's denote them a (with 0 in your position) and b (with 1 in your position) . It is trivial that a and b are at Hamming distance 1. Then there are only 2 possibilities:

1) Either a or b belongs to A in which case the other one is graviting around it in the Hamming partition.

2) Neither a nor b belong to A in which case they are both graviting around two different centers (at distance 3 from one another, as seen above).

Assume the following strategy/algorithm for each person:

Strategy A.
Step 1. Compute a and b from the 14 bits you see.
Step 2. If neither a nor b belong to A - ABSTAIN else go to step 3.
Step 3. Exactly one of a and b belong to A, so choose the one that doesn't belong to A.
Assume this is true distribution and say the colour that corresponds to that distribution
(the colour on your position in that string). So choose 0=Blue if a is in A and 1=Red if b is in A.

Denote the actual distribution of the hats as the n-bit string d. To compute the chances of success, note that there are only two cases: Case 1) If the distribution of the hats is in A, when computing a and b, they would all choose the wrong colour in Step 3. Case 2) If the distribution of the hats is not in A, then it is graviting around a center in A. Denote with c the string in A at Hamming distance 1 from the actual distribution that is in A. Denote i the position in which the distribution of hats and c differs. The person in position i can clearly compute in Step 1 a_i=c (in A) and b_i=d. So in step 3 he chooses (correctly) d avoiding the centers in A. The other persons compute similar a_j and b_j. The trick is that one of them is d (which is not in A) and the other differs by d in one position different than i. Let's call this other one as candidate alpha. Now, alpha cannot be in A since it is not c (which is different than d on position i and i is not equal to j) and both alpha and c being in A would mean their balls both share d, which is impossible in a radius-1 ball partition. Therefore, since neither d nor alpha is in A, they would choose in Step 2 to abstain. Since exactly one person votes correctly and the rest abstain, the game is won. Note that there are 2^n possible strings each with equal probability to be the actual distribution in the contest, of which 2^(n-m) are in A (remember n=2^m-1) and the other 2^n-2^(n-m) aren't. Therefore the winning probability is [2^n-2^(n-m)]/2^n = 1-1/2^m. For n=15, m=1 this means 15/16=93.75%, which may seem surprising or counter-intuitive at first. Winning with this deterministic strategy is possible because of the beauty of the Hamming partition itself.

The key element in this perfect-strategy is that any set A / any Hamming partition established beforehand by the players will do. Arriving at such a set A can be done: I) Either by exhaustive tables shared by all members before hand. (for n=15, 2^(n-m)=2048 strings). Granted sharing/memorizing so much information before hand is a stretch. II) Sharing a seed/generator and a generating mechanism of A. Memorizing the seed and generation mechanism allows each player to recompute all A's elements in O(2^(n-m)) time and then use them in III) Sharing a particular property of elements in A such that a quick algorithm (optimal would be O(n)) exists for determining if a string is in A. Comments: - I personally don't like approaches of type I, but they do work. And their complexity is O(2^(n-m)) since two lookups in the table are required in step 2 of the strategy. - bushindo's and Kornrade's solutions are based on Hamming codes as a generating mechanism that allows a quick algorithm (O(n)) for determining if a string is in A. Excellent choice indeed, but setting for a particular Hamming codes-presentation such as the one in Wikipedia (presentation = choosing the parity bits' positions in the string e.g. as 1,2,4,8 as in the wikipedia classical definition and how these bits are computed) doesn't cover all solutions. In particular, choosing a presentation means choosing a way to compute the parity bits (and a particular position of them, but this is resolved by shifting so only the relative distances between the parity bits' positions determine a unique Hamming code-presentation). All Hamming partitions determine a Hamming code (with a different presentation). So, a type III set A construction is the following (algebraic relations for the elegant algorithm for constructing a particular Hamming code

presented by Wikipedia): - For each 15-bit string a denote a1...a15 it's bits. - Choose A such that all the bits except a1, a2, a4 and a8 can be chosen freely and bits a1,a2,a4,a8 are bound to the following equations:

a1=a3+a5+a7+a9+a11+a13+a15
a2=a3+a6+a7+a10+a11+a14+a15
a4=a5+a6+a7+a12+a13+a14+a15
a8=a9+a10+a11+a12+a13+a14+a15

Visual matrix representation:

a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 a13 a14 a15
a1 X X X X X X X
a2 X X X X X X X
a4 X X X X X X X
a8 X X X X X X X

- Approaches of type II are what Carbon1nTheRough had in mind. Choose a minimum number of seeds (11010001000000 in his case, which is actual easy to remember 1 if position is a power of 2 and 0 otherwise) and choose addition between elements in A and multiplication between one element in A and any other element as generating mechanisms i.e. generating a cyclic code as an ideal in a certain ring. As I said, choosing rotation/cyclic shift as a generating mechanism is not enough since rotation/cyclic shift is only multiplication by a particular element - polynomial p(X)=X or 0100..00. So you basically need at least an additive group (e.g. additive group generated by 4 strings with only one bit as 1, on positions 1,2,4 and 8) as seeds and then allow for full-multiplication (modulo 2) to grow/generate the set A. Rotation/cyclic shift is not sufficient.

I think the different viewpoints come from different interpretations for the n=3 case. n=3=2^2-1 so 2 balls are in the Hamming partition. There are also 2-partitions of the same space which do not follow construction by Hamming distance one of which is given as example.

The following are different 2-partitions with a "center (set of elements graviting the center)" notation for Hamming :

- Linear/Hamming: 000 (100, 010, 001) and 111 (011, 101, 110).

- Cyclic partition: (110, 101, 011, 000) and mirror (001, 010, 110, 111).

All Hamming codes are notorios to being closed under addition (as any linear code) and although not all Hamming code presentations are cyclic themselves, they are equivalent to a Hamming code presentation that is a cyclic code.

In my opinion, the cyclic view is much harder to grasp for n>3. Although such a cyclic partition does exist (as Hamming codes are equivalent to a cyclic code), it's not that simple as choosing a minimal seed and reconstructing the rest with rotation/mirroring/addition as it looks like for n=3.

For n=7, one can indeed construct such a (cyclic) set easily (roughly following Carbon1nTheRough ideas) using mirroring and rotation. For n=15 and above, I don't see an easy construction (for n=15, a partition has 2048 elements so less than log(2048) would sound as a nice seed set).

I personally like a star/planets analogy view on Hamming partitions which I will use in the following. Assume a finite universe of size 2^n in which all points are either stars or planets. All centers in the Hamming partition are stars and all points not in A are planets which revolve around exactly one star.

Recall some of the previous notes on how centers in A relate to one another:

1) (Local sparsity) Two centers are at a distance of at least 2 from one another: The 2 centers cannot be at distance 1 from one another i.e. one "graviting" around another one since the radius-1 balls around each other would collide. Moreover, since the balls don't touch, two centers cannot be at distance 2 from one another. In that case, the balls would share at least a string (two strings in fact) that can be found in the middle of the two-step flipping transition which gets us from one center to another (definition of distance 2).

2) (Global density) Two centers cannot be too much apart either or more precisely, for each center there must be at least one center at distance 3 from it (for n>=2). Just imagine center A - a string B gravitating around A (at distance 1) and a string C obtained by flipping another bit from B (not the one that differentiates between A and B). Distance between A and C is 2 so C is not a center. However, C must gravitate around a center since this a partition after all.

3) The Hamming distance is also a metric on the n-bit space - the triangle inequality d(A,C) <= d(A,B) + d(B,C) holds for the Hamming distance. It's easy to see that equality is reached if and only if the set of positions in which A and B are different is disjoint from the set of positions in which B and C are different.

So, starting from s=null-string which has 0 1-bits (call it our Sun), we find all strings with 1 1-bit graviting around this center (call them planets) and the all 2 1-bit strings (planets in another solar system) graviting around other centers (stars). Since these neighbor stars cannot have one 1-bit, then reaching them from one of the 2 1-bit planets means flipping one of the other bits from them - a bit which is 0 for planets. Hence these neighboring stars have 3 1-bits = are at distance 3 from our sun (seed).

However not all 3-bit strings can be stars since for example 11100..0 and 01110..0 are at distance 2 from one another.

Choosing a set of stars from these 3-bit strings is certainly not unique, since rotation/shifting for example can lead to alternative partitions. There are nC3 combinations of 3 1-bit strings.

First, let's see how many we need. For n=7, m=3 so we need 2^(7-3)=16 stars in A.

Taking s=0000000 and non-s=1111111 in A, 14 pairs remain. nC3=7C3=7*6*5/2*3=35 points at distance 3 from s. Similarly, only 35 points have 4 1-bits and thus lie at distance 3 from non-s and therefore distance n-3=4 from s. It is then clear that the only stars other than s and non-s must lie at either distance 3 or 4 from s, otherwise they would be too close from s or non-s. The symmetry involved in the Hamming hypercube shows that there are as many stars at distance 3 from s as stars at distance 4 from non-s so 14/2=7=n stars are in each category. Moreover, choosing 7 stars at distance 3 from s (which lie at least at distance 3 from each other) forces us to consider their mirrors as the other set of stars.

Note that if you get lucky and choose a stars whose rotations are all at distance at least 3 from one another, your job is finished since there are 7 rotations possible. Since these are stars with 3 1-bit, achieving a distance of at least 3 means that when rotating, no more than 1 pair of these 3 1-bits can overlap (2 pairs of 1-bits overlapping determine a Hamming distance of 2 - remaining 1-bits can be flipped to go from one star to another - as seen in the following counter example: 1110000 and 01110000).

A beautiful (easier to prove) seed for the 3-bit stars is the one involved in all strategies in the other posts - one in which the 1-bits are on positions that are powers of 2. For n=3 this means 1101000.

So, for n=3 a simple set A can be found by taking s=0000000, p=1101000, all the strings that can be obtained from p by shifting (1+1+6=8 so far) and all their mirror strings (totaling 16 so far).

For n=15 the problem is not that simple. Consider Carbon1nTheRough's partial solution. He chooses s=000000000000000, p=110100010000000 and their mirrors and cyclic shifts (because he does not consider a predetermined fixed position i.e. a leader). Problem is that d(s,p)=4 and no shifting modifies the number of 1's (1-bits) in a string. So there is no star at distance 3 from s which contradicts the Global density property of Hamming partitions. Therefore it is at best incomplete/partial in achieving a Hamming code/Hamming partition, no matter how you look at it.

For n=15, I do not see such an easy-to-explain construction using mirroring/shifting and maybe addition (n=15=2^4-1, m=4, 2^(n-m)=2^11=2048 stars needed). From an algebraic point of view, a binary linear cyclic code can be generated by the polynomial g(x)=1+x+x^4.

Completely classifying/constructing 1-error correcting codes of length n is not so simple as it may seem. If one defines two codes to be equivalent if one can turn one code into the other by permuting the coordinates and adding a constant vector, then characterization of equivalence clases is non-trivial for n>=15. For example there are 5983 non-equivalent perfect codes of length 15 (while there is a unique perfect code for n=3, n=7). Several recent results can be found here and here . n=31 is still an open challenge I think.

Thanks, araver, I was confused by the solution comments made by

Carbon1nTheRough, bushindo, and Kornrade. They obviously understood

something which I missed somewhere along the line. I very much appreciate

your excellent explanation. I now understand the other's comments on

solution. I also wish to thank Kornrade for this beautiful problem.

But without your lengthy explanation, araver, I would be spending at

least several more hours pondering this (possibly without success).

[Guest]

With the explanations of this puzzle, Bushido's and possibly others, it seems that almost all perspectives on block coding have been covered

He who understood all this can easily pass a mid-term exam at the university

[CaptainEd]

Thank you, Bonanova and K-man! It took me several readings of Bonanova's explanation before I could get into the right mindset, and understand why one person's 50% chance of being right is irrelevant to the team's ability to win in most cases (most wrong guesses are wasted together on only a few team events, while all the right guesses are spread across all the rest of the team events). Thank you for that illumination.

Then, K-man points to the incredible power of the Hamming distance and Hamming codes to improve the team's ability to an astounding degree! Also very educational.

[CaptainEd]

Sorry folks, the note above (#61) was intended for the simpler, more recent post (), which was the first I had ever heard of this stuff.

In this case, I need to give thanks in profusion to araver, Bushindo and CarbonInTheRough for the education on Hamming distance and Hamming code.

Edited August 8, 2011 by CaptainEd

[bonanova]

My take on araver's discussion is that earlier solutions did not adequately rule out cases where everyone would abstain.

That point, I could not see had been covered.

In my that point was clear, because the 8 cases could easily be enumerated.

[bushindo]

My take on araver's discussion is that earlier solutions did not adequately rule out cases where everyone would abstain.

That point, I could not see had been covered.

In my that point was clear, because the 8 cases could easily be enumerated.

Here's a discussion of why the 15 people won't all abstain during the same turn.

So, let's index the 15 people from with numbers from 1 to 15. Let the hat color be represented by 1's and 0's. In the hamming code solution, we essentially assume that 11 people are the 'data' (encoded by d_i in the following table), and the other 4 people are the 'error checking bits' (encoded by p_i).

So, according to the chart above, we are assuming that in modulo 2 arithmetics,

p_1 = d_1 + d_2 + d_4 + d_5 + d_7 + d9 + d_11

p_2 = d_1 + d_3 + d_4 + d_5 + d_7 + d_10 + d_11

...

p_8 = ..

So, the 15 people in the game are assuming that p_1, p_2, p_4, and p_8 follow the 4 equations above. Let's enumerate the cases, and show that none of those cases result in everyone abstaining

a) p_1 to p_8 follow the hamming encoding equation (the probability of this happening is 1/16). Following the rules of the solution, all 15 would successfully solve for their hat color assuming that the hamming encoding rules are true. All 15 would then simultaneously guess the opposite color. Everybody lose.

b) one of the 4 error checking people (p_i) has the opposite bit of what the hamming encoding rule says. p_i would then be able to calculate his hat color from the rules, and the guess the opposite of it. Everybody else would abstain because they would realize the encoding assumption doesn't apply. Everybody win.

c) two of the 4 error people (p_i and p_j) have the opposite bit of what the encoding rule says. Looking at the data table, there is a data person (d_i) whose column includes precisely the two people with error. This data person would then be able to calculate this hat and guess the opposite of it. For instance, let's say that p_1 and p_2 have the opposite bits of the encoding rules. The data person d_1 would then be able to correctly guess his hat color. Everybody win

d) 3 of the 4 error people have the opposite bit of what the encoding rule says. Looking at the data table, there is a data person (d_i) whose column includes precisely the three people with error. For instance, let's say that p_1, p_2, and p_4 dont follow the encoding rules. Then the data person d_4 would raise his hand and guess correctly. Everybody win

e) Let's say all 4 error checking people's hats don't follow the encoding rule. The data person d_11 would then correctly guess his hat color. Everybody win

Note that there are 6 data people that each covers two error checking people (d_1, d_2, d_3, d_5, etc. ). There are 4 data people that each covers three error checking people, and 1 data person (d_11) that covers all four. It is no accident that these numbers are precisely ₄C₂, ₄C₃, and ₄C₁, and they add together to form 11.

Edited August 15, 2011 by bushindo

[bushindo]

Here's a discussion of why the 15 people won't all abstain during the same turn.

So, let's index the 15 people from with numbers from 1 to 15. Let the hat color be represented by 1's and 0's. In the hamming code solution, we essentially assume that 11 people are the 'data' (encoded by d_i in the following table), and the other 4 people are the 'error checking bits' (encoded by p_i).

So, according to the chart above, we are assuming that in modulo 2 arithmetics,

p_1 = d_1 + d_2 + d_4 + d_5 + d_7 + d9 + d_11

p_2 = d_1 + d_3 + d_4 + d_5 + d_7 + d_10 + d_11

...

p_8 = ..

So, the 15 people in the game are assuming that p_1, p_2, p_4, and p_8 follow the 4 equations above. Let's enumerate the cases, and show that none of those cases result in everyone abstaining

a) p_1 to p_8 follow the hamming encoding equation (the probability of this happening is 1/16). Following the rules of the solution, all 15 would successfully solve for their hat color assuming that the hamming encoding rules are true. All 15 would then simultaneously guess the opposite color. Everybody lose.

b) one of the 4 error checking people (p_i) has the opposite bit of what the hamming encoding rule says. p_i would then be able to calculate his hat color from the rules, and the guess the opposite of it. Everybody else would abstain because they would realize the encoding assumption doesn't apply. Everybody win.

c) two of the 4 error people (p_i and p_j) have the opposite bit of what the encoding rule says. Looking at the data table, there is a data person (d_i) whose column includes precisely the two people with error. This data person would then be able to calculate this hat and guess the opposite of it. For instance, let's say that p_1 and p_2 have the opposite bits of the encoding rules. The data person d_1 would then be able to correctly guess his hat color. Everybody win

d) 3 of the 4 error people have the opposite bit of what the encoding rule says. Looking at the data table, there is a data person (d_i) whose column includes precisely the three people with error. For instance, let's say that p_1, p_2, and p_4 dont follow the encoding rules. Then the data person d_4 would raise his hand and guess correctly. Everybody win

e) Let's say all 4 error checking people's hats don't follow the encoding rule. The data person d_11 would then correctly guess his hat color. Everybody win

Note that there are 6 data people that each covers two error checking people (d_1, d_2, d_3, d_5, etc. ). There are 4 data people that each covers three error checking people, and 1 data person (d_11) that covers all four. It is no accident that these numbers are precisely ₄C₂, ₄C₃, and ₄C₁, and they add together to form 11.

Minor correction to the last paragraph in the spoiler.

Note that there are 6 data people that each covers two error checking people (d_1, d_2, d_3, d_5, etc. ). There are 4 data people that each covers three error checking people, and 1 data person (d_11) that covers all four. It is no accident that these numbers are precisely ₄C₂, ₄C₃, and ₄C₄, and they add together to form 11.

[Guest]

The rules of the contest are:

1. The players sit in a circle, so that everybody sees everybody. Then the players are blindfolded.

2. On each player's head, either a red or a blue cap is placed. The colour of the cap is determined completely arbitrarily, e.g. by coin toss.

3. The blindfold is removed, and everybody has to write on a piece of paper the answer to the question "What is the colour of your cap?". The answer must be "RED", "BLUE" or "---". Everybody has to write down their answer at the same time.

4. Everybody shows the paper at the same time.

5. The players do not cheat. (They do not exchange information through words, utterances, signs, facial expressions, delays in writing their answer, etc.)

The odds are 50% for any individual.

If 1 is elected and everyone else puts --- then the teams odds raise greatly to 50%.

Since no information can be exchanged and the team can not see the order the hats are selected or placed it is impossible for the odds to be above 50%

Example, everyone is assuming the following.

A. that all hats are selected with the same arbitrary (e.g. single coin repeatedly tossed by one person)

B. the hats are picked and placed in a clockwise or counter-clockwise order.

C. the elected member knows that they are in a good position to gain odds on probability.

Breaks that destroy the odds.

A. multiple persons using multiple arbitrary for selection (e.g. 15 people with 15 coins flipping and placing the hats, in other words 100% random pattern)

B. hats could have been done in any order and since the team is blindfolded would not likely know.

C. Elected in capital all others in lower case in below examples.

1. Rbbrbbbrrbrrbrb or bbrbbrrbrrbrbR If the elected thinks they were last of first but was not, then they have little to base numbers on.

2. rbBbbrbbbrrbrrb if near the beginning or near the end it can also odds greatly drop to try and use statistics.

The main problem is that 15 is an extremely small sample to attempt to derive information from, especially when no other data is known.

Never make assumptions.

[Guest]

I'm afraid that this problem has not been solved properly. Discussions of the Hamming code (which is admittedly a beautiful mathematical object) are irrelevant to this problem, since it is founded on a very slippery probabilistic error.

There is actually no answer to the problem as posed, which is "What is the strategy that gives the biggest chance of success?"

If the question were refined to "What is the maximum probability of success that the team can guarantee themselves from a carefully chosen determinitic strategy?" the answer is in fact 0%.

The reason for this is as follows: The effectiveness of any strategy is entirely dependent on the probability distribution used to distribute the hats in the first place.

The original posted stated that the placement of hats was entirely arbitrary (e.g. flipping a coin). Later, the poster stated that all ratios of blue hats to red hats are equally likely. Unfortunately, these three ideas ("arbitrary", "decided by flipping a coin", "all ratios equally likely") are mathematically different and would not reward strategies in the same way. The poster has fallen into the trap of assuming that saying that each hat has a 50-50 chance of being either red or blue is the same as saying that the distribution of hats is completely random (all permutations equally likely) and every subsequent post that has offered a solution giving a probability greater than 50% has also fallen into this trap.

A simple example to illustrate this:

One way to guarantee that everyone has a 50% chance of having a red hat is to flip a coin for each person and put a hat on their head of the corresponding colour: H=Red, T=Blue. However, an equally valid way to guarantee that everyone has a 50% chance of having a red hat is to flip a coin once and give all 15 people a hat of the same corresponding colour. And there are many, many, many other subtler ways to do this. Each of the very credible arguments presented above as to why a probability of greater that 50% can be guaranteed has implicitly assumed one of these probability distributions.

*More to follow*

[Guest]

I like this guy...can we keep him?

maybe araver saned up!

[Guest]

Further justification as to why there is no answer to the question: "What is the strategy that gives the biggest chance of success?"

I can construct different scenarios in which the team can guarantee themselves different probabilities of success, simply by varying the probability distribution.

a) A situation in which everyone has a 50% chance of having a blue or a red hat, but the team has a strategy that guarantees 100% success.

The distribution of hats: I flip one coin. H: I alternate red and blue hats (the extra hat is red), T: Hat colours are reversed from the heads case.

Strategy to guarantee 100% success: Vote against the majority hat colour that you see, abstain if you see equal numbers.

b) A situation in which everyone has a 50% chance of having a blue or a red hat, but the team only has a strategy that guarantees 50% success.

The distribution of hats: I put the numbers 1-15 in a hat and pick one out at random. This is the number (n) of red hats that I will place. I then number the players 1-15, put the numbers back in the hat and draw n numbers sequentially to see which n players will receive the red hats.

Proof that there is no strategy here to guarantee greater than 50% success: In order for the game to be won, some player must not abstain. Even if we assume that such a player knows the way that the hats have been distributed (and, according to the question, he does not), whatever the complicated rule that has been worked out with his team mates that leads him to decide to pick a colour, his situation is this: He can see some number (k) of red hats. From the probability distribution of the hats, he knows that the chances of there being k or k+1 red hats are equal. Thus if he says "red", he is assuming that he is in the k+1 case and will be correct 50% of the time. If he says "blue", he is assuming that he is in the k case and will be right 50% of the time. It does not matter what reasoning got him to that "red" or "blue" answer or why he chose not to abstain (we are only considering a player who ultimately does not abstain), when he gives his answer, he will be wrong 50% of the time, so the team as a whole cannot be right more than 50% of the time.

[Guest]

The example distributions of hats that I have chosen may seem artificial, but the fact that no information is exchanged between players in this game means that the probability distribution of the hats is the only determinant of the probability of success from a particular guess of "red" or "blue", given the hats that you see in front of you. If no such probability distribution is given, then the probability of success from a given guess of "red" or "blue" is not defined.

The difference between this problem and the twenty prisoner problem, which is also listed as one of the site's favourite problems, is that the solution to the twenty prisoner problem guarantees 95% success independently of the way that the hats are distributed, and thus is well posed.

The only suggestion that the original poster makes as to how the hats are distributed in the original question is "e.g. by flipping a coin". If we assume that this means that each prisoner is allocated a red or blue hat according to an independent coin toss, then it can again be shown that no strategy can guarantee better than 50% success. Again, given a certain arrangement of hats, a winning strategy must dictate that some player (maybe several) does not abstain. This player sees a certain arrangement of red and blue hats. For this player, all the possible permutations of hats have now been narrowed down two just two possibilities: the arrangement he sees plus a red hat on him or the arrangement he sees plus a blue hat on him. The coin flipping rule that we have established makes every permutation of hats equally likely. In particular, the two possible remaining permutations described above are equally likely. Hence, whatever the rule that causes him to say "red" or "blue", he will have a 50% chance of being incorrect and thus the team as a whole cannot have a greater than 50% chance of being correct.

Note that saying that every permutation is equally likely is not the same as saying that every ratio of red to blue is equally likely, as some have assumed. The ratio 7 red:8 blue is much more likely than 15 red:0 blue, but a particular arrangement of those 7 red and 8 blue around the circle is equally likely to the all red arrangement. This is another problem with some of the methods above.

Edited October 23, 2011 by tpe03

[Guest]

Actually, I take back the "flipping the coin" paragraph from the last post. After much thought, I have to agree that the Hamming code method works for that probability distribution, which is pretty mind-blowing.

I stand by the other points, though.

Phil