[bushindo]

7 Britishmen, 7 Frenchmen, and 7 Italians are invited to play a cooperative game. The game is as follows:

1) The game host puts each of the 21 participants into a separate room, blindfolds him, and places either a red or blue hat on his head.

2) The host then tells each participant the following: how many red hats are there total among each of the other two races, and how many red hats total among the participant's other 6 countrymen. For instance, if the host is talking to a Frenchmen, he would say to the Frenchmen, "Among the 7 Italians, there are a total of x red hats. Among the 7 Britishmen, there are a total of y red hats. Among the remaining 6 Frenchmen, there are z red hats."

3) Each of the 21 participants is then requested to guess their hat color. Each participant has a choice of 'Red', 'Blue', or 'Abstain'.

4) Everybody wins if at least 1 person correctly guesses his hat color, and no person incorrectly guesses his hat. The choice 'Abstain' is considered neutral, and is neither right or wrong. For example, if 1 person guesses the right color, and the other 20 abstain, then everybody wins. If 1 person guesses correctly, 19 abstain, and 1 guesses incorrectly, then everybody lose.

The 21 Europeans above can discuss a strategy before playing the game. Help them determine a strategy that gives as high a winning rate as possible.

Edited December 13, 2010 by bushindo

[Guest]

1

Let's take the Frenchmen (could be any team though). FR1 will hear that there are z red hats among his 6 compatriots (let's say that z1 is the number FR1 hears). There are only two possible options for z1: either it is the case that z1 = r, where r stands for the actual total number of red hats for all 7 Frenchmen, including himself (this is the case if his own hat is blue), or z=r-1 (this is the case if his own hat is red). However, FR1 doesn't know whether z1=r, or z1 = r-1, so he should abstain, as should the rest of his teammates, until one of them hears a different number than the other teammates. If z1=2, z2=2, and z3=3, then FR3 has just learned that r (the total number of red hats on his team) =3. If he was wearing a red hat, he would have been told only of the other two men wearing red hats. He now knows that that he must be wearing a blue hat. Perhaps not a solution worthy of the tricky elegance of the puzzle, but I think it works....though I wonder, my solution didn't require anything about the other teams. Did I miss something here?

. And sorry for the accidental reposts, something goofy when I logged in....

[Guest]

1

Let's take the Frenchmen (could be any team though). FR1 will hear that there are z red hats among his 6 compatriots (let's say that z1 is the number FR1 hears). There are only two possible options for z1: either it is the case that z1 = r, where r stands for the actual total number of red hats for all 7 Frenchmen, including himself (this is the case if his own hat is blue), or z=r-1 (this is the case if his own hat is red). However, FR1 doesn't know whether z1=r, or z1 = r-1, so he should abstain, as should the rest of his teammates, until one of them hears a different number than the other teammates. If z1=2, z2=2, and z3=3, then FR3 has just learned that r (the total number of red hats on his team) =3. If he was wearing a red hat, he would have been told only of the other two men wearing red hats. He now knows that that he must be wearing a blue hat. Perhaps not a solution worthy of the tricky elegance of the puzzle, but I think it works....though I wonder, my solution didn't require anything about the other teams. Did I miss something here?

. And sorry for the accidental reposts, something goofy when I logged in....

Well... they're in separate rooms, so they wouldn't be able to listen the clues given to any of their fellas...

[bushindo]

1

Let's take the Frenchmen (could be any team though). FR1 will hear that there are z red hats among his 6 compatriots (let's say that z1 is the number FR1 hears). There are only two possible options for z1: either it is the case that z1 = r, where r stands for the actual total number of red hats for all 7 Frenchmen, including himself (this is the case if his own hat is blue), or z=r-1 (this is the case if his own hat is red). However, FR1 doesn't know whether z1=r, or z1 = r-1, so he should abstain, as should the rest of his teammates, until one of them hears a different number than the other teammates. If z1=2, z2=2, and z3=3, then FR3 has just learned that r (the total number of red hats on his team) =3. If he was wearing a red hat, he would have been told only of the other two men wearing red hats. He now knows that that he must be wearing a blue hat. Perhaps not a solution worthy of the tricky elegance of the puzzle, but I think it works....though I wonder, my solution didn't require anything about the other teams. Did I miss something here?

. And sorry for the accidental reposts, something goofy when I logged in....

Sorry to hear about the ridiculous charts

You actually just solved a different puzzle from what I intended. The version that you just solved is still pretty interesting, good job. You should also try the intended version also. I guarantee that no ridiculous charting is required.

I'd like to note that each participant are put into a different room, so he can not hear that has transpired with his fellow participants.

Edited December 13, 2010 by bushindo

[Wilson]

I have to warn you that I could often be found wearing a pointed hat with the letter D on it

But this seems like fun, so I'll have a go.

All agree that only one nominated member of each nationality can guess.

All others abstain at all times.

Only one of the three will guess, depending on which is best( x, y or z closest to 7 or 0)

The nominee from an agreed nationality does the guessing when x,y,z is a tie.

Nominees always guess with the odds.

[superprismatic]

7 Britishmen, 7 Frenchmen, and 7 Italians are invited to play a cooperative game. The game is as follows:

1) The game host puts each of the 21 participants into a separate room, blindfolds him, and places either a red or blue hat on his head.

2) The host then tells each participant the following: how many red hats are there total among each of the other two races, and how many red hats total among the participant's other 6 countrymen. For instance, if the host is talking to a Frenchmen, he would say to the Frenchmen, "Among the 7 Italians, there are a total of x red hats. Among the 7 Britishmen, there are a total of y red hats. Among the remaining 6 Frenchmen, there are z red hats."

