wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> SINGLE-FILE HAT EXECUTION
        
(Message started by: oneself on Jul 28th, 2002, 9:34pm)
Title: SINGLE-FILE HAT EXECUTION
Post by oneself on Jul 28th, 2002, 9:34pm
Single-File Hat Execution (http://www.ocf.berkeley.edu/~wwu/riddles/hard.shtml#singleFileHatExec)

This one is really giving me the run around.

The hint says you can guarantee N-1 saved.  But I was thinking
and really only the first prisoner can pass along information to the others,
and maybe die, at that point everyone else MUST know what color
hat they have on AND use that information to save themselves.
Therefore they can not pass along any more usefull information, unless
they say their answer in a low voice which means the next guy has a
blank hat on or a high voice if it's white.  Only I hope that is not the
answer.

If half the prisoners sacrifice themselves they can save the other half,
by saying what color that hat in front of them is instead of their own.
But that only gaurantees N/2.

That is my best solution so far.

//Link added and Title changed by moderator//
Title: Re: SINGLE-FILE HAT EXECUTION - HINT PLEASE?
Post by william wu on Jul 29th, 2002, 1:58pm
There's no voice intonation tricks; if the problem had that much freedom, it would be trivial ... people could tap each other on the shoulder, or use mutant telekinesis powers.

It is not exactly true that what the 10th prisoner says (I refer to the 10th prisoner as the last person in line, who is the first person the executioner prompts) can convey the colors of everyone's hats. This was what I thought at first as well.

However, it is true that what the 10th prisoner says should reveal the color of the 9th prisoner's hat.

Then, the 8th prisoner should be able to figure out his or her hat color based on information given by both the 9th and 10th prisoners.

The 7th prisoner uses information from the 8th, 9th, and 10th prisoners. And so on. So there's a cascading effect.
Title: Re: SINGLE-FILE HAT EXECUTION - HINT PLEASE?
Post by Gamer555 on Jul 29th, 2002, 7:54pm
Much of this is (including this and Greedy Pirates) is called (By me) "Yes, Yes, Yes" tactics (which was a problem like this, only WAY simpler) because like what da cool moderator said, you can make your decision based on what the others said.

My question is, does the solution involve sure things (like there is a logic that will say what is going on) used by the prisoners to obtain maximum saving, or is there probability (like kill yourself if there are more black hats then white, and don't if there are more white hats then black)

My (partial) solution is:

10: Kill yourself if 1,2,3 have more blacks than 4,5,6
9: Kill yourself if 2,3,4 have more blacks than 5,6,1
8: Kill yourself if 3,4,5 have more blacks than 6,1,2
7: ?

Will this work if 7 is given a boolean statement? Or is boolean logic out altogether?
Title: Re: SINGLE-FILE HAT EXECUTION - HINT PLEASE?
Post by Jon on Jul 30th, 2002, 7:36am
Look at the thread titled "Single file execution - want hint" or something like that for a discussion and the solution and a walkthrough.

jon
Title: Re: SINGLE-FILE HAT EXECUTION - HINT PLEASE?
Post by Peter on Jul 30th, 2002, 10:19am
I’m intrigued at how straight-jacketed men could tap one another on the shoulder but I don’t think it helps resolve this problem!

By definition Guy 10 can only communicate “black” or “white”. I assume if he says anything else he is executed and the game starts all over for the remaining 9.  So, for sake of example let’s assume he says “black” what might this mean?.

a) black could be the most prevalent colour and if everyone follows suit this only guarantees a minimum of 5 but 10 on a good day! Also, Guy 9 could ‘take a dive’ here and that compromises ‘n-1’ if 10 has already ‘copped it’.

b) black could be the colour of hat 9 and if all the even Guys declare the colour of the hat of the odd Guy in front of them we should, on average save 7.5 and on a good day 10 but no guarantee of 5+ here.

If we know the number of, say, black hats its all very easy everyone keeps a tally of “black” declarations, adds the number of black hats they see and subtract that sum from the known number to deduce their hat colour.

The dilemma I can’t resolve is how Guy 9 can communicate anything other the colour of his own hat, he must say that colour if he is to live and with a guaranteed ‘n-1’ I assume poor old 10 is the possible (he might fortuitously say his hat colour) ‘Fall Guy’.

Does exclusion of intonation also disallow a delay in response being a means of communication? It will work as each Guy is asked a question and no delay could mean your hat is the same colour as I'm saying and a delay means otherwise.

