Red hat, blue hat

[bonanova]

First, the good news: Nobody gets killed. 100 prisoners are out on parole, and the those who guess wrong will simply have their parole revoked. No blood. What a relief. The children will sleep well tonight.

But a lot of the usual stuff in the red hat / blue hat genre still applies:

• The Parole Officer (PO) will fit each parolee with a red hat or a blue hat.
• Each parolee can see all the other hat colors, but not his own.
• No communication is permitted. Just looking at hat colors.
  Seriously, no shouting, pausing, singing, pointing, facial expressions.
  If anything like that happens, then the PO will get PO'd and shoot everyone.
• On a common signal, each parolee will simultaneously guess the color of her own hat.
• Parolees initially meet, to formulate a strategy that dictates what color to guess, based on what she sees.
• The object is to guarantee the most successful guessers, regardless of the hat distribution.

And here's a wrinkle. There is a spy who informs the PO of the strategy.

So in placing the hats, the PO does his best to foil it.*

How many parolees can be saved?

* For example, if the strategy is to "guess the majority color" the PO will place 50 red and 50 blue hats, and no parolee will be saved.

[Rainman]

50 prisoners assume the number of blue hats is odd, the other 50 assume the number of blue hats is even.

[phil1882]

have half the prisioners think of blue as 1 and red as 0, and guess their own hat color as the total of all 1's %2

and the other half have red as 1 and blue as 0. trying to come up with a better strat.

[harey]

Based on a similar problem, the prisoners form a line with following rules:

a1) if there are less than 2 colours, take any place;
a2) otherwise take place between.

This way, prisoners are sorted R.....RRRrbBBB...B (or B...BBBbrRRR....R).
b1) 98 prisoners go for sure
b2) the remaining 2 prisoners guess at random.

This strategy can be refined so that everybody knows his colour.

As the PO cannot do anything to foil it, there will be two Best Answers.

Edited October 23, 2013 by harey

[Rainman]

Based on a similar problem, the prisoners form a line with following rules:

a1) if there are less than 2 colours, take any place;

a2) otherwise take place between.

This way, prisoners are sorted R.....RRRrbBBB...B (or B...BBBbrRRR....R).

b1) 98 prisoners go for sure

b2) the remaining 2 prisoners guess at random.

This strategy can be refined so that everybody knows his colour.

As the PO cannot do anything to foil it, there will be two Best Answers.

Standing in a certain position based on what you see is a form of communication.

[Rainman]

There are many strategies to achieve 50 guaranteed saves, but can we do better? Suppose we could guarantee at least 51 saves. Consider all possible permutations of hats, there are 2

¹⁰⁰ of them. Our strategy must yield at least 51 saves for every permutation, which means there are at least 51*2¹⁰⁰ saves total across the universe of possibilities. Now let's distribute these saves amongst the individual prisoners. Since there are 100 prisoners, the pigeonhole principle guarantees that some prisoner is saved at least 0.51*2¹⁰⁰ times. But then that prisoner's probability of guessing correctly is at least 0.51, which contradicts the premise that he/she makes an uninformed guess.

The conclusion is that we can not guarantee more than 50 saves.

[ThunderCloud]

Each prisoner should guess that his hat color is the same as the majority of the other hats he sees UNLESS he sees 49 of one color and 50 of the other, or he sees 48 of one and 51 of the other, in which case he should guess his hat is the minority color.

I think the worst the PO could do in that case would be to give a 49/51 distribution, in which case the 49 would be freed.

[ThunderCloud]

have half the prisioners think of blue as 1 and red as 0, and guess their own hat color as the total of all 1's %2

and the other half have red as 1 and blue as 0. trying to come up with a better strat.

I would give each prisoner that counts blue as 1 a red hat, one prisoner who counts red as 1 a red hat, and the other 49 prisoners (who all count red as 1) blue hats. 51/49 split, deviously distributed. Everyone who is counting blue as 1 (and is wearing a red hat) sees 49 blue hats and therefore guesses blue and is hauled back off to jail. Everyone who counts red as 1 and is wearing a blue hat sees 51 red hats and therefore guesses red. The lone prisoner who counts red hats as 1 and is wearing a red hat sees 50 red hats and therefore guesses blue. No parolees leaving prison this year...

Edited October 24, 2013 by ThunderCloud

[ThunderCloud]

Upon seeing a 49/50 split amongst their peers, half the prisoners will assume a 50/50 split and guess the minority color, while the other half will assume a 51/49 split and guess the majority color. Upon seeing a 48 / 51 split, each prisoner assumes a 49/51 split and guesses the minority color. Upon seeing any other distribution, each prisoner guesses his hat to be the majority color.

[phil1882]

edit: never mind

Edited October 24, 2013 by phil1882

[ThunderCloud]

Upon seeing a 49/50 split amongst their peers, half the prisoners will assume a 50/50 split and guess the minority color, while the other half will assume a 51/49 split and guess the majority color. Upon seeing a 48 / 51 split, each prisoner assumes a 49/51 split and guesses the minority color. Upon seeing any other distribution, each prisoner guesses his hat to be the majority color.