3) Each of the 21 participants is then requested to guess their hat color. Each participant has a choice of 'Red', 'Blue', or 'Abstain'.

4) Everybody wins if at least 1 person correctly guesses his hat color, and no person incorrectly guesses his hat. The choice 'Abstain' is considered neutral, and is neither right or wrong. For example, if 1 person guesses the right color, and the other 20 abstain, then everybody wins. If 1 person guesses correctly, 19 abstain, and 1 guesses incorrectly, then everybody lose.

The 21 Europeans above can discuss a strategy before playing the game. Help them determine a strategy that gives as high a winning rate as possible.

What happens if everyone abstains? Play again? Lose?

[bushindo]

I have to warn you that I could often be found wearing a pointed hat with the letter D on it

But this seems like fun, so I'll have a go.

All agree that only one nominated member of each nationality can guess.

All others abstain at all times.

Only one of the three will guess, depending on which is best( x, y or z closest to 7 or 0)

The nominee from an agreed nationality does the guessing when x,y,z is a tie.

Nominees always guess with the odds.

The quote 'nominees always guess with the odds' is a bit ambiguous and makes it difficult to compute the winning rate of this strategy. Can you clarify?

What happens if everyone abstains? Play again? Lose?

If everyone abstain, that would be considered a loss for the participants.

Edited December 13, 2010 by bushindo

[araver]

I like the following strategy, but I'm not sure it's optimal. However I think it's a good ice-breaker as being the first with an actual winning chance computed.

As my starting ideas were symmetrical and deterministic up to a point, yet the resulting strategy is somewhat asymmetrical, my hunch says its probably not optimal. But it's the best I have so far.

Also sorry, it's longer to read because I started writing something else and changed mid-way

Assume the two colors are coded as 0 and 1 - 0=Blue or 1=Red.

For each team, if we ignore the other teams exist, it's similar to a "Team of 7" puzzle, with less information.

So, restricting ourselves to 1 team:

- each player knows the number of hats the other players have (0<=z<=6)

- if 0<z<6 each player does not know the actual distribution of the z hats among the other players .

For a Hamming-code approach, knowing the actual distribution of the hats is crucial. A Hamming-code for n=7=2^3-1 would require 16=2^(7-3) code words. Previous observations in the "Team of 15" thread leads to Hamming codes (set A) having 0, 3, 4 or 7 red hats. Recall the Hamming-style strategy for "Team of 15/7"

Step 1. Compute a and b from the bits you see completed by either 0 or 1.

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 does not belong to A. 

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

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

Without knowing the actual distribution of the other z hats, any preestablished Hamming-based strategy has a lower chance of working than expected. Denote the absolute number of hats as w (unknown to players). The following strategy assumes a non-optimal Hamming-style approach:

Step 0. Assume A={0,3,4,7}.

Step 1. Compute a=z and b=z+1.

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

Step 3. Exactly one of a and b belongs to A, so choose the one that does not belong to A and  

        assume this is true distribution and say the colour that corresponds to that outcome:

		If a is in A, choose w=b=z+1 to be true, so choose 1=Red.

		If b is in A, choose w=a=z to be true, so choose 0=Blue.

Note that z <= w <= z+1. So either a=w or b=w. The number of winning cases is 2*(7+21)=28 from 128 cases which is very low.

- If z=0 then a=0, b=1 the player chooses Red in step 3 . - If z=1 then a=1, b=2 the player chooses in step 2 to abstain. - If z=2 then a=2, b=3 the player chooses Blue in step 3. - If z=3 then a=3, b=4 the player chooses in step 2 to abstain. - If z=4 then a=4, b=5 the player chooses Red in step 3. - If z=5 then a=5, b=6 the player chooses in step 2 to abstain. - If z=6 then a=6, b=7 the player chooses Blue in step 3. Now let's see the chances. Note that if you see z=w-1 you have Red and if you see z=w you have Blue (of course, no way of knowing it). - If w=0 then all players see z=0 (therefore have Blue) and choose Red. LOSE - If w=1 then all players who see z=0 (therefore have Red) choose Red and all players who see z=1 (therefore have Blue) choose to abstain. WIN - If w=2 then all players who see z=1 (therefore have Red) choose to abstain and all players who see z=2 (therefore have Blue) choose Blue. WIN - If w=3 then all players who see z=2 (therefore have Red) choose Blue and all players who see z=3 (therefore have Blue) choose to abstain. LOSE - If w=4 then all players who see z=3 (therefore have Red) choose to abstain and all players who see z=4 (therefore have Blue) choose Red. LOSE - If w=5 then all players who see z=4 (therefore have Red) choose Red and all players who see z=5 (therefore have Blue) choose to abstain. WIN - If w=6 then all players who see z=5 (therefore have Red) choose to abstain and all players who see z=6 (therefore have Blue) choose Blue. WIN - If w=7 then all players who see z=6 (therefore have Red) choose to abstain. LOSE

The next Greedy strategy tries to win the middle cases (w=3,w=4) and group everyone errors in the losing cases:

Depending on z choose:

z=0 - Red*

z=1 - Blue

z=2 - Red

z=3 - abstain

z=4 - Blue

z=5 - Red

z=6 - Blue*

*-same chances if instead of color, abstain is chosen. This greedy strategy has a 2*(7+35)=84 out of 128 winning cases = 65.625% It wins for B={1,3,4,6} instances. Its not so good compared to 112 out of 128=87.5% for the perfect-Hamming strategy (if we knew the distribution of hats as well), but not far from that either.

