[Blofeld]

This time, we have only four captives. They each have an independent 50% chance of getting a red hat, or else they get a black hat. They know everyone else's hat colour, but not their own.

The rules of this particular contest are as follows: at a given moment, each person may either guess their hat colour or pass. The group wins or loses as a unit: they win if at least one person gets it right, and nobody gets it wrong, and lose otherwise. Guessing (or not) is simultaneous, and they may not pass information to each other. They are allowed to confer beforehand.

What strategy should they adopt to maximise their chances of winning?

[Apologies if I've left any ambiguities in the statement of that ... ask and I'll try to answer]

[jonottawa]

I don't see how this is a different problem than the 2 prisoner solution that Han posted in the other thread.

Adam and Bob are instructed as follows:

Adam, say Bob's hat color

Bob, say the opposite of Adam's hat color.

Carl and Doug are given the same instructions:

Carl, say Doug's hat color

Doug, say the opposite of Carl's hat color.

2 of the guys will be right, they all win.

Edit: I misread the problem. I stopped reading after 'They win if at least one person gets it right.' I'll leave my stupid answer up.

[joshs]

Blofeld, on Nov 20 2007, 07:01 PM, said:

This time, we have only four captives. They each have an independent 50% chance of getting a red hat, or else they get a black hat. They know everyone else's hat colour, but not their own.

The rules of this particular contest are as follows: at a given moment, each person may either guess their hat colour or pass. The group wins or loses as a unit: they win if at least one person gets it right, and nobody gets it wrong, and lose otherwise. Guessing (or not) is simultaneous, and they may not pass information to each other. They are allowed to confer beforehand.

What strategy should they adopt to maximise their chances of winning?

[Apologies if I've left any ambiguities in the statement of that ... ask and I'll try to answer]

Well here it seems that you only want 1 person to guess most of the time and having more than 1 person guesses reduces your expectations.

So it seems that the optimal strategy is:
If you see 3 hats of the same color, guess the opposite. Otherwise Pass.

This wins in 4 of the 5 cases when you guess
RRRG (person 4 guess and is right)
RRGR (person 3 guesses and is right)
RGRR (person 2 guesses and is right)
GRRR (person 1 guesses and is right)
RRRR (they all guess and are all wrong)

And the same with the R's and G's switched.

So you win with all the 3-1's, lose with the 4-0's, and don'tbet with the 2-2's.

There are 8/16 3-1's
There are 2/16 4-0's
There are 6/16 2-2's

So your expectations is 6/16=3/8 per turn

I haven't thought about an optimality proof.

[Trumpace]

I think I have seen this before and seem to remember that if n is the number of people then probability of winning can be made 1 - O(1/2^n) (O = order of in asymptotic language)

i.e as n increases, the chances of winning can be made close to 100%.

[joshs]

joshs, on Nov 20 2007, 07:18 PM, said:

Blofeld, on Nov 20 2007, 07:01 PM, said:

This time, we have only four captives. They each have an independent 50% chance of getting a red hat, or else they get a black hat. They know everyone else's hat colour, but not their own.

The rules of this particular contest are as follows: at a given moment, each person may either guess their hat colour or pass. The group wins or loses as a unit: they win if at least one person gets it right, and nobody gets it wrong, and lose otherwise. Guessing (or not) is simultaneous, and they may not pass information to each other. They are allowed to confer beforehand.

What strategy should they adopt to maximise their chances of winning?

[Apologies if I've left any ambiguities in the statement of that ... ask and I'll try to answer]

Well here it seems that you only want 1 person to guess most of the time and having more than 1 person guesses reduces your expectations.

So it seems that the optimal strategy is:
If you see 3 hats of the same color, guess the opposite. Otherwise Pass.

This wins in 4 of the 5 cases when you guess
RRRG (person 4 guess and is right)
RRGR (person 3 guesses and is right)
RGRR (person 2 guesses and is right)
GRRR (person 1 guesses and is right)
RRRR (they all guess and are all wrong)

And the same with the R's and G's switched.

So you win with all the 3-1's, lose with the 4-0's, and don'tbet with the 2-2's.

