Discussion about math, puzzles, games and fun. Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ π -¹ ² ³ °

You are not logged in.

- Topics: Active | Unanswered

**salem_ohio****Member**- Registered: 2016-03-11
- Posts: 35

Five prisoners are arrested for a crime. However, the jail is full and the jailer has nowhere to put them. He eventually comes up with the solution of giving them a puzzle so if they succeed they can go free but if they fail they are all executed.

The jailer gives all the prisoner party hats: He gives each prisoner one hat, which can be of any of the following colors: Cyan, Magenta, Yellow, Red, Green. Given that there are more than 5 hats of each color, it is possible that more than one prisoners wear hats of the same color.

Each of the prisoners only see the hats of the others but not on himself.

If any prisoner can figure out and say to the jailer what color hat he has on his head with 100% certainty, all five prisoners go free. If any prisoner suggests an incorrect answer, all five prisoners are executed. Communication among the prisoners is allowed only before they put the hats on and is prohibited afterwards. They all write their guess on a piece of paper simultaneously, without anyone reading each other's guess.

What strategy must they follow so as to go free?

Offline

**thickhead****Member**- Registered: 2016-04-16
- Posts: 1,061

One prisoner groups others according to the color of their hats. If there emerges any group one of the group will announce the color of the hat by looking at others in the group. If there is no group (all 4 having different colors) any other person will group the first person to the color of his hat. If now also group is not formed the first person can tell the color of his hat by missing color.

I think the prisoners are executed by now.

*Last edited by thickhead (2016-04-30 19:27:48)*

**{1}Vasudhaiva Kutumakam.{The whole Universe is a family.}(2)Yatra naaryasthu poojyanthe Ramanthe tatra Devataha{Gods rejoice at those places where ladies are respected.}**

Offline

**salem_ohio****Member**- Registered: 2016-03-11
- Posts: 35

For sure, unless you come up with some idea!!

thickhead wrote:

I think the prisoners are executed by now.

Offline

**thickhead****Member**- Registered: 2016-04-16
- Posts: 1,061

I have come up with my idea as above.

**{1}Vasudhaiva Kutumakam.{The whole Universe is a family.}(2)Yatra naaryasthu poojyanthe Ramanthe tatra Devataha{Gods rejoice at those places where ladies are respected.}**

Offline

**Lessismore****Member**- Registered: 2016-06-02
- Posts: 3

I think there must be an error in the question. One prisoner has to risk getting it wrong - surely it should be that one prisoner has to be right for them all to go free.

E.g. Prisoner 1 writes x if he can see odd number of colour 1, y if he can see even number of colour 1.

Prisoner 2 does the same with colour 2, 3 with 3, 4 with 4.

Prisoner 5 can therefore ascertain what is on his head. Not sure how you do it simultaneously though

Offline

**thickhead****Member**- Registered: 2016-04-16
- Posts: 1,061

Hi Lessismore,

you have almost solved it. I had thought making notes was as good as useless as others can not read it but of course paper has 2 sides and people can see on which side you are writing.By prior mutual understanding each person is given one color to look upon. if he sees odd number of hats he will write on **front side**else on **backside**. if 1st person is to comment on color cyan and shows it as odd,one of the other person wearing sees even number of cyan hats (excluding 1st person) and knows that he is wearing cyan hat. Problem occurs when 1st person sees no cyan hat. Then the information that he has seen zero cyan hat does not give any clue. then you have to depend on 2nd person. If the same case of not seeing any hat of his color occurs for all 5 nobody can decide but that is the decision point. each is wearing the hat of the color which he is supposed to keep tag. So everybody knows the color of his hat. Could we decide also on throwing pen to front,left,right or back side to convey the number of hats he sees.

*Last edited by thickhead (2016-06-28 05:07:40)*

**{1}Vasudhaiva Kutumakam.{The whole Universe is a family.}(2)Yatra naaryasthu poojyanthe Ramanthe tatra Devataha{Gods rejoice at those places where ladies are respected.}**

Offline

**samuel.bradley.99****Member**- Registered: 2016-03-16
- Posts: 44

This is the solution I propose:

We have 5 available colors, so, in order to transmit the information to the others, we will use this method:

We have 5 different values of mod(5): 0, 1, 2, 3, 4.

They coordinate and agree the following:

They assign these 5 values to the five hat colors Cyan, Magenta, Yellow, Red, Green.

0: Cyan

1: Magenta

2: Yellow

3: Red

4: Green

They also assign themselves with one of the numbers 0 to 4 (i.e. the 1st prisoner is assigned with number 0, the 2nd with 1 etc).

The above is pre-agreed before they wear the hats.

After they wear the hats, they do the following:

Then each prisoner calculates the sum of the numbers of the hat colors, based on the above table and DEDUCTS this number from his own and then converts the difference to mod(5). Then he finds the color that this number corresponds to, based on the above table.

Example: Suppose the 2nd prisoner sees the following hats to the other four: 1st-3rd-4th-5th: Cyan-Cyan-Red-Green. Let's assume his own hat is Yellow.

Then he calculates the sum 0+0+3+4=7. His own number is 1 (because he is the 2nd and number 1 is assigned to him). He deducts 7 from 1 and converts the difference (6) to mod(5) = 1. Then he guesses that he wears a Magenta hat. Obviously he is wrong, but let's see what the others will guess (because, even if all are wrong and ONLY one guesses correctly, they are saved).

The 1st one sees Yellow-Cyan-Red-Green and calculates the sum 9, which he deducts from his own that is 0, so the remainder is 9 which is 4 mod(5) so he guesses that he wears Green, which is also wrong because he wears Cyan.

Similarly the 3rd guesses Yellow and is wrong because he wears Cyan,

the 4th guesses Red which is CORRECT

and the 5th guesses Magenta and is wrong because he wears Green.

We therefore see that they are saved because always, at least one will guess correctly, based on the above strategy (the key here is that they are each assigned one different number of the 5 mod(5) so at least one will be correct).

Obviously no one knows the sum of all colors, since each of them does not see his own hat, but we know for sure that it will be one of the 5 numbers 0-4 mod(5).

We know, though, that it is sufficient that at least one finds the correct color, then at least one will have the number that will be the same as the correct sum of the hat colors, so he will announce the correct color!

*Last edited by samuel.bradley.99 (2016-06-28 07:05:23)*

Offline

**thickhead****Member**- Registered: 2016-04-16
- Posts: 1,061

Hi Samuel.bradley.99

The idea is not clear. Needs more explanation.

(2)Yatra naaryasthu poojyanthe Ramanthe tatra Devataha

{Gods rejoice at those places where ladies are respected.}

Offline

**samuel.bradley.99****Member**- Registered: 2016-03-16
- Posts: 44

Hi Thickhead - I did some edits and think now it's more clear.

thickhead wrote:

Hi Samuel.bradley.99

The idea is not clear. Needs more explanation.

Offline

**thickhead****Member**- Registered: 2016-04-16
- Posts: 1,061

Deducting 7 from 1 gives -6 and -6 mod 5 =4 and then problem setter says " If any prisoner suggests an incorrect answer, all five prisoners are executed."

(2)Yatra naaryasthu poojyanthe Ramanthe tatra Devataha

{Gods rejoice at those places where ladies are respected.}

Offline

**thickhead****Member**- Registered: 2016-04-16
- Posts: 1,061

I want to add a provision to what I wrote in #6. If 1st person sees no cyan hat he will not scribble anything so that others will know that he has nothing to tell.

(2)Yatra naaryasthu poojyanthe Ramanthe tatra Devataha

{Gods rejoice at those places where ladies are respected.}

Offline