Depending on z choose:

z=0 - Blue

z=1 - Red

z=2 - abstain

z=3 - Blue

z=4 - abstain

z=5 - Blue

z=6 - Red

This reverseGreedy strategy has 2*(1+21)+35=79 out of 128 winning cases. Its not as good as the Greedy strategy, but it is good if you think you're in a non-B instance {0,2,5,7}. As a side-effect, it also wins for a particular B-instance (w=3) i.e. when you think you're in a non-B instance but you're actually in a w=3 instance.

Step 0. Establish B={1,3,4,6} and assume teams form a circle (i.e. n=3 Hamming instance). 

        Assume A={000,111}. 

        Appoint a leader team as a starting point and a rotation direction: e.g. British, French, Italian.

Step 1. Compute the two bits of information you see from other teams based on set B. 

        So if you see a number that is in B mark it as a bit 1, else mark it as bit 0.

Step 2. Assuming the two possibilities (that you are either a B-instance or a non-B-instance) as bits for your team 

        you arrive at two unique 3-bit strings a (if you are a nonB-instance) and b (if you are a B-instance).

        The fact that you established in step 0 a starting point and a rotation direction makes a and b unique.

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

Step 4. Exactly one of a or b belongs to A:

	If a is in A, then choose b (think that you are a B-instance), so play the individual Greedy strategy.

	If b is in A, then choose a (think that you are a non-B instance), so play individual reverseGreedy strategy.

Note that this global strategy is independent of what you are told about your team, and only after arriving in step 4 and choosing an individual strategy you actually take the information about your team into account.

Chances of winning depend on the unknown global string w1w2w3 (British, French, Italian) where wi=1 iff the number of hats in team i is in B:

-000 - Everybody sees non-B instances, chooses b in step 4, tries to play Greedy and fails. Game is LOST.

-001, 010, 100 - One team (in a B instance) sees a=000 in A and plays the Greedy strategy which wins. Other two teams see 1-bit and 2-bit numbers not in A and abstain. Game is WON.

-110, 101, 011 One team (in a non-B instance) sees b=111 in A and plays reverseGreedy which wins. Other teams see 1-bit and 2-bit strings not in A and abstain. Game is WON.

-111 Everybody sees b=111 in A, so they choose to play reverseGreedy (for the wrong reasons). They usually fail. But the lack of symmetry in reverseGreedy gives you a rather unique global win if everyone is in a particular B-instance (w=3). Only in this case, all three teams play a winning reverseGreedy. In all other cases, at least one team fails and Game is LOST.

That lack of symmetry in reverseGreedy makes over-all winning chances harder to compute.

First, the individual probability of having a B-instance(1,3,4,6) is easy to compute (and was already computed) as it is the same with winning chances of the Greedy strategy 84/128. Conversely, 44/128 cases for a non-B instance.

Also, the chances of a w=3 instance are 35/128.

So, global chances (denote t=44/128):

Case 1) 000 means non-B instances for everyone = 44/128*44/128*44/128= t^3

Case 2) 001, 010, 100 means as single non-B instance = 3*44/128*44/128*84/128 = 3*t^2*(1-t)

Case 3) 110, 101, 011 means as single B instance = 3*44/128*84/128*84/128 = 3*t*(1-t)^2

Case 4) 111 means B instances for everyone = 84/128*84/128*84/128= (1-t)^3. Of which a particular case with global (35/128)^3 probability should be counted as a win (reverseGreedy side-effect).

So, global winning is 3*44/128*44/128*84/128 + 3*44/128*84/128*84/128+ (35/128)^3=(1486848+42875)/128^3=1529723/128^3.

Roughly 72.94%.

EDIT: Tried to make it more readable by two levels of spoilers.

- If w=0 then all players see z=0 (therefore have Blue) and choose Red. LOSE - If w=1 then all players who see z=0 (therefore have Red) choose Red and all players who see z=1 (therefore have Blue) choose Blue. WIN - If w=2 then all players who see z=1 (therefore have Red) choose Blue and all players who see z=2 (therefore have Blue) choose Red. LOSE - If w=3 then all players who see z=2 (therefore have Red) choose Red and all players who see z=3 (therefore have Blue) choose to abstain. WIN - If w=4 then all players who see z=3 (therefore have Red) choose to abstain and all players who see z=4 (therefore have Blue) choose Blue. WIN - If w=5 then all players who see z=4 (therefore have Red) choose Blue and all players who see z=5 (therefore have Blue) choose Red. LOSE - If w=6 then all players who see z=5 (therefore have Red) choose Red and all players who see z=6 (therefore have Blue) choose Blue. WIN - If w=7 then all players who see z=6 (therefore have Red) choose Blue. LOSE

Combining 3 teams' strategies in a greedy manner, each team playing the same local (inside-team) strategy is a little tricky. We should use the fact that one knows the exact instance the other teams are in to obtain a global advantage. Therefore each player should look at the global picture, then either choose to abstain or play a team strategy (e.g. Greedy strategy as above). Assuming the third team's point of view for a moment i.e. imagine you see x and y and your own z<=w<=z+1. First, if you play the Greedy strategy as described above you know it's a win for a team iff number of hats is actually 1,3,4,6. So if you see that both x and y are not in the set B={1,3,4,6}, there's no point in abstaining since the others surely cannot get it right on their own. You might get lucky and be in a B-instance yourself, therefore winning the game. This would be Naive-Rule 1. If both x and y are in set B, then you might be spoiling everyone's chances by playing since your set might not be a wining set. This would count as a Naive-Rule 2. However, assuming a symmetrical global strategy, if all see B-instances, they would all abstain and perhaps lose a chance of winning. Then perhaps choosing/appointing a team to take action if all else fails would be better but this does not actually lead to a simple Naive-Rule 3. This starts to looks like a small version of the Hamming-problem. So, instead of choosing a strategy based on the Naive-rules above, you can actually choose a sort of Hamming n=3 strategy. However, besides the individual Greedy strategy above, you will need a mirror strategy for when you're a non-B instance. The following reverseGreedy strategy wins for non-B instances (i.e. when w=0,2,5,7)