There are 8/16 3-1's
There are 2/16 4-0's
There are 6/16 2-2's

So your expectations is 6/16=3/8 per turn

I haven't thought about an optimality proof.

Oh woops, I thought you don't lose anything if no one guesses. So this solution is clearly not right if you lose unless you have at least 1 right and have 0 wrong....

[joshs]

the best I have so far is:
Person 1 always abstains, and the other 3 ignore what is on his head.
Of the other 3, someone votes IFF the other 2 are the same, in which case he selects the other color
So of the 3 hats, we win all the 2-1's (only the 1 votes), and lose the 3-0's. So we win 75% of the time.

I can't seem to do any better by including the 4'th guy so far...

[inquiry]

joshs, on Nov 20 2007, 09:01 PM, said:

the best I have so far is:
Person 1 always abstains, and the other 3 ignore what is on his head.
Of the other 3, someone votes IFF the other 2 are the same, in which case he selects the other color
So of the 3 hats, we win all the 2-1's (only the 1 votes), and lose the 3-0's. So we win 75% of the time.

I can't seem to do any better by including the 4'th guy so far...

You can do slightly better, i think. If the first guy sees three colors the same, he votes the other color, if he sees a 2-1 mix, he abstains. Then the next guys know to follow your strategy, and they never lose (as 3-0 color amongst themselves will not exist). So you lose only to 4-0 (not 3-0).

So the results of this strategy is

All four same color, you lose
You win, per force in all other situations. So that the math is,

4 - alike (12.5%) you lose,
all others, you win (87.5%).

This odds were calculated on the chance of the same color comming up 4 times in a row, i figured as follows: the first hat will be some color, so the chance for the next three to be the same color would be 12.5% (0.5x0.5x0.5), so the correct statistics would be lose 12.5% of the time, win 87.5% of the time.

(alternatively, teh chance for 4 red hats is .5 x .5 x .5 x .5 = 6.25, chance for four blacks is same 6.25, so chance of all one color is the sum or 12.5)

[jonottawa]

inquiry, on Nov 21 2007, 05:12 AM, said:

joshs, on Nov 20 2007, 09:01 PM, said:

the best I have so far is:
Person 1 always abstains, and the other 3 ignore what is on his head.
Of the other 3, someone votes IFF the other 2 are the same, in which case he selects the other color
So of the 3 hats, we win all the 2-1's (only the 1 votes), and lose the 3-0's. So we win 75% of the time.

I can't seem to do any better by including the 4'th guy so far...

You can do slightly better, i think. If the first guy sees three colors the same, he votes the other color, if he sees a 2-1 mix, he abstains. Then the next guys know to follow your strategy, and they never lose (as 3-0 color amongst themselves will not exist). So you lose only to 4-0 (not 3-0).

So the results of this strategy is

All four same color, you lose
You win, per force in all other situations. So that the math is,

4 - alike (12.5%) you lose,
all others, you win (87.5%).

This odds were calculated on the chance of the same color comming up 4 times in a row, i figured as follows: the first hat will be some color, so the chance for the next three to be the same color would be 12.5% (0.5x0.5x0.5), so the correct statistics would be lose 12.5% of the time, win 87.5% of the time.

(alternatively, teh chance for 4 red hats is .5 x .5 x .5 x .5 = 6.25, chance for four blacks is same 6.25, so chance of all one color is the sum or 12.5)

I started thinking along the same lines but this doesn't work. The other 3 guys can't know when they're 3-0. Of course, if you see that they're 3-0 it doesn't hurt anything for you to vote the other color, but all 3 other guys will too and you still lose. Everybody votes simultaneously ... The problem is going to throw bridge players off because we think of an auction and a clockwise sequence. This is everyone 'bidding/passing' at the same time/all at once.

I can't improve on Josh's effort (at least so far) but he seems to imply it's gotta be person 1 who abstains. It can be any of the 4 since they're essentially interchangeable.

[inquiry]

jonottawa, on Nov 21 2007, 12:21 AM, said:

inquiry, on Nov 21 2007, 05:12 AM, said:

joshs, on Nov 20 2007, 09:01 PM, said:

