I take it the black, white, grey hats are randomly distributed, not any pattern?

I take it the prisoner can't see his own hat for some reason?

Solved

Posted on 2005-04-13

this question, I know the solution, just wanted to challenge the great forum here.

100 prisoners stand in a column, last prisoner see 99 prisoners in front of him.

prisoner N+1 see N prisoners in from of him. each see only back. no communication is allowed.

each prisoner been given a hat colored White OR Gray OR Black.

the jail manager ask the 100th prisoner what is the color of his hat, prisoner must answer 1 of the 3 colors,

each prisoner hear the answer.

then jail manager ask same question the 99th prisoner and so on.

at the end, if at least 99 answers are correct - all prisoners are free, else all die.

no tricks - pure mathematics

delay answer, change tone, lowd / wisper : all are not allowed

the only information the prisoners have:

1) what been told until now (what, and not how ...)

2) what they can see in front of each.

3) they all agreed to use a specific algorithem

find out how

100 prisoners stand in a column, last prisoner see 99 prisoners in front of him.

prisoner N+1 see N prisoners in from of him. each see only back. no communication is allowed.

each prisoner been given a hat colored White OR Gray OR Black.

the jail manager ask the 100th prisoner what is the color of his hat, prisoner must answer 1 of the 3 colors,

each prisoner hear the answer.

then jail manager ask same question the 99th prisoner and so on.

at the end, if at least 99 answers are correct - all prisoners are free, else all die.

no tricks - pure mathematics

delay answer, change tone, lowd / wisper : all are not allowed

the only information the prisoners have:

1) what been told until now (what, and not how ...)

2) what they can see in front of each.

3) they all agreed to use a specific algorithem

find out how

17 Comments

I take it the black, white, grey hats are randomly distributed, not any pattern?

I take it the prisoner can't see his own hat for some reason?

prisoner can't see hats of prisoners behind him.

no pattern, any combination of 3^100 is possible

99 then says the color of his hat in

French if the 98th hat is white

German if the 98th hat is grey

Russian if the 98th hat is white

then 98 can say the correct color of his hat in a language chose according to the hat of 97, and so on.

I think my lawyers can get this past the 'no tricks' clause

I want to make sure I understand the problem.

Person number n+1 can only see hat number n. Is that right?

Person number n+1 is supposed to say the color of his own hat (n+1)? Or can he say the color of hat n?

There are supposed to be a total of 99 correct answers, and it doesn't matter whether the color announced matches the hat worn by the person announcing the color?

Can we make the set-up a little more civilized -- let's not kill the people in line, let's just give them ice cream if they meet the challenge, and nothing if they don't.

mathbiol

>100 prisoners stand in a column, last prisoner see 99 prisoners in front of him.

>prisoner N+1 see N prisoners in from of him. each see only back. no communication is allowed.

each see only the back side of the prisoners that in front of him

prisoner N+1 see {N,N-1,...,2,1}

also prisoner N+1, will be asked by the jail manager, AFTER he heard all answers from {100,99,..,N+3,N+2}

white =both odd grey=both even black=different

so if he says white ie they are both even and the 99th prisoner sees an even number of white and grey hats ie they are the same for him as well then he knows he has a black hat on.

From this the 98th can determine that the 99th prisoner see the same even parity of white and grey yet that he sees they are different and that here are an odd number of white hats in front of him which means he has a white hat on

From this the 97th prisoner can detrmine the 98th can see an odd number of white and an even number of grey hats yet he see an odd number of both so he knows he has a grey hat on

etc etc.

The 100th prisoner reports the parity of the white and grey hats, with a prearranged code

white =both odd, grey=both even, black=different

(I have not explained the solution terrible well but basically if the parity of 2 of the hat colors are know , ie both even, both odd or both different then all the colors can be determined.)

Say the parity of white and grey hats are the same for the first 98 people

Prisoner 100 says Black, -> different.

Is prisoner 99's hat grey or white? She can't tell. All she knows is that it's not black.

Set order BWG. When I say follows, I mean if the 2nd prisoner follows the 1st and so on.

For each black hat:

If white follows it, add 1.

if grey follows it, subtract 1.

If black follows it, do nothing.

For each grey hat