- If w=0 then all players see z=0 (therefore have Blue) and choose Blue. WIN - If w=1 then all players who see z=0 (therefore have Red) choose Blue and all players who see z=1 (therefore have Blue) choose Red. LOSE - If w=2 then all players who see z=1 (therefore have Red) choose Red and all players who see z=2 (therefore have Blue) choose to abstain. WIN - If w=3 then all players who see z=2 (therefore have Red) choose to abstain and all players who see z=3 (therefore have Blue) choose Blue. WIN - If w=4 then all players who see z=3 (therefore have Red) choose Blue and all players who see z=4 (therefore have Blue) choose to abstain. LOSE - If w=5 then all players who see z=4 (therefore have Red) choose to abstain and all players who see z=5 (therefore have Blue) choose Blue. WIN - If w=6 then all players who see z=5 (therefore have Red) choose Blue and all players who see z=6 (therefore have Blue) choose Red. LOSE - If w=7 then all players who see z=6 (therefore have Red) choose Red. WIN

Returning to the Hamming-style global strategy: Edited December 15, 2010 by araver

[bushindo]

I like the following strategy, but I'm not sure it's optimal. However I think it's a good ice-breaker as being the first with an actual winning chance computed.

As my starting ideas were symmetrical and deterministic up to a point, yet the resulting strategy is somewhat asymmetrical, my hunch says its probably not optimal. But it's the best I have so far.

Also sorry, it's longer to read because I started writing something else and changed mid-way

Assume the two colors are coded as 0 and 1 - 0=Blue or 1=Red.

For each team, if we ignore the other teams exist, it's similar to a "Team of 7" puzzle, with less information.

So, restricting ourselves to 1 team:

- each player knows the number of hats the other players have (0<=z<=6)

- if 0<z<6 each player does not know the actual distribution of the z hats among the other players .

For a Hamming-code approach, knowing the actual distribution of the hats is crucial. A Hamming-code for n=7=2^3-1 would require 16=2^(7-3) code words. Previous observations in the "Team of 15" thread leads to Hamming codes (set A) having 0, 3, 4 or 7 red hats. Recall the Hamming-style strategy for "Team of 15/7"

Step 1. Compute a and b from the bits you see completed by either 0 or 1.

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 does not belong to A. 

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

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

Without knowing the actual distribution of the other z hats, any preestablished Hamming-based strategy has a lower chance of working than expected. Denote the absolute number of hats as w (unknown to players). The following strategy assumes a non-optimal Hamming-style approach:

Step 0. Assume A={0,3,4,7}.

Step 1. Compute a=z and b=z+1.

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

Step 3. Exactly one of a and b belongs to A, so choose the one that does not belong to A and  

        assume this is true distribution and say the colour that corresponds to that outcome:

		If a is in A, choose w=b=z+1 to be true, so choose 1=Red.

		If b is in A, choose w=a=z to be true, so choose 0=Blue.

Note that z <= w <= z+1. So either a=w or b=w. The number of winning cases is 2*(7+21)=28 from 128 cases which is very low.

- If z=0 then a=0, b=1 the player chooses Red in step 3 . - If z=1 then a=1, b=2 the player chooses in step 2 to abstain. - If z=2 then a=2, b=3 the player chooses Blue in step 3. - If z=3 then a=3, b=4 the player chooses in step 2 to abstain. - If z=4 then a=4, b=5 the player chooses Red in step 3. - If z=5 then a=5, b=6 the player chooses in step 2 to abstain. - If z=6 then a=6, b=7 the player chooses Blue in step 3. Now let's see the chances. Note that if you see z=w-1 you have Red and if you see z=w you have Blue (of course, no way of knowing it). - If w=0 then all players see z=0 (therefore have Blue) and choose Red. LOSE - If w=1 then all players who see z=0 (therefore have Red) choose Red and all players who see z=1 (therefore have Blue) choose to abstain. WIN - If w=2 then all players who see z=1 (therefore have Red) choose to abstain and all players who see z=2 (therefore have Blue) choose Blue. WIN - If w=3 then all players who see z=2 (therefore have Red) choose Blue and all players who see z=3 (therefore have Blue) choose to abstain. LOSE - If w=4 then all players who see z=3 (therefore have Red) choose to abstain and all players who see z=4 (therefore have Blue) choose Red. LOSE - If w=5 then all players who see z=4 (therefore have Red) choose Red and all players who see z=5 (therefore have Blue) choose to abstain. WIN - If w=6 then all players who see z=5 (therefore have Red) choose to abstain and all players who see z=6 (therefore have Blue) choose Blue. WIN - If w=7 then all players who see z=6 (therefore have Red) choose to abstain. LOSE

The next Greedy strategy tries to win the middle cases (w=3,w=4) and group everyone errors in the losing cases:

Depending on z choose:

z=0 - Red*

z=1 - Blue

z=2 - Red

z=3 - abstain

z=4 - Blue

z=5 - Red

z=6 - Blue*