the best I have so far is:
Person 1 always abstains, and the other 3 ignore what is on his head.
Of the other 3, someone votes IFF the other 2 are the same, in which case he selects the other color
So of the 3 hats, we win all the 2-1's (only the 1 votes), and lose the 3-0's. So we win 75% of the time.

I can't seem to do any better by including the 4'th guy so far...

You can do slightly better, i think. If the first guy sees three colors the same, he votes the other color, if he sees a 2-1 mix, he abstains. Then the next guys know to follow your strategy, and they never lose (as 3-0 color amongst themselves will not exist). So you lose only to 4-0 (not 3-0).

So the results of this strategy is

All four same color, you lose
You win, per force in all other situations. So that the math is,

4 - alike (12.5%) you lose,
all others, you win (87.5%).

This odds were calculated on the chance of the same color comming up 4 times in a row, i figured as follows: the first hat will be some color, so the chance for the next three to be the same color would be 12.5% (0.5x0.5x0.5), so the correct statistics would be lose 12.5% of the time, win 87.5% of the time.

(alternatively, teh chance for 4 red hats is .5 x .5 x .5 x .5 = 6.25, chance for four blacks is same 6.25, so chance of all one color is the sum or 12.5)

I started thinking along the same lines but this doesn't work. The other 3 guys can't know when they're 3-0.

But the first guy CAN, that is the point... if he sees three the same, he guess the other color. So if the first guy passes, the next three can not be all the same. Obviously the last three guys can then either pass, or all say the opposite color of the first guy.

[jonottawa]

If there were a SEQUENCE to the 'auction' you could say:

Person 1, 2 and 3 should pass if the last guy's hat is black

Person 1 and 2 should pass if the 3rd guy's hat is black

Person 1 should pass if the 2nd guy's hat is black

Person 1 should take a wild guess (for the sake of argument, we'll say he guesses black) if the other 3 hats are red.

That agreement loses only to 4 red hats.

Wouldn't surprise me if Josh's answer is best, but maybe not. Blofeld, what number should we be shooting for?

[han]

Josh's answer is not correct.

Ben seems to have misunderstood the question, but...

(very nice question btw Owen)

[Echognome]

Are they allowed to delay in giving their answer?

[matmat]

they're supposed to state their answer simultaneously.

[jonottawa]

Hannie, on Nov 21 2007, 07:14 AM, said:

Ben seems to have misunderstood the question, but...

That's a hint, I take it? So we're shooting for 87.5%? That seems reasonable, since 75% is not good enough and 100% seems unattainable.

[Echognome]

matmat, on Nov 20 2007, 11:49 PM, said:

they're supposed to state their answer simultaneously.

Right, but that's not what I'm getting at. Some of these have solutions as follows:

If anyone sees three hats of the same color, he guesses the other color. If no one guesses immediately, then that isn't the case, so if you see two of one color and one of the other, you guess the other.

That accounts for all the cases except all four of the same color.

Now let me change it slightly. You get are in a chamber that is divided into 4 by soundproof glass walls and curtains. The curtains are raised for 3 seconds and then quickly lowered and then they can't see each other again. Then they have to exit the chamber and discuss with a guard if they want to make a guess or not. Then the game is over.

[brianshark]

Are they allowed multiple simultanious (red/black/pass) 'calls'? If that were the case, on the first 'round' then they could arrange for everyone but 1 to pass. And on the second round, everyone but 2 passes. Etc.

If instead we are allowed to hesitate before making our call, surely that is passing information to each other about each other's own hat, albeit in a codified way.

So I assume the intention of the problem is Matt's scenario where only one mass simultanious round of calls takes place? (But they can discuss beforehand their strategy before any of them are given coloured hats)

[Blofeld]

That's right.

Can anyone come up with a bound on the chance of winning?

(Harder:) How well can you do with n people instead of 4?

[han]

You should ignore my comment, I didn't get the problem right myself!

[Blofeld]

I'm intrigued, now, Han - what did you think the problem was? There's obviously a range of interesting problems here.

[brianshark]

I don't believe 75% can be bettered with 4 people. Though there are numerous ways to get that 75% probability. If I'm wrong, do tell so I can look harder.