Hats On A Death Row

I thought of 2 cunning answers...but then paused to engage my brain and realised they were both wrong...

This is just pretendies right, and they won't kill a Cat ...right?
Del

OH! I know this one!

Just as he asks the first (well, the last in line) prisioner the question, they all throw their hats up in the air to create a distraction. In the resulting confusion, two prisioners grab up a few of the hats and put them into a bundle, while three other prisioners frantically strike their chains against the hard stone floor to make sparks. Once the pile of hats ignites, they use the flaming headwear to incapacitate the guards. Under the cover of all the smoke, they grab the king (who as is typical with such bullies is frightened witless) and find the key to the prision gate, which he has not-so-cleverly hidden in his left shoe.

It's really simple when you think it through.

Only be a problem if the king won't tell them how many of the hats are red.

I'm guessing the prisoners get together and agreed that the guy in the back would speak the color he guessed for himself if the hat in front of him was red, and he would shout the color he guessed for himself if the hat was black.

The next man would say the color of his hat if the man in front of him had a Red hat and would shout the color if the man in front of him had a black hat.

Everyone would know what they were wearing based on how the man behind them answered, speak or shout.

This way the only one risking his life, was the poor guy in the back.

Come on, if the guy in the back looking out at the other 19 guys. He has been told there are five red hats. He sees only four then he's has to be red. If number 19 looking at the 18 men in front and there are four red hats. He heard number 20 say his is red then he knows his is black. All they have to due is sing out loud and clear.

There is no mention of how many hats of each colour are available... (unless I have miss-read the post... it wouldn't be the first time.

See post #4

The prisoner at the back fakes a hard sneeze that causes his hat to fly off in front, so he gets to see what color it is.

It appears that not enough information is given to deduce a possible outcome beyond a 50% chance for all 20 prisoners. Now, if the number of each hat color was given then all prisoners would know with certainty what color hat they had and would go free if there were 10 of each color. I believe that this riddle was given incorrectly. The last prisoner in line (we will call him #20), facing all the others may not know with 100% certainty what color hat he had on if they were all (20 prisoners) told that there were, for example, 11 red hats and 11 black hats and only 10 red hats and 9 black hats were used on prisoners 1 thru 19.

To explain this we will us a more manageable number. Now let's suppose the following: There are only 3 prisoners, each facing to the right; i.e., the 1st prisoner does not see anyone in front of them, the 2nd prisoner only sees the 1st and the 3rd prisoner can see the 2nd and the 3rd. The warden blindfolds all prisoners and places a red hat on the 1st and 3rd prisoners and a black hat on the 2nd and then takes the blind folds off. The 3rd prisoner can see the hat colors of the 2nd and 1st but not his own. The 2nd prisoner can see the hat color of only the 1st and the 1st prison can not see any ones hat color. Once again, no prison can see their own hat color. The warden tells the prisoners that there are 2 red hats and 2 black hats. He also states that if you know the color of the hat you are wearing then let me know and you will go free. Prisoner #2 speaks-up after a pause and states that he has a black hat. Prisoner #1 states immediately after this that he has a red hat. Prisoner #3 doesn't know what color hat he has and his guess would give him a 50% survival rate.

The answer for the release of prisoners 1 and 2 can now be logically derived with 100% certainty while prisoner 3, well, survival is left to a 50% chance. This deduction can now be transposed to the 20 prisoners with only 1 through 19 being released with 100% certainty and the same demise for #20 awaits that of prisoner #3 in the 3 prisoner example.

I can give the rational behind this but I'm sure someone else will so I won't spoil the fun.

Oops!, my error.

"...11 red hats and 11 black hats and only 10 red hats and 9 black hats were used on prisoners 1 thru 19."

Change this to:

11 red hats and 10 black hats and only 10 red hats and 9 black hats were used on prisoners 1 thru 19.

The prisoners have ample time to collude. Only 1 may die.

I would suggest they all agree:

a) to all call out the colour of the hat worn
by the person in front of them; and:

b) if the colour hat of the person in front of them is different
to their own colour hat, they will call their own hat colour twice.

Therefore: the first call tells the person in front of them the colour
of their hat; and, if the same colour call is repeated (to save the
life of the caller) it tells the person in front of the caller, their own
hat is actually the opposite colour. i.e. red=red. red, red,= black

e.g. imagine the person behind you has called out your hat is red;
(according to a) - so to save your life you must call "red." However;
the person in front of YOU has a black hat; then, to save your life,
you call out "red; and then red" again, to inform the person in front
of you his hat is actually black. (according to b)