I’m rambling, .............. does any of this help?
Title: Re: SINGLE-FILE HAT EXECUTION - HINT PLEASE?
Post by Peter on Jul 30th, 2002, 2:47pm
Nope, it doesn't help at all, what does is looking at alternative forum board "single file execution (want hint)". Over & out!
Title: Re: SINGLE-FILE HAT EXECUTION - HINT PLEASE?
Post by Charlie949 on Aug 1st, 2002, 6:32pm
When this problem was first posed to me it involved 50 prisoners. I found a non-optimal but decent solution.

Let the first 6 prisoners who speak use the words "black" and "white" to signify one's and zero's in a binary number. This number can represent 0 <= x <= 64. This value can indicate the number of black hats (WLOG).

The optimal solution can be found at http://www.freuman.com/puzzles.htm
Title: Re: SINGLE-FILE HAT EXECUTION - HINT PLEASE?
Post by Luni_B on Aug 2nd, 2002, 12:36am
i thought about this one for a couple minutes...but i can save 9 of the 10 (also N-1) lives guarenteed, with a 50% chance of total salvation! :

It is agreed upon that the person ANSWERING first (last in line) will answer BLACK for an ODD, and WHITE for an EVEN.  Odd/Even applying to only ONE color hat(must be memorized by all...we'll say they picked BLACK to be the counted color)

Reguardless of whether the 1st person answered correctly, the rest of them can now deduce what color hat they have on by counting the same color hats in front of themselves.

For instance:
1st person answers = BLACK (odd)...
now 2nd person counts the black hats in front of himself and finds an odd number, therefore he knows his hat is white (for those not following: if he counts and finds odd he CAN'T have black on or the count would have come up even when the 1st person counted).  
The 3rd person now knows his hat is BLACK, because its even in front of him.  
The 4th person, knowing that the 3rd must have counted even, starts the whole process over again, bearing in mind that the person behind him saw an EVEN number of black hats...
etc etc etc - if you don't follow by now you won't.

FINALLY note that the 1st person to answer did so based solely on his count, therefore he had 50% of dying...
Title: Re: SINGLE-FILE HAT EXECUTION -SOLUTION
Post by jograd on Aug 2nd, 2002, 2:14am
This is your solution.

And this accounts for the N-1 probability.

Every man says the color of the hat of the man in front of him starting with the last guy.

Now the last guy answers first and he will never know what color his hat is. He has a 50/50 chance of living. He is the "-1" in the "N-1" probability. Therefore he will take a chance and say what color the hat of the man in front of him is and this goes down the line to the first guy and so everyone is sure to be saved except the last guy (#10).
Title: Re: SINGLE-FILE HAT EXECUTION - HINT PLEASE?
Post by Andrew Ooi on Aug 8th, 2002, 11:03pm
jograd, try your solution with a BWBWBWBWBW combination and see how well it works  ;D

There is another thread to this [single file execution (want hint)] same question where I have posted a generalized solution for N prisoners and K colour hats, where N-1 prisoners are guaranteed to survive and the remaining prisoner has a 1/K chance of survival.
Title: Re: SINGLE-FILE HAT EXECUTION - HINT PLEASE?
Post by pranava on Jun 5th, 2003, 11:53pm
All the prisoners got together and decided that they shout a number and colour. This would be similar to the roll call of people.
Eg. the 10th guy would shout "10 black" to signify the colour of caps on next two people in the row. (1: white, 0: Balck)
for exapmle if the arrangement is

           BWWBBWBBWW
the 10th guy would shout : 11 Black
9 th: 10 white.
and goes on...
the 10th guy always says black....
Title: Re: SINGLE-FILE HAT EXECUTION - HINT PLEASE?
Post by Icarus on Jun 6th, 2003, 4:58pm
The prisoners are only allowed to say "Black" or "White". Luni_B gives the best solution possible with no other means of communicating anything other than 1 of the two colors(though you will find it better explained on the other thread for this puzzle (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1027806438;start=0))

To summarize:
  • The prisoners agree in their meeting that the first person will call "black" if he sees an even number of black hats. Otherwise, he says "white".
  • Each remaining prisoner counts the number of "blacks" called out behind him, and the number of black hats he can see. If on his turn the total is odd, he must have on a white hat. If the total is even his hat must be black. He calls out the appropriate color.


The same logic will work for any number K of colors, except that you have to identify each color with an integer from 0 to K-1. The first guy adds up the numbers for all the hats in front of him, and figures out what additional number must be added to bring the total to a multiple of K. He calls out the corresponding color. Everyone else adds up the colors they see and the colors they hear, and also figure out what is missing to get to a multiple of K. That is the color of their hat.

There is no way for the first guy to ever have a better than 1/K chance of surviving - he must make his call without any information at all. But this guarantees the others will live. The only drawback is that you've got to have a "team player" in that first slot. You definitely don't want someone who would like to see everyone else dead!
Title: Re: SINGLE-FILE HAT EXECUTION - HINT PLEASE?
Post by James Fingas on Jun 10th, 2003, 9:33am
Icarus,

That's an interesting point--what if the very first person says the wrong colour? (incompetence, malicious intent, etc). If we know that the second person in line is following the strategy and still gets killed then the subsequent people in line can mentally reverse the answers of the first two to guarantee their survival.

But if person #2 assumes that person #1 was lying, but was wrong about it, then reversing the answers would get #3 killed. Of course if person #2 assumes that person #1 was lying and was right about it, then person #3 will die if he doesn't reverse his answer. Allowing maliciousness brings us much closer to the original 50/50 chance of dying...
Title: Re: SINGLE-FILE HAT EXECUTION - HINT PLEASE?
Post by Icarus on Jun 10th, 2003, 9:28pm
You can divide the prisoners into two types:
Lying-Suspicious-Stupid = says the opposite of what the scheme indicates.
Truthful-Trusting-Smart = says exactly what the scheme indicates.

Every time in the lineup that a LSS follows a TTS or a TTS follows an LSS, he dies.

Therefore, it is in the best interests of everyone (except the unhelpable #1) to try and minimize the number of transistions. So if you know that #1 is a slimy bastard, you let everyone know that they ought not trust him (so that He doesn't hear it of course). If not, then make sure everyone else is in complete agreement. But most particularly you want to make sure you know the demeanor of the guy immediately behind you. If you can agree with him, then you are safe, no matter what happens to everyone else.
Title: Re: SINGLE-FILE HAT EXECUTION - HINT PLEASE?
Post by Non-entity on Jul 22nd, 2003, 7:10pm
forgive me for not reading every post.

I am the ninth person in line.  I have been notified by the person behind me that my hat is black.  The hat in front of me is white.  How do I save myself (by saying black) and notify the person in front of me that his hat is white?

with the only signals I can say being "black" or "white" I am at a loss to save n-1.
Title: Re: SINGLE-FILE HAT EXECUTION - HINT PLEASE?
Post by Icarus on Jul 23rd, 2003, 4:44pm
If you want a hint: The first guy does not simply announce your hat color. He has to make an announcement that will allow everyone to deduce their own hat color from all the announcements they hear from behind and what they see in front of them.

If you want the full answer, read the posts - there are not that many of them.
Title: Re: SINGLE-FILE HAT EXECUTION - HINT PLEASE?
Post by coderyogi on Mar 4th, 2010, 8:27am

on 06/06/03 at 16:58:39, Icarus wrote:
The same logic will work for any number K of colors, except that you have to identify each color with an integer from 0 to K-1. The first guy adds up the numbers for all the hats in front of him, and figures out what additional number must be added to bring the total to a multiple of K. He calls out the corresponding color. Everyone else adds up the colors they see and the colors they hear, and also figure out what is missing to get to a multiple of K. That is the color of their hat.

There is no way for the first guy to ever have a better than 1/K chance of surviving - he must make his call without any information at all. But this guarantees the others will live. The only drawback is that you've got to have a "team player" in that first slot. You definitely don't want someone who would like to see everyone else dead!


If I get this correct, each guy has to add ALL previous calls made by other guys and then add this number to the addition of colors he can see out front to get his hat number? Coz as far as i can see, just remembering the previous call does not get the required color number.
Title: Re: SINGLE-FILE HAT EXECUTION - HINT PLEASE?
Post by rmsgrey on Mar 4th, 2010, 9:12am

on 03/04/10 at 08:27:57, coderyogi wrote:
If I get this correct, each guy has to add ALL previous calls made by other guys and then add this number to the addition of colors he can see out front to get his hat number? Coz as far as i can see, just remembering the previous call does not get the required color number.

Yep.

The first guy to speak describes a property of the entire line (apart from himself), so that changing the colour of any one hat would change what he says.

By listening to other people (correctly) identifying their own hats, and observing the hats in front of them, by the time they speak, every prisoner knows the colour of every hat other than their own (and the first guy's) so can use the first prisoner's statement to save themselves.
Title: Re: SINGLE-FILE HAT EXECUTION
Post by Aryabhatta on Mar 5th, 2010, 6:10am
Strange this is in Hard. The infinite version of this: http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_medium;action=display;num=1263428017

is in medium!

Either this thread should move to medium (I suggest doing that, but I guess it might contradict the riddle collection site) or that thread should move here.
Title: Re: SINGLE-FILE HAT EXECUTION - HINT PLEASE?
Post by coderyogi on Mar 5th, 2010, 11:00pm

on 03/04/10 at 09:12:45, rmsgrey wrote:
Yep.

The first guy to speak describes a property of the entire line (apart from himself), so that changing the colour of any one hat would change what he says.

By listening to other people (correctly) identifying their own hats, and observing the hats in front of them, by the time they speak, every prisoner knows the colour of every hat other than their own (and the first guy's) so can use the first prisoner's statement to save themselves.


Thanks!
Title: Re: SINGLE-FILE HAT EXECUTION
Post by rohigoyal86 on Nov 22nd, 2011, 2:39pm
10th guy has to say BLACK(if no. of caps which are more are in odd no.)
otherwise he will say white ( if no. of caps which are greater are in even no.)

suppose there are 9 guys in front of him
so cases may be

odd is greater;
7,2 ;
5,4;
9,0;
 
or even is greater;
6,3;
8,1;


in this way 9 can find out by counting no. of coloured hats which are in greater no.
slly by hearing his reply others can calculate.

10 and 9 have a probability of dying i.e 1/2.
rest 8 would be saved.
Title: Re: SINGLE-FILE HAT EXECUTION
Post by rmsgrey on Nov 23rd, 2011, 9:46am

on 11/22/11 at 14:39:04, rohigoyal86 wrote:
10th guy has to say BLACK(if no. of caps which are more are in odd no.)
otherwise he will say white ( if no. of caps which are greater are in even no.)

suppose there are 9 guys in front of him
so cases may be

odd is greater;
7,2 ;
5,4;
9,0;
 
or even is greater;
6,3;
8,1;


in this way 9 can find out by counting no. of coloured hats which are in greater no.
slly by hearing his reply others can calculate.

10 and 9 have a probability of dying i.e 1/2.
rest 8 would be saved.


Actually, by my calculations, your method will save everyone except those who see/hear four of each colour (and a "Black" from #10) and #10 himself. If the colours are split 5-4 (ignoring #10's cap) then the five with the majority colour are at risk initially. If mistakes are executed immediately, then only the first to guess wrong will die; if the executions wait until the end, then those wearing the other colour are reduced to guessing after each mistake - if cap colours alternate, then all ten could guess wrong...
Title: Re: SINGLE-FILE HAT EXECUTION
Post by rohigoyal86 on Nov 23rd, 2011, 3:17pm

on 11/23/11 at 09:46:26, rmsgrey wrote:
Actually, by my calculations, your method will save everyone except those who see/hear four of each colour (and a "Black" from #10) and #10 himself. If the colours are split 5-4 (ignoring #10's cap) then the five with the majority colour are at risk initially. If mistakes are executed immediately, then only the first to guess wrong will die; if the executions wait until the end, then those wearing the other colour are reduced to guessing after each mistake - if cap colours alternate, then all ten could guess wrong...



suppose it is  5 and 4 . 9th guy will sees 4 white and 4 black .the he can say any colour.so his probability of living is .5 in that case.  
now trick is that if he says wrong colour he will die. other will soon know that he has said wrong colour.also if he 9th says the right colour then colour in front of 8th are in ratio 4;3 and he also knows color of hat of 9th guy through this he can deduce his color of hat
Title: Re: SINGLE-FILE HAT EXECUTION
Post by rmsgrey on Nov 24th, 2011, 8:45am

on 11/23/11 at 15:17:16, rohigoyal86 wrote:
suppose it is  5 and 4 . 9th guy will sees 4 white and 4 black .the he can say any colour.so his probability of living is .5 in that case.  
now trick is that if he says wrong colour he will die. other will soon know that he has said wrong colour.also if he 9th says the right colour then colour in front of 8th are in ratio 4;3 and he also knows color of hat of 9th guy through this he can deduce his color of hat

If #9's hat is black and #8 sees 4 white and 3 black, #8 knows it's 5-4, whichever colour his hat is, but doesn't know whether #9 saw 5 white and 3 black and knew his own hat must be black, or 4 white and 4 black and guessed right. If he always guesses white in that situation, #8 has a 2/3 chance of being right (assuming the hats were assigned independently so each has a 50% chance of being white).

If #9's hat is black and #8 sees 3 white and 4 black (and #10 signalled the larger group to be odd) then #8 knows his hat must be white and is safe.

If #7 then sees three of each, knowing that there's a black and a white behind him, and that nobody has yet guessed wrong, then he has to guess, with a 60% chance of having a black hat.

And so on. I'm not going to bother computing the other variations for #7 or the variations for #6 onward. The point is that (until someone dies), anyone who knows that there are 4 black and 4 white (and #10's hat) aside from their own hat can't be sure whether the 5-4 is 5 blacks or 5 whites - they'd have heard and seen exactly the same things in either case.


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board