*-same chances if instead of color, abstain is chosen. This greedy strategy has a 2*(7+35)=84 out of 128 winning cases = 65.625% It wins for B={1,3,4,6} instances. Its not so good compared to 112 out of 128=87.5% for the perfect-Hamming strategy (if we knew the distribution of hats as well), but not far from that either.

Depending on z choose:

z=0 - Blue

z=1 - Red

z=2 - abstain

z=3 - Blue

z=4 - abstain

z=5 - Blue

z=6 - Red

This reverseGreedy strategy has 2*(1+21)+35=79 out of 128 winning cases. Its not as good as the Greedy strategy, but it is good if you think you're in a non-B instance {0,2,5,7}. As a side-effect, it also wins for a particular B-instance (w=3) i.e. when you think you're in a non-B instance but you're actually in a w=3 instance.

Step 0. Establish B={1,3,4,6} and assume teams form a circle (i.e. n=3 Hamming instance). 

        Assume A={000,111}. 

        Appoint a leader team as a starting point and a rotation direction: e.g. British, French, Italian.

Step 1. Compute the two bits of information you see from other teams based on set B. 

        So if you see a number that is in B mark it as a bit 1, else mark it as bit 0.

Step 2. Assuming the two possibilities (that you are either a B-instance or a non-B-instance) as bits for your team 

        you arrive at two unique 3-bit strings a (if you are a nonB-instance) and b (if you are a B-instance).

        The fact that you established in step 0 a starting point and a rotation direction makes a and b unique.

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

Step 4. Exactly one of a or b belongs to A:

	If a is in A, then choose b (think that you are a B-instance), so play the individual Greedy strategy.

	If b is in A, then choose a (think that you are a non-B instance), so play individual reverseGreedy strategy.

Note that this global strategy is independent of what you are told about your team, and only after arriving in step 4 and choosing an individual strategy you actually take the information about your team into account.

Chances of winning depend on the unknown global string w1w2w3 (British, French, Italian) where wi=1 iff the number of hats in team i is in B:

-000 - Everybody sees non-B instances, chooses b in step 4, tries to play Greedy and fails. Game is LOST.

-001, 010, 100 - One team (in a B instance) sees a=000 in A and plays the Greedy strategy which wins. Other two teams see 1-bit and 2-bit numbers not in A and abstain. Game is WON.

-110, 101, 011 One team (in a non-B instance) sees b=111 in A and plays reverseGreedy which wins. Other teams see 1-bit and 2-bit strings not in A and abstain. Game is WON.

-111 Everybody sees b=111 in A, so they choose to play reverseGreedy (for the wrong reasons). They usually fail. But the lack of symmetry in reverseGreedy gives you a rather unique global win if everyone is in a particular B-instance (w=3). Only in this case, all three teams play a winning reverseGreedy. In all other cases, at least one team fails and Game is LOST.

That lack of symmetry in reverseGreedy makes over-all winning chances harder to compute.

First, the individual probability of having a B-instance(1,3,4,6) is easy to compute (and was already computed) as it is the same with winning chances of the Greedy strategy 84/128. Conversely, 44/128 cases for a non-B instance.

Also, the chances of a w=3 instance are 35/128.

So, global chances (denote t=44/128):

Case 1) 000 means non-B instances for everyone = 44/128*44/128*44/128= t^3

Case 2) 001, 010, 100 means as single non-B instance = 3*44/128*44/128*84/128 = 3*t^2*(1-t)

Case 3) 110, 101, 011 means as single B instance = 3*44/128*84/128*84/128 = 3*t*(1-t)^2

Case 4) 111 means B instances for everyone = 84/128*84/128*84/128= (1-t)^3. Of which a particular case with global (35/128)^3 probability should be counted as a win (reverseGreedy side-effect).

So, global winning is 3*44/128*44/128*84/128 + 3*44/128*84/128*84/128+ (35/128)^3=(1486848+42875)/128^3=1529723/128^3.

Roughly 72.94%.

EDIT: Tried to make it more readable by two levels of spoilers.

- If w=0 then all players see z=0 (therefore have Blue) and choose Red. LOSE - If w=1 then all players who see z=0 (therefore have Red) choose Red and all players who see z=1 (therefore have Blue) choose Blue. WIN - If w=2 then all players who see z=1 (therefore have Red) choose Blue and all players who see z=2 (therefore have Blue) choose Red. LOSE - If w=3 then all players who see z=2 (therefore have Red) choose Red and all players who see z=3 (therefore have Blue) choose to abstain. WIN - If w=4 then all players who see z=3 (therefore have Red) choose to abstain and all players who see z=4 (therefore have Blue) choose Blue. WIN - If w=5 then all players who see z=4 (therefore have Red) choose Blue and all players who see z=5 (therefore have Blue) choose Red. LOSE - If w=6 then all players who see z=5 (therefore have Red) choose Red and all players who see z=6 (therefore have Blue) choose Blue. WIN - If w=7 then all players who see z=6 (therefore have Red) choose Blue. LOSE

