Jump to content
BrainDen.com - Brain Teasers
• 0

# Red hat, blue hat

## Question

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.

## Recommended Posts

• 0

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

##### Share on other sites

• 0

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.

##### Share on other sites

• 0

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 by harey
##### Share on other sites

• 0

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.

##### Share on other sites

• 0

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

100 of them. Our strategy must yield at least 51 saves for every permutation, which means there are at least 51*2100 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*2100 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.

##### Share on other sites

• 0

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.
##### Share on other sites

• 0

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 by ThunderCloud
##### Share on other sites

• 0

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.

##### Share on other sites

• 0

edit: never mind

Edited by phil1882
##### Share on other sites

• 0

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.

##### Share on other sites

• 0

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.

##### Share on other sites

• 0

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 by ThunderCloud
##### Share on other sites

• 0

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?

##### Share on other sites

• 0

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.

##### Share on other sites

• 0

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.

##### Share on other sites

• 0

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.

##### Share on other sites

• 0

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.

##### Share on other sites

• 0

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.

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Answer this question...

×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
×
• ### Recently Browsing   0 members

• No registered users viewing this page.
×

• #### Activity

• Riddles
×
• Create New...