Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 643
  • Last Modified:

3 colors 100 hats

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









0
Talmash
Asked:
Talmash
  • 6
  • 4
  • 3
  • +3
1 Solution
 
deightonCommented:
interesting, person 100 can't know the answer - so he might as well say the color of 99's hat so that he can give the right answer - but then I can't see how 98 is ever helped because 99 has no choice of answers to pass on info.

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?
0
 
TalmashAuthor Commented:
prisoner can't see his own hats,
prisoner can't see hats of prisoners behind him.

no pattern, any combination of 3^100 is possible
0
 
deightonCommented:
the 100th prisoner simply says the color of 99th prisoners hat. (so 100 may use up the 1 wrong answer)

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
0
What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

 
TalmashAuthor Commented:
your lawyar maybe executed as well.
please accept my sincere condolence
0
 
mathbiolCommented:
Talmash,

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
0
 
TalmashAuthor Commented:
clarify what written above:

>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}

0
 
GwynforWebCommented:
The 100th prisoner reports if the parity of the white and grey, with a prearranged code

 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.
0
 
GwynforWebCommented:
shld read

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

 white =both odd,    grey=both even,    black=different
0
 
GwynforWebCommented:
ps that is a really cool problem,  I sort of remembered in the back of mind the problem for just black and white  hats and had to dig deep to remember it, but had never seen it for 3 colors.

(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.)
0
 
jkmyoungCommented:
I don't agree with the last solution.
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.
0
 
jkmyoungCommented:
Here's a little more complicated way, but I think it works.
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.
0
 
jkmyoungCommented:
Shoot, this doesn't work. If the person in front of you and behind you have the same colour, you can't tell a thing.

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.
0
 
TalmashAuthor Commented:
well, about this question;

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 :)
0
 
NovaDenizenCommented:
I think jkmyoung has it.
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.

0
 
GwynforWebCommented:
...this generalises to N colors.
0
 
TalmashAuthor Commented:
hi, very nice indeed jk !

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)
0
 
TalmashAuthor Commented:
hi all.

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
0

Featured Post

Free Tool: Path Explorer

An intuitive utility to help find the CSS path to UI elements on a webpage. These paths are used frequently in a variety of front-end development and QA automation tasks.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

  • 6
  • 4
  • 3
  • +3
Tackle projects and never again get stuck behind a technical roadblock.
Join Now