Actually, that conniving PO could foil this plan too, saving only 48...

Half of the prisoners will assume a 50/50 distribution upon seeing a 49/50 split, and will assume a 48/52 distribution upon seeing a 48/51 split. The other half will assume a 49/51 distribution in both cases. In every other case, all prisoners guess the majority color.

[bonanova]

have half the prisioners think of blue as 1 and red as 0, and guess their own hat color as the total of all 1's %2

and the other half have red as 1 and blue as 0. trying to come up with a better strat.

I would give each prisoner that counts blue as 1 a red hat, one prisoner who counts red as 1 a red hat, and the other 49 prisoners (who all count red as 1) blue hats. 51/49 split, deviously distributed. Everyone who is counting blue as 1 (and is wearing a red hat) sees 49 blue hats and therefore guesses blue and is hauled back off to jail. Everyone who counts red as 1 and is wearing a blue hat sees 51 red hats and therefore guesses red. The lone prisoner who counts red hats as 1 and is wearing a red hat sees 50 red hats and therefore guesses blue. No parolees leaving prison this year...

Good observation TC.

But in fairness to Phil, the PO, knowing that half will make blue=1, etc., may not know which half that is. The PO, I think, would only choose the distribution of red/blue, not the individuals that receive a certain color. I'm still thinking through Phil's solution before I declare the puzzle solved.

In addition to the solutions posted (Rainman's #11 is very concise, and I'm wondering whether it's equivalent to Phil's?) there is a another clever one, not yet posted.

[ThunderCloud]

The PO, I think, would only choose the distribution of red/blue, not the individuals that receive a certain color.

The puzzle states: "There is a spy who informs the PO of the strategy. So in placing the hats, the PO does his best to foil it." I interpreted this to mean the PO placed the hats himself, as diabolically as he could.

Edited October 25, 2013 by ThunderCloud

[bonanova]

The PO, I think, would only choose the distribution of red/blue, not the individuals that receive a certain color.

The puzzle states: "There is a spy who informs the PO of the strategy. So in placing the hats, the PO does his best to foil it." I interpreted this to mean the PO placed the hats himself, as diabolically as he could.

I follow you. And the OP, again, to be fair to you, does not preclude your comment.

The difference I drew was between knowing the strategy in general terms and being privy to the details of its implementation. And that is a finer distinction than the OP makes.

BTW, This may distinguish between Phil's and Rainman's (post 11) approaches. I don't think your PO tactic can defeat Rainman's solution. Or can it?

[Rainman]

Phil's post is equivalent to half of the prisoners guessing there is an even number of blue hats, and the other half guessing there is an even number of red hats. Which is equivalent to everyone guessing there is an even number of blue hats. A 51-49 distribution, for example, is enough to guarantee that everyone fails. He had the right idea, but switching between counting red as 1 and counting blue as 1 does not change the outcome of the guess.

[bonanova]

The classic solution I saw a while back is clever, but not as neat as Rainman's:

In pairs, half guess the color they see on their partner's hat.

The other half guess the color not on their partnet's hat.

E.g. a husband would guess his wife's color; his wife would guess the color not her husband's.

It would almost happen that way without planning it.

[ThunderCloud]

The PO, I think, would only choose the distribution of red/blue, not the individuals that receive a certain color.

The puzzle states: "There is a spy who informs the PO of the strategy. So in placing the hats, the PO does his best to foil it." I interpreted this to mean the PO placed the hats himself, as diabolically as he could.

I follow you. And the OP, again, to be fair to you, does not preclude your comment.

The difference I drew was between knowing the strategy in general terms and being privy to the details of its implementation. And that is a finer distinction than the OP makes.

BTW, This may distinguish between Phil's and Rainman's (post 11) approaches. I don't think your PO tactic can defeat Rainman's solution. Or can it?

The Evil PO would be out of luck with Rainman's approach, so far as I can tell.

[benjer3]

What is discussed is specifying who will say red and who will say blue. However, the prisoners being logical, take from it to say the opposite. A not-so-intelligent PO would give each person the opposite colored hat, and all the prisoners would go free; with an intelligent PO, it would turn into a game of WIFOM, and may free 100 or 0, which doesn't exactly meet the puzzle's criteria. And if the prisoners tried to decide what the PO would do, it may just end up being around 50-50.

[bonanova]

What is discussed is specifying who will say red and who will say blue. However, the prisoners being logical, take from it to say the opposite. A not-so-intelligent PO would give each person the opposite colored hat, and all the prisoners would go free; with an intelligent PO, it would turn into a game of WIFOM, and may free 100 or 0, which doesn't exactly meet the puzzle's criteria. And if the prisoners tried to decide what the PO would do, it may just end up being around 50-50.

I think you're correct in your last statement. You can, as far as I know. guarantee 50% but not more.