This means only the first person to call out, i.e.the last person in the
queue, is at risk, with a 50/50 chance of calling the correct colour.
That is, only the first person to call out may die; because the next
person(s) forward will have been told their hat colour, and so on.

Without any form of communication, e.g. signalling, queue positioning,
etc. I do not know (yet) how the first caller can be informed of his hat colour.

That is, with no hat numbers to tally (i.e.10 red/10 black hats NOT specified.)
no signalling, nor communication, and no pre-arranged positioning, the first
caller seems "blind" to the hat colour information needed to save his life.

However; if the 10/10 info. was omitted by accident, and 10 hats of
each colour were used, then the 20th prisoner would have no problem
calling his own colour. (seeing the 19 in front of him.)

That is, if his hat colour was red, he would call the hat colour of the
prisoner in front of him, either as red, (because his was) or, red, red; to tell
the prisoner in front of him his hat colour was actually black; etc. (as above.)

Interesting to learn the correct answer!

jt.

Have a free web page in seconds - on http://www.mfnb.at

No collusion is allowed and the only words coming out of their mouths would be that of the color of their own hat and no one else's hat. No hand signals can be used, no grunting, no body language, no physical contact, no telepathy, etc. The answer is obtained by pure reasoning and in fact, very simple once you know it.

Hint: The last prisoner in the 3 prison scenario doesn't know which color hat he has on. All he knows is that there are 4 hats, 2 of each color and he sees one of each color in front of him. Because he doesn't know the correct color hat he has on, without guessing, prisoner #2 knows his color hat and then prisoner #1 now knows his for the same reason.

So, how do prisoners #2 and then #1 know what color hats they are wearing?

One more thing...there are no mirrors and no one in the 'audience' is giving any hints:)

All he knows is that there are 4 hats, 2 of each color ..

The question doesn't state that there is a specific number of hats of each colour...

You are 100% correct, the initial post does not state a specific number of hats..

Go to post #10:

"It appears that not enough information is given to deduce a possible outcome beyond a 50% chance for all 20 prisoners...I believe that this riddle was given incorrectly." Therefore, I introduced a specific quantity of hats for each color to move the riddle beyond chance to one of logic.

Now, I could be wrong but in any case I introduced another variable.

Re: reply to Plaasteek.

1) The problem does not prohibit prior collusion.
The king gives them 24 hours notice, saying only:

"not be allowed to look back or communicate together in any way
(talking, touching.....)." - i.e. during the test.

2) The prisoners only call out the colour of their own hats.

(in my solution) Which also complies fully with the problem.

i.e. prisoners only call out the red or black colour of their own hat.
They repeat this, their own, correct hat colour, to inform the prisoner
(in front of them) when the one in front hat is a different colour.

e.g. the man behind me calls "red" (once) - because he has been told
his hat is red. (by the man before him.) If he calls "red" only once -
which he should do, - remember this is the colour of his own hat - then
my hat is also red. (according to "a" in my original reply.) however:

If he repeats the "red" - which he is allowed to do, - it being the colour
of his own hat - this double "red" tells me that my hat is actually black;
and, while he has done nothing "wrong" at all, - by stating his own colour
hat, he has also informed me (being in front) that my hat is actually black

In turn, I now know my hat is black; and view the hat in front of me.

If the hat (in front) is black, I just state "black" and go free - by correctly
stating the colour of MY hat. (which is also the colour of the one in front)

However:

If the man in front of me has a red hat, I call "black" twice, - both being
correct for MY hat. - But, this also tells the man in front of me his hat
is not black (as indicated by my first "black") but his in fact is actually "red."

This way, the prisoner not only calls the true colour of HIS own hat, to go free,
but also informs the prisoner in front of him the colour of their hat; and
who can then also call it correctly and go free. And so on, down the line.

Therefore, at least 19 prisoners can go free, this way, no problem;
and in accordance with the problem as set.

jt.

I used to be in archaeology, but quit.. when I realised my life was in ruins.

Here's the answer to my variation.