Combining 3 teams' strategies in a greedy manner, each team playing the same local (inside-team) strategy is a little tricky. We should use the fact that one knows the exact instance the other teams are in to obtain a global advantage. Therefore each player should look at the global picture, then either choose to abstain or play a team strategy (e.g. Greedy strategy as above). Assuming the third team's point of view for a moment i.e. imagine you see x and y and your own z<=w<=z+1. First, if you play the Greedy strategy as described above you know it's a win for a team iff number of hats is actually 1,3,4,6. So if you see that both x and y are not in the set B={1,3,4,6}, there's no point in abstaining since the others surely cannot get it right on their own. You might get lucky and be in a B-instance yourself, therefore winning the game. This would be Naive-Rule 1. If both x and y are in set B, then you might be spoiling everyone's chances by playing since your set might not be a wining set. This would count as a Naive-Rule 2. However, assuming a symmetrical global strategy, if all see B-instances, they would all abstain and perhaps lose a chance of winning. Then perhaps choosing/appointing a team to take action if all else fails would be better but this does not actually lead to a simple Naive-Rule 3. This starts to looks like a small version of the Hamming-problem. So, instead of choosing a strategy based on the Naive-rules above, you can actually choose a sort of Hamming n=3 strategy. However, besides the individual Greedy strategy above, you will need a mirror strategy for when you're a non-B instance. The following reverseGreedy strategy wins for non-B instances (i.e. when w=0,2,5,7)

- If w=0 then all players see z=0 (therefore have Blue) and choose Blue. WIN - If w=1 then all players who see z=0 (therefore have Red) choose Blue and all players who see z=1 (therefore have Blue) choose Red. LOSE - If w=2 then all players who see z=1 (therefore have Red) choose Red and all players who see z=2 (therefore have Blue) choose to abstain. WIN - If w=3 then all players who see z=2 (therefore have Red) choose to abstain and all players who see z=3 (therefore have Blue) choose Blue. WIN - If w=4 then all players who see z=3 (therefore have Red) choose Blue and all players who see z=4 (therefore have Blue) choose to abstain. LOSE - If w=5 then all players who see z=4 (therefore have Red) choose to abstain and all players who see z=5 (therefore have Blue) choose Blue. WIN - If w=6 then all players who see z=5 (therefore have Red) choose Blue and all players who see z=6 (therefore have Blue) choose Red. LOSE - If w=7 then all players who see z=6 (therefore have Red) choose Red. WIN

Returning to the Hamming-style global strategy:

Bravo! The insight about the fact that the teams can be abstracted to a solved problem is spot on. Great work! Just some more comments

The substantial ideas of this puzzle are already described above. However, the step 4 in the global hamming code I think is more complicated than necessary. Some refinement are possible. I did not use the reverseGreedy strategy, and I was able to get the winning rate to above 75%.

Edited December 15, 2010 by bushindo

[bushindo]

This puzzle has been partially solved by araver. The strategy still isn't as optimal as it could be, so for the sake of completeness I'll clarify the remaining challenge. Given the problem in the OP, find a strategy that has a winning rate that is 75% or higher.

Edited December 17, 2010 by bushindo

[Guest]

This puzzle has been partially solved by araver. The strategy still isn't as optimal as it could be, so for the sake of completeness I'll clarify the remaining challenge. Given the problem in the OP, find a strategy that has a winning rate that is 75% or higher.

Thanks for a very interesting puzzle bushindo. I've thought about this one for awhile and the best I can do is a little over 71%. I'll be very curious to see how you get to over 75%.

First an observation on the puzzle and puzzles of this nature:

In any guessing puzzle like this, any individual guess can't be any better than 50%. No matter what information you get as a single player in the game, if you guess, you will only be right 50% of the time. So the key team strategy is to have as many players guess wrong when the team is wrong and only a few players to guess right when the team is right. If you pick the right strategy, the team can be right more often than not, while each individual will only bat 50%.

The first thing to think about before constructing a team strategy is to understand the distributions of the hats for 7 players. As noted in other posts you get 0 or 7 red hats 1 time each out of 128, 1 or 6 red hats 7 times each, 2 or 5 red hats 21 times each, and 3 or 4 red hats 35 times each. I can't think of any way to optimize a team strategy in a good way to account for 3 or 4 red hats. But the team can optimize for the 0,1,2 and 5,6,7 cases.

If we just look at the Brit team, they can guarantee a win if they actually have 0 or 2 total red hats and 5 or 7 red hats. Using this strategy, they lose if they have 1 or 6 red hats. The good news is there are 22*2 ways for there to be 0,2,5,or 7 red hats and only 2*7 ways to have 1 or 6 red hats for win percentage of over 75%. However they will all have to abstain more than half the time (70/128) to use this strategy.

Luckily, the other teams can pick up the slack. So, the Brit strategy is if you are told there are 0 red hats, you guess "blue." If you are told there are 1 red hats, you guess "red." If you are told there are 6 red hats, you guess "red." And if you told there are 5 red hats, you guess "blue."

For a reality check, let's add up the the right and wrong guesses, using this strategy. If there are 0 red hats, all 7 players will guess right. If there is 1 red hat, all 7 players will guess wrong. And if there are 2 red hats, only 2 players will guess right, but the other 5 will abstain. So for all the distributions, you get (7*1) + (2*21) = 49 correct guesses and (7*7) = 49 incorrect guesses. This is just as hoped for. The individuals are 50% on there guesses, but the team wins 22 times and only loses 7 times. The same is true on the other side of the spectrum with 5, 6 or 7 red hats.

The French strategy is the same as the Brit strategy, except that no one will guess if they hear that the Brits have either 0,1,2,5,6,or 7 red hats. In those cases, they know that the Brits made a guess, so they have no need to guess themselves. The French team will guess 70/128 percent of the time.

The Italians are little more complicated. First they abstain if either the Brit or French team had 0,1,2,5,6,or 7 red hats. If they know the Brits and the French abstained, they will use the same strategy outlined above with one extra case. Since abstaining is the same as losing, they should guess if there are 3 or 4 red hats. So, they should also guess "blue" if they hear that their teammates have 3 red hats. That way they will win if they have exactly 0,2,3,5,or 7 hats. The will lose if they 1,4 or 6 red hats.