if white follows it, subtract 1

if grey follows it do nothing.

if black follows it, add 1.

For each white hat

If white follows it, do nothing

if grey follows it add 1

if black follows it subtract 1.

At the end if we have a number

0 mod 3 = "WHITE"

1 mod 3 = "GREY"

2 mod 3 = "BLACK"

The 99th person can calculate up to the person in front of him.

So if the number the 99th person calculates:

- matches the number the 100th prisoner called out, he's got the same color hat as the guy in front

- is 1 greater then the number (by color) the 100th prisoner called out, he's got a hat where he has to subtract 1. Eg. if he sees white it's black. if he sees grey, it's white. If he see white, it's black.

- is 1 less then the number (by color), he has to add 1.

I think I complicated things. You should just add up the hats.

White = 0 mod 3

Grey = 1 mod 3

Black= 2 mod 3

Since everyone knows all the hats in front, and all the hats behind (except for 100) they can easily figure out their own by subtracting the called out value from the added up value.

2 years ago, my brother in law, followed me this question, for a while I wasn't sure the details are correct, and asked him to check for the source of the problem. meanwhile I had the strong will to solve by my self, and found a solution.

as I couldnt believe the Q as it is, has solution without tricks, I now believe the Q has unique solution.

since at least, from my prev comment, you give here some progress, I'll guide you a little:

try to solve the Q for 10 hats, 2 colors,

then ,and only after :

try to solve the Q for 10 hats, 3 colors.

jkmyoung :)

White = 0

Grey = 1

Black= 2

100th guy sums hats 1-99 modulo 3 and calls corresponding color. He is probably wrong about his own color, but that doesn't matter.

99th guy calculates sum of seen hats 1-98 modulo 3, subtracts it from 100th guy's declaration. The difference is his color (modulo 3, of course).

98th guy calculates 100th's declaration - sum of seen hats 1-97 - 99th's color modulo 3, and declares that color.

...

nth guy calculates 100th's declaration - sum of seen hats 1-(n-1) - sum of declarations of (n+1) through 99 modulo 3 and declares that color.

...

1st guy calculates 100th's declaration - sum of declarations of 2 through 99 modulo 3, and declares that color.

last night i had no time to "compile" and "simulate" your algorithm, u r right.

compare it with my solution, they are very close, someone my have time to proof both are equal:

100 count the 99 hats : X=White % 3 , Y = Grey % 3, Z = Black % 3

X,Y,Z can be :

1) all the same : 100 say the word "White"

2) 0,1,2 in the cyclic order White -> Grey -> Black (ie: W=2,G=0,B=1 OR W=1,G=2,B=0) : 100 say "Grey"

3) 2,1,0 in the oposite order : 100 say "Black"

this algorithm is lightly easier for the prisoners to apply are learn, and therefor maybe they won't make mistakes...

GwynforWeb : I checked jk algorithm for 4 colors: (R = Red)

W after W: same

G after W: +1

R after W: +2

B after W : -1

after G:

G : same

R : +1

B : +2

W : -1

and so on

from my point of view, It's working well.

the sum (mod 4) given by 100th to 99, summerize all the information, and with what 99 sees, he got complete picture, and also following prisoners have complete picture as well.

great job,

and for summery, of course, don't forget you also to post here interesting problems.

tal

3)

I checked the difference between the solution I post here, and that given by jk, then rejected by jk himself , then Approved by Nova & Gwyn.

so,

I am with jk, his solution gives nothing, only the 99th can tell his oun color.

and I am very sorry, couldn't challenge you with this question, still, none solved it but me yet.

you are invited to review the algorithm I posted at last comment.

btw, Gwyn, as for N colors : proof that for 4 colors there is NO non-tricky solution.

tal

By clicking you are agreeing to Experts Exchange's Terms of Use.

Title | # Comments | Views | Activity |
---|---|---|---|

technology for 'real' windows (not OS) | 7 | 56 | |

Q1. Magnets and Electromagnetism | 33 | 81 | |

Random Variable | 2 | 35 | |

Triangle - calculating angles | 9 | 30 |

Join the community of 500,000 technology professionals and ask your questions.

Connect with top rated Experts

**11** Experts available now in Live!