In the 3 prisoner scenario the 2^nd prisoner knew that he had a black hat on because the prisoner behind him (#3) didn't know. The 1^st prisoner then knew his hat was red for the same reason; prisoner #3 didn't know and prisoner #2's stated that his was black. Since there were 4 hats (in my variation) and prisoner #3 could see the 2 prisoners in front of him, each having a different color hat, he didn't know what color hat he had on. Therefore, prisoner #2 could see that prisoner #1 had a red hat and if he also had a red had then prisoner #3 would know that he (#3) had to have a black hat. Since prisoner #3 didn't know then prisoner #2 deduced that he had to have a black hat on. You can use this same logic for any number as long as there is one more hat than prisoners and the left over hat is a different color than what the last prisoner has on.

Friends,

The probability is quite high that a little planning in advance can result in close to 15 prisoners going free, not the 10 (50%) which has been posited. If the post's rules are followed (not the different variations and assumptions added by others), and the prisoners have agreed that the even prisoners will answer with the color of the person's hat ahead of them, then 10 of the 20 (all the odd ones in the line) will go free because their hat color was told them by the answer of the prisoner behind. However, since the odd prisoners in the line still have a 50% chance of wearing the color they call (assuming that the king was assigning hat colors at random), some of them will also go free. Note that no prisoner can call out colors twice, so suggestions of doing this are going to result in all prisoners being executed (according to the original post's rules).

If the hats are distributed by alternates, then 10 prisoners will go free. If they are not by alternates and are random instead, then the probabilities are 1/1024 for 10 or 20 to go free, 10/1024 for 11 or 19 to go free, 45/1024 for 12 or 18, 120/1024 for 13 or 17, 210/1024 for 14 or 16, and 252/1024 for 15 to go free. This is the standard statistical bell curve, skewed by 10 because of the prior agreement among the prisoners (which was not prohibited in the original post).

Looking again at the possibility of the king not being random in distribution of hat colors, a distribution of 10 red then 10 black will result in all prisoners going free under the above process, so one can argue that the selection of a pattern by the king is also a potentially random process, so the above numbers are still reasonable.

Stating these numbers differently, the probability of prisoners going free is as follows: at least 10 free - 100%, at least 11 free - 99.9%, at least 12 free - 98.9%, at least 13 free - 94.5%, at least 14 free - 83%, at least 15 free - 62%, at least 16 free - 38%, at least 17 free - 17%, at least 18 free - 5.5%, at least 19 free - 1.1%, all 20 free - 0.1%.

Regards--John M.

jmueller - "and the prisoners have agreed that the even prisoners will answer with the color of the person's hat ahead of them"

How could they agree? Let's follow the post rules. The original post states "you will not be allowed to look back or communicate together in any way (talking, touching.....)."

Let's assume that they could agree then all 19 would know what colour hat they had on because the prisoner behind them told them. The last person in the row that started the sequence would have a 50% chance by telling the person in front of him his hat colour. If by chance this person that started the sequence has the same colour hat as the one in front of him then he will be set free too. But they aren't allowed to agree so back to the drawing board!

Guest,

Perhaps I didn't word my reasoning well. The agreement made in advance is that whoever becomes the last prisoner in the line (an even-positioned prisoner) will answer with the hat color of the prisoner who is directly in front of him/her self. That prisoner (an odd-positioned prisoner) will then answer with the same answer just given, which is in fact the color of the hat on his/her own head. Then the next prisoner (even-numbered position) answers with the hat color of the prisoner next ahead. This continues for all 20 in the line. There is no discussion at the time the hats are placed on the heads and no one knows where they will be in the line until it is formed. Yet, every second prisoner from the back to the front will be told the color of his/her own hat by the prisoner immediately behind, who is allowed to see it according to the rules of the original post, and allowed to answer his/her "guess" about his/her own hat color. The ruler has no way to prove that the answer is anything other than a guess about his/her own hat color.

You are right, that the even-numbered prisoners, when giving the answer for the hat color of the prisoner next ahead does have a 50% chance of having guessed his/her own hat color correctly (assuming random distribution of colors). That is why I stated the probabilities as I did.

It is very difficult for a person to truthfully state the color on his own head if he is supposed to answer with the color of the hat on the next person's head and he has already been told his own color is different. However, if you are in that line and don't know your own color, yet know that telling the person in front of you his hat color also has a 50% chance of being correct for yourself, this is a reasonable risk you would be willing to take.

Thus, the position in line automatically frees every other prisoner, and the remaining ones each have a 50% chance of being freed too. Whereas, if each one is expected to answer with the color ahead, and knows his own color, then the temptation is present to save oneself by breaking the agreement made in advance.

--John M.

jmueller

You stated, "The agreement made in advance..."

There is no agreement per the original post, "you will not be allowed to look back or communicate together in any way (talking, touching.....)."

It seems (to me) either I have become totally inarticulate,
or readers are missing my posts. - please see #12 and #16.

Agreed, I may not have explained my solution well enough,
but how others can input solutions for 3 "prisoners" and write
..."about up to 15 can get free" etc. is completely beyond me.

The question, and parameter(s), was quite clear, and (I think)
my solution was readable, and workable; in practice.
(if a little confusing)

Please, could I ask the members to at least consider reading
my offerings (#12 & #16) and possibly, replace it with
something correct or better; eeeeeeeeeekkkk.

I thought Louis was mad.... (Durante)

jt.

jt, "b) if the colour hat of the person in front of them is different
to their own colour hat, they will call their own hat colour twice."

Read the original post..."He will be only allowed to answer "BLACK" or "RED". If he says anything else you will ALL be executed immediately...we move on to the one in front of him and ask him the same question and so on…" Not "BLACK BLACK" or "RED RED;" just "BLACK" or "RED." Looks like you just put your own variation in and that is completely beyond me why you should do such a thing.

Re Guest.

Agreed. They can only call black or red - which the prisoners do.
(the question does NOT say they can call their colour only once.)

i.e. - if the colour hat in front is red = call red.
and; if the colour hat in front is black, call red, red.
Both calls being
i) correct to the question; and
ii) informing the next prisoner inline of their colour.

The sequence is:

20th calls red or black - according to the hat in front. (19th)
IF.. he has no considered knowledge. e.g. 10/10 hat info. etc.
This clearly tells 19th the colour of his hat. i.e.

19th calls according to 20th - who has now informed him of his colour.
That is, 19th calls HIS own hat colour. (given from 20th)
Either once, or twice, (according to the 18th colour.) and goes free.
This has informed the 18th of his hat colour.

18th calls HIS colour - once, or twice, (according to the 17th colour)
goes free.

17th calls HIS colour (once, or twice, according to the 16th colour)
goes free.

16th calls HIS colour (once, or twice, according to the 15th colour)
goes free.

etc. etc.

1st calls HIS colour (once) goes free.

At least 19 can go free; and probably 20. (depending)

Hope this is a much clearer solution.

jt.

I see an inconsistency in the way the question is posed.

He will be only allowed to answer "BLACK" or "RED". If he says anything else you will ALL be executed immediately.

Because of this wording, you could see that ALL prisoners would be killed right away if the last prisoner in line made the wrong guess. Then there would be no need to ask the other prisoners what color their hats are.

Anyway, here's the spoiler.

3Doug -

I also agree that there appeared to be an inconsistency with the way the question was posed.

Thank you for the link that helped to shed light on the answer(s).

The number of hats (prisoners) can be infinite provided a prior code is made by the prisoners using the same allowed word. (The rules state: one word, taken as using the same word, and not being taken as using a single word.) That is, the same one (correct) word may be repeated more than once.

With this prior collusion the prisoners can go free. E.g. if there were 20 prisoners inline with 20 various blue and red hats. The 20th, last in line, without any considered or prior information, would be at risk. However, by calling the hat colour of the 19th prisoner (in front of him) he has a 50/50 chance of going free; and guarantees the 19th prisoner can go free.

The 19th now calls (correctly) his own hat colour (as informed by number 20) and; if prisoner 18 (in front of number 19) has the same colour hat, the correct colour 19 calls will also confirmed the same colour to prisoner 18.

However, if prisoner 18 has the other colour hat, prisoner 19 repeats his own correct hat colour twice. As previously agreed between the prisoners, this repeat, of the same correct colour word, informs prisoner 18 that his hat colour is actually the opposite colour to that called by prisoner 19. Simply: the repeat of the same, correct colour word informs the next prisoner in line that his hat is of the other colour. That is, a repeat (of the correct colour) toggles that colour, for the prisoner in front. i.e. red=red. red,red,=blue.

This toggle can be used by all the prisoners each in turn, who will both correctly call their own colour every time; either once or twice, and so doing, will also directly inform the prisoner in front of the colour they have to correctly call. Enabling in this instance, at least 19 prisoners to go free, and possibly all 20.

For those who disagree with the solution of using the one (correct) word more than once, my solution can be varied by different use of the toggle for one word. Just the one word could be said, e.g. either loudly or softly. i.e. If the hat in front is the same colour, the correct colour is called softly; and, if the hat in front is of the other colour, the correct colour could called loudly.
(Either way I'll get the prisoners free, if it kills me!)

jt

I had a few words with the wife... she had a few paragraphs with me.

To make the puzzle even harder, you could not give the clue to line themselves up. Just say the king put them in a room, no talking, no signalling. They are allowed to say one word only 'red' or 'black' and then they must immediately leave the room. Then the reader would have to figure out that they need to line themselves up and go from there as given in the solution.

#20 says red IF THE TOTAL NUMBER OF RED HATS HE SEES IS EVEN (Could just as well be for odd, as long as the others know, its an arbitrary choice). If he's lucky and his hat is red, he's saved, else BLAM! Now #19 looks and sees the rest. If he sees an even number of reds, his own hat is black, so he calls black. #18 looks and sees an odd number of hats, so his hat must be red to make the total even, calls red. #17 is listening carefully,when he hears #18 say red, heknows there are now an odd number of reds left. If he sees even, his own hat is red, else black,

And so on...

Dad helped me, facking smart

Good Answer

Shame others have stopped reading.

Here are two answers that require that everyone is present when the other prisoners answer, but allows for any rules that prohibit saying anything other than red or black, shouting, or repeating (the king doesn't seem so nice and would obviously catch on to the aforementioned). It also doesn't require the prisoners to know the number of each color ahead of time.

This one may not be the most practical solution - in a perfect run, there is a good chance that everyone survives. Unfortunately, it is possible that all fail as well. Here goes: having a night to think things over, the prisoners work out a timing mechanism. As they line up on execution day, #20 quickly makes a count of the least frequent hat color. At the moment the question "WHAT IS THE COLOR OF YOUR HAT?" is done, he begins a slow measured count based on a predetermined mantra (i have practiced this before with people and it is very possible, especially with a whole night to rehearse), one measure for each of the least frequent hat, and then answers that color. Everyone is repeating the same count in their head, silently, of course. Well practiced, everyone in line now knows how many of one of the colors is. If they see that many in front of the them, they know they are the opposite. If they see one less, they are the lesser appearing color, and as they answer, each person in front of them subtracts one from the count. The success of this method is much much higher if the executions are immediately known to everyone else, as the count could always be repeated for confirmation after a failure. These pauses would be reasonalble and likely tolerated for the first person or after someone is killed. Done properly, everyone survives except #20, who is left with a 50/50 chance. Poor counting and pacing without feedback could end in a 100% execution however, so...

There is a second method with a pretty decent survival rate. #20, #17, #14, #11, #8, and #5 answer RED if the two hats in front of the them are the same, and BLACK if the two hats are different. That saves 19, 18, 16, 15, 13, 12, 10, 9, 7, 6, 4, and 3 unequivocally. In addition, 2 saves 1 by telling them the right color. Thus, at most, 7 die, but probability suggests the survival rate would be closer to the 16 or 17 level - pretty good if you ask me. The question is, would the sacrifices still be willing to do their job properly if they looked ahead and saw only black hats? ;-)

Okay.. forget the count - that odd even thing is fraking smart!

i can think of only this....

# 20 can see colour of # 19 hat. his answer will be that colour. so now # 19 knows what is colour of his hat.

he will then answer the same colour as #20 said.

but he must tell #18 if that is the colour of #18 hat or not.

for differentiating, they must form a code.

for example:

if # 20 says black

# 19 also says black ... but very loudly so as to inform # 18 that this is the same colour of your hat...

or very slowly so as to inform # 18 that this is not the colour of your hat....

so everybody must listen carefully to the colour and voice level of the person behind him to know what colour of hat they are wearing.

just that poor #20 is in danger,,,,,

he may answer right or wrong....... 50% chances are still there of living....

This idea is somewhat of a combination of some of the ideas posted but should result in 19 or 20 of the prisoners going free. There actually is a way for the prisoners to communicate during the executions, but instead of with words, they communicate with silence. a 15 second pause would mark that the individual in front of the person up has a different color hat than the person up. so it would go something like this:

1st to be executed would just say the person in front of him's hat color, unless it appears to go red black red black etc, in which case he would take a 15 second pause, and then answer the opposite color of the hat the person in front of him has. So as an example, assuming that the hats were assigned randomly, the first person would immediately answers black, the color of the hat in front of him. Then he lives or dies. Next person would see black again, and say black immediately. Then the next person sees red, so they take a fifteen second pause, and then answer black, so that the next person knows to answer red. and so on and so forth.