Hey, this one is not that easy. not impossible, but not that easy either. it was asked for my lab partner in a job interview
there are 100 death row prisoners. the guards decided to execute them in the following way. they will make the prisoners sit in a row, and they will put a hat on each prison, either red or blue (colors doesn’t make a difference) then they will start from the prisoner sitting in the back , they will ask him what is the color of your hat, if he got it right they won’t shoot him, if wrong they will shoot him.
each prisoner can see all the prisoners in front of him and can hear all the prisoners before him and of course the gun shots.
now the prisoners were told that this is the way they will be executed, so they need to figure a plan to save the most number of prisoners. of course assume selflessness in all prisoners, so they all care about the overall number of saved prisoners.
very small hint: ALOT OF PRISONERS can be surely saved.
Well theoretically couldn’t all of them be saved except for the first?
each person simply tells the person in front of them what they’re wearing, and then, since no one can do this to the first guy, he has to take a shot. (unless there are 50 of each color and then you could just ask each prisoner to yell out their color and tally them) am i right?
nice one! at least 99 can be saved for sure, and with little luck 100 can be saved! I won’t say how unless s3d let me do!
oh no shit! that was a quick answer! I will take it back!
Now am sure, 50 prisoners can be saved for sure! the rest have undefined chance of surviving!
all can get free
thats an easy Game theory question
We can arrive at this by considering some of the simpler cases. Let’s assume that the warden placed only 1 Blue hat on my head and 99 black hats on everyone else’s head. So at the time when the warden said start, I would look around and see 99 black hats. Since there has to be at least one 1 hat, I would immediately announce that I had a Blue hat. Everyone else would then know that they had black hats and would say so.
Now consider the case where I have a Blue hat and someone else also has a Blue hat. I would look and see 1 Blue hat. If I had a black hat, that person would immediately announce that they had a Blue hat. But that doesn’t happen. Instead they wait. Now since neither of us was able to announce right away, we know that there must be 2 Blue hats. So we both announce that we have Blue hats.
You can follow this pattern with 3 Blue hats, etc. but it requires that you have a plan in place for timing. Let’s say that everyone will wait ten seconds for every hat they see less of. So if I see no Blue hats, I will immediately announce “Blue” after 0 seconds. Everyone else will follow with “BLACK” right after. Similarly, if I saw 1 Blue hat, I would plan to say Blue after 10 seconds. If no one announced after 0 seconds, I would be correct. Then everyone else would say “BLACK” after that.
It doesn’t matter the number of hats or whether there are more or less of one color as long as we wait a discrete period of time to announce. I chose periods of 10 seconds so that there wouldn’t be a chance of mistakes.
If there are W Blue hats and B black hats, then:
Everyone wearing a Blue hat will see W-1 Blue hats and B black hats.
Everyone wearing a black hat will see B-1 black hats and W Blue hats.
There are 3 cases:
If W < B then all Blue hats will say ‘Blue’ at the same time (10(W-1) seconds), and everyone else knows they are wearing red
If B < W then all black hats will say ‘Black’ at the same time (10(B-1) seconds), and everyone else knows they are wearing Blue.
If W = B then all prisoners will know their color at the same time. (10(B-1) seconds, or 10(W-1) seconds, they are equivalent).
Let’s take an example. If there were 51 Blue hats and 49 black hats, and I was wearing a Blue hat. Then I would plan to say “black” after 490 seconds. However, the people in black hats would beat me to the punch saying “black” after 480 seconds. Then I would say “Blue” along with all the rest of the prisoners wearing Blue hats.
The “hat puzzle” is described in detail at Wikipedia and I’ve included the link below. I think the first answerer quoted from there but didn’t include the reference.
Source(s):
http://en.wikipedia.org/wiki/Hat_Puzzle
also
The mathematics of this type of puzzle (although not this one
specifically) are discusssed in this document:
http://www.hpl.hp.com/infotheory/hats_extsum.pdf
and
http://www.stanford.edu/~cpetriuc/puzzles_wSolutions.html
and for those who took a communication course
this puzzle is like the Hamming code solution
see
http://en.wikipedia.org/wiki/Hamming_code
copy and paste doesnt count ! ur a cheater severO shame on u !
i love copy and paste, and the internet ofc
with them, i dont need to understand a thing ,
true, thats why i wont try to solve the puzzle, but i wont ruin it for the ppl who like to think ! u should wait 3 days before posting a solution imo
P.S : imo= in my opinion
severus! what u post is a solution for a different type of questions! in ur case the guy can see every ones hat, but not his. in s3d examplem he gets to see only guys infront of him!
2nd, this was an interview question, unless they do not want that guy to join them, they will not ask him this question! it is a thesis man, and not a solution
Severus, COM’N why u didn’t even try.
and your answer is first for different question and it is not the one i am looking for.
the first guy guess will only save 50 people for sure, you can save more people for sure
i have to be honest though, i think we can alter severus answer to fit this question where the first person will count the blue hats and for every blue hat he says he delays his answer 10 seconds, so everyone elses know the number of blue hats, so by counting blue hats in front of you u can figure out what is on ur head. but let’s assume the guards won’t let you take as much as u want and they will shoot you in 5 seconds if you don’t answer.
just clearing for the first person answer again, the first guy will say the hat of the next guy. Now the next guy can’t say the hat of the third guy because he want to save himself, so he will actually say the color the first guy said, so the third guy has to guess again or sacrifice himself by telling the one in front of him his color.
I was thinking in the 10 secs thingy! but if u were the gardues u can figure a way to excute them all using this method!
i just told the 10 seconds delay to the lab partner, he said u r not allowed to convey ANY message through ur answer besides red or blue. his example was whispering versus shouting. so the first one simply say the color of the one in front of him, for example it was red. so the second one either whisper red or shout red depending on the third guy, so whenever a whisper means red. this works, but again u r not allowed to send any message with the “blue””red” answer.
this kills severus cheating solution. keep thinking though and tell me any interesting ideas cross ur mind. it took me good amount of time and i ended up using couple of hints.
i cant try, am simply stupid
i really am
dude u are not stupid! Severus, do not think that math or physics or solving any puzzle means u r smart, nor it means u r not!
When it comes to networking, ur just to smart to be true, and u know that!
and btw, the answer to my solution is u are that u are gaurds, u can kill them with or without a reason =) kinda like bohr answers x)
i like that answer
bs seriously, i am stupid
just ask
so, supreme ki, do u have an answer? u mentioned before u had an answer then u said u were too quick to judge, so what about now?
ask me about severus ! and gololo kol 3am wenta bkher ! 😀
yea man! it is the forth comment here man!
u did not see it?
or u want another answer?
tell me!
sorry it is the fourth x0
see, I had 3 comments, at 11:49, 11:51 and 11:56 i think! see them up!
50 is not enough, u can save much more
here is the biggest hint
u can SURELY save 99 prisoner
u can use ur voice to signle a msg! can this be used?
we have been through this, u r not allowed to convey any kind of message through saying blue or red except the fact that u said blue or red
shit!!! using odd and even sequance x) is this true or not? my mind is not stable now tell me quick?!
u have to say in a little bit more details what do u meant by even and odd, because this can be the right answer and it can be not
see, the first guy has to say the number infront of him that is odd, i mean there are 99 guy infront and so one of the colors has to be odd, now if the second guy heard red lets say and saw that there are even number of red infront, that means his is red, now the next guy has to follow up and do the same and so all can be saved for sure! is it true?
i solved it….x-ray vision goggles, every prisoner except for the first one (he is poor) wears one and see the hat by himself. this is how u save 99 prisoners.
MALIK, how the heck an x-ray vision goggles will help????? FIRST x-ray can’t see color, second, u already can see the color of the hats in front of you and X-ray goggles don’t help you seeing your own !!!!!!!!!!! what the ….. malek?
that would be a good one! or u know, the gaurds can color the rare half with a color and the front half with another and then excute them all heheheh!
dude tell me is my answer right or nottttt
ok, yuri officially got it. and he gave a new hint, it get to do with evens and odds
i swear we ended up just choosing the answer i chose…
but wasn’t my answer just common sense?
surely there is an actual sneaky answer to this question!
the answer spreme ki gave me is not posted and your method only saves 50 for sure, i am saying you can save 99 for sure.
each prisoner has one shot, so u can’t say the color of your own hat AND tell the one in front of you his color, only one of these two can be accomplished.
and there is no distribution for the colors at all, so not necessary 50/50
here is the answer
.
.
.
.
.
.
.
.
.
.
you consider red equals 0 and blue equals 1, and the first guy will count the blues in front of him.
if the count was odd, he will say blue, if even he will say red.
let’s assume there was 40 blue and 55 red, so the first guy will say red because the blues are even, so the second guy will know that the number of blues is even, so he will count all the blues in front of him, if he found them 39 (odd) that mean he is a blue, if he found them 40 (even) that means he is red. and the third guy will already know what the second guy was, and by counting all the blues in front of him, he can figure out his hat. ..etc till all 99 are SURELY SAVED, only the first one my get the bullet
So you have a bullet to you head and 99 prisoners infront of you. How the heck can you count 99 people’s hats and then decide the odd and even in 5 seconds (or even 10 seconds)? And when did the prisoners decide on this scheme? Before they communed to be executed! Because usually, the 100 people will not be together… even if they were, chances are someone will miss up…
hehehehhe, thanks for your input, but we assumed that the prisoners are smart enough and have a brotherly bond that prevent them from cheating.
there is no limit for answering the question, or let’s assume 10 minutes limit. the intro to this puzzle that the prisons are overcrowded, so they wanted a scheme to kill some, but to leave some hope rather than random selection, this way they will prevent uprising.
in real world something similar is used, example, if A hits B and when asked why he says unless C gives me something i will keep hitting B. this happen on country level and i prefer not to give political examples.