The total win rate for this global strategy is: (44/128) + ((44/128)*(70/128)) + ((79/128)*(70/128)*(70/128)) = 71.63%.

If the actual optimal strategy is over 75%, I must be missing something big. I'll be very curious to hear bushindo's solution.

[Guest]

itailian:

0 guess red

1 abstian

2 guess red

3 abstian

4 guess blue

5 abstian

6 guess blue

0, 7 red, lose; 1, 6 win; 2, 5 lose; 3, 4 win.

this makes the calculation

44/128 +44/128 *70/128 +84/128 *70/128 *70/128 = 72.8%

[Guest]

If there are 21 people we know there are 21 hats. Is there a set number of hats? I mean, is there 10 of one, and 11 of the other? Really, I don't see how you can get better than a 50/50 chance not being able to see anyone else nor knowing for certain the total amount of either blue or red hats.

[bushindo]

Thanks for a very interesting puzzle bushindo. I've thought about this one for awhile and the best I can do is a little over 71%. I'll be very curious to see how you get to over 75%.

First an observation on the puzzle and puzzles of this nature:

In any guessing puzzle like this, any individual guess can't be any better than 50%. No matter what information you get as a single player in the game, if you guess, you will only be right 50% of the time. So the key team strategy is to have as many players guess wrong when the team is wrong and only a few players to guess right when the team is right. If you pick the right strategy, the team can be right more often than not, while each individual will only bat 50%.

The first thing to think about before constructing a team strategy is to understand the distributions of the hats for 7 players. As noted in other posts you get 0 or 7 red hats 1 time each out of 128, 1 or 6 red hats 7 times each, 2 or 5 red hats 21 times each, and 3 or 4 red hats 35 times each. I can't think of any way to optimize a team strategy in a good way to account for 3 or 4 red hats. But the team can optimize for the 0,1,2 and 5,6,7 cases.

If we just look at the Brit team, they can guarantee a win if they actually have 0 or 2 total red hats and 5 or 7 red hats. Using this strategy, they lose if they have 1 or 6 red hats. The good news is there are 22*2 ways for there to be 0,2,5,or 7 red hats and only 2*7 ways to have 1 or 6 red hats for win percentage of over 75%. However they will all have to abstain more than half the time (70/128) to use this strategy.

Luckily, the other teams can pick up the slack. So, the Brit strategy is if you are told there are 0 red hats, you guess "blue." If you are told there are 1 red hats, you guess "red." If you are told there are 6 red hats, you guess "red." And if you told there are 5 red hats, you guess "blue."

For a reality check, let's add up the the right and wrong guesses, using this strategy. If there are 0 red hats, all 7 players will guess right. If there is 1 red hat, all 7 players will guess wrong. And if there are 2 red hats, only 2 players will guess right, but the other 5 will abstain. So for all the distributions, you get (7*1) + (2*21) = 49 correct guesses and (7*7) = 49 incorrect guesses. This is just as hoped for. The individuals are 50% on there guesses, but the team wins 22 times and only loses 7 times. The same is true on the other side of the spectrum with 5, 6 or 7 red hats.

The French strategy is the same as the Brit strategy, except that no one will guess if they hear that the Brits have either 0,1,2,5,6,or 7 red hats. In those cases, they know that the Brits made a guess, so they have no need to guess themselves. The French team will guess 70/128 percent of the time.

The Italians are little more complicated. First they abstain if either the Brit or French team had 0,1,2,5,6,or 7 red hats. If they know the Brits and the French abstained, they will use the same strategy outlined above with one extra case. Since abstaining is the same as losing, they should guess if there are 3 or 4 red hats. So, they should also guess "blue" if they hear that their teammates have 3 red hats. That way they will win if they have exactly 0,2,3,5,or 7 hats. The will lose if they 1,4 or 6 red hats.

The total win rate for this global strategy is: (44/128) + ((44/128)*(70/128)) + ((79/128)*(70/128)*(70/128)) = 71.63%.

If the actual optimal strategy is over 75%, I must be missing something big. I'll be very curious to hear bushindo's solution.

Thanks for the interest, howardl1963. I describe my solution below

Let's consider the 7 Brits. Let the total number of red hats be called r. The following strategy is taken from araver's post, let's hope he doesn't mind =). Let A = {1,3,4,6}, and let B = {0, 2, 5, 7}. The total number of red hat r either belong to A or to B. Given that the hat colors are uniformly assigned, A will happen 65.625% of the time, and B will happen (1 - 65.625)% of the time.

If the Brits know that the total number of red hats belong to A, then they can guarantee a win by playing with the following strategy,

Let z be the number of red hats from a person's remaining 6 countrymen, depending on z choose:

z=0 - Red

z=1 - Blue

z=2 - Red

z=3 - abstain

z=4 - Blue

z=5 - Red

z=6 - Blue

If the Brits know that the total number of red hats is in B, then they can also construct a strategy that is guaranteed to win.

Now the game is reduced to a simple version of Essentially, we have 3 teams playing a game. Each team's state is either A (65%) or B (35%). If any team can correct guess their state, and no team incorrectly guesses it, then all wins. We can represent all possible outcomes by the following graph.

Where the letters at each vertex represent the states of the Brits, Frenchmen, and Italians, respectively. The number next to each vertex represent its probability. For instance, the probability that all there teams have state B is equal to .35 * .35 * .35 = .04 or 4%.

From the previous puzzle 'Team of 15' (see araver's excellent explanation at the end about the solution; also see for a example of a 3-person game with equal probability for the hat states), we know that given such a cube, if the 3 teams assume that their state distribution does not include ANY two diagonally opposite vertexes, then they can find a strategy that is guaranteed to win, given that their assumption is true. So, for this problem, the key is not to exclude the two vertexes AAA and BBB, as their total probability is 27+4 = 31%, giving a winning rate of 69%. If we exclude the vertexes ABA and BAB instead, then we are guaranteed to win (100 - (15 + 8) ) = 77% of the time.

Edited January 19, 2011 by bushindo

[Guest]

correct me if I'm wrong.

so here's three examples.

let's say the British have 6, the French have 4, and the Italians have 4 (state AAA)

the British go first. they know that Italians and French are in state A, they just don't know their own state.

however, we have eliminated BAA as a result, therefore they would guess correctly they are in A.

the French (ABA or AAA) and Italians (AAB or AAA) wouldn't be able to eliminate one of these possibilities, therefore they don't guess.

lets say the British have 5, the french have 7, and the Italians 4. (state AAB)

again the British go first. they could be in BAB or AAB, therefore they don't guess.

then french. they guess they are in state A, as state ABB has been eliminated.

then Italians. they don't guess. (AAA or AAB).

now let's do one where they lose.

let's say they are in state ABB.

British would guess they are in state B, French would guess they are in state A, and Italians would guess they are in state A.

all of them are wrong, but this only happens 8% of the time.

[Guest]

Thanks for the interest, howardl1963. I describe my solution below

Let's consider the 7 Brits. Let the total number of red hats be called r. The following strategy is taken from araver's post, let's hope he doesn't mind =). Let A = {1,3,4,6}, and let B = {0, 2, 5, 7}. The total number of red hat r either belong to A or to B. Given that the hat colors are uniformly assigned, A will happen 65.625% of the time, and B will happen (1 - 65.625)% of the time.

If the Brits know that the total number of red hats belong to A, then they can guarantee a win by playing with the following strategy,

Let z be the number of red hats from a person's remaining 6 countrymen, depending on z choose:

z=0 - Red

z=1 - Blue

z=2 - Red

z=3 - abstain

z=4 - Blue

z=5 - Red

z=6 - Blue

If the Brits know that the total number of red hats is in B, then they can also construct a strategy that is guaranteed to win.

Now the game is reduced to a simple version of Essentially, we have 3 teams playing a game. Each team's state is either A (65%) or B (35%). If any team can correct guess their state, and no team incorrectly guesses it, then all wins. We can represent all possible outcomes by the following graph.

Where the letters at each vertex represent the states of the Brits, Frenchmen, and Italians, respectively. The number next to each vertex represent its probability. For instance, the probability that all there teams have state B is equal to .35 * .35 * .35 = .04 or 4%.

From the previous puzzle 'Team of 15' (see araver's excellent explanation at the end about the solution; also see for a example of a 3-person game with equal probability for the hat states), we know that given such a cube, if the 3 teams assume that their state distribution does not include ANY two diagonally opposite vertexes, then they can find a strategy that is guaranteed to win, given that their assumption is true. So, for this problem, the key is not to exclude the two vertexes AAA and BBB, as their total probability is 27+4 = 31%, giving a winning rate of 69%. If we exclude the vertexes ABA and BAB instead, then we are guaranteed to win (100 - (15 + 8) ) = 77% of the time.

That's a truly elegant solution. Quite impressive. When you consider how prosaic and one dimensional my solution is compared to yours, it seems weird that your solution is only 5.5% better.

[araver]

Thanks for the interest, howardl1963. I describe my solution below

Let's consider the 7 Brits. Let the total number of red hats be called r. The following strategy is taken from araver's post, let's hope he doesn't mind =). Let A = {1,3,4,6}, and let B = {0, 2, 5, 7}. The total number of red hat r either belong to A or to B. Given that the hat colors are uniformly assigned, A will happen 65.625% of the time, and B will happen (1 - 65.625)% of the time.

If the Brits know that the total number of red hats belong to A, then they can guarantee a win by playing with the following strategy,

Let z be the number of red hats from a person's remaining 6 countrymen, depending on z choose:

z=0 - Red

z=1 - Blue

z=2 - Red

z=3 - abstain

z=4 - Blue

z=5 - Red

z=6 - Blue

If the Brits know that the total number of red hats is in B, then they can also construct a strategy that is guaranteed to win.

Now the game is reduced to a simple version of Essentially, we have 3 teams playing a game. Each team's state is either A (65%) or B (35%). If any team can correct guess their state, and no team incorrectly guesses it, then all wins. We can represent all possible outcomes by the following graph.

Where the letters at each vertex represent the states of the Brits, Frenchmen, and Italians, respectively. The number next to each vertex represent its probability. For instance, the probability that all there teams have state B is equal to .35 * .35 * .35 = .04 or 4%.

From the previous puzzle 'Team of 15' (see araver's excellent explanation at the end about the solution; also see for a example of a 3-person game with equal probability for the hat states), we know that given such a cube, if the 3 teams assume that their state distribution does not include ANY two diagonally opposite vertexes, then they can find a strategy that is guaranteed to win, given that their assumption is true. So, for this problem, the key is not to exclude the two vertexes AAA and BBB, as their total probability is 27+4 = 31%, giving a winning rate of 69%. If we exclude the vertexes ABA and BAB instead, then we are guaranteed to win (100 - (15 + 8) ) = 77% of the time.

Nicely done

Guess I should have seen that variation of the 3-person game with unequal probabilities ... stuck my head too deep in the sand to see that.

Edited January 19, 2011 by araver