[bonanova]

Everyone in the BrainDen universe has heard of the Hats on Death Row problem.

Well, maybe you haven't. Take a quick look [hah!] here, then come back.

Alright then ... here's the deal. The warden was ticked off that the BD geniuses here

foiled his attempt to execute 20 of his worst prisoners, using black and white hats.

So he's upped the ante.

The same rules apply, except now there are hats of three colors: Black, White and Red.

No communication after tonight's strategy meeting, which you lead.

Tomorrow the prisoners are lined up facing along the line and beginning at the back of the line must call out his own color to survive.

How many prisoners can you guarantee will survive?

Remember there are 20 prisoners.

Have fun!

[Guest]

Well so far I can guarantee 10 will survive. The first prisoner (last in line) calls out the colour of the prisoner in front of him. Usin this every 2nd prisoner is guaranteed survival, there is also the possibility that the colour of the hat in front will be the same as that of the person calling so a minimum of ten can survive

[bonanova]

Well so far I can guarantee 10 will survive. The first prisoner (last in line) calls out the colour of the prisoner in front of him. Usin this every 2nd prisoner is guaranteed survival, there is also the possibility that the colour of the hat in front will be the same as that of the person calling so a minimum of ten can survive

This is the solution to beat.

Can anyone do better?

[Guest]

Can it be as simple as...

First man looks in front of him. Sees 19 hats. Two colors have even numbers, one has odd. Pretend he sees 4 black, 6 white, 9 red. He says the color that he sees an odd number of (red). Hopes he's wearing that color. Next man looks in front of him. If he sees an odd number wearing the same color mentioned before (red), he counts the other colors. He says the color that is now odd (and was even before--either white or black). Pretend he was wearing black. He sees 3 black, 6 white, and 9 red, so knows he is wearing black. The next man knows that the first man saw an odd number red, and the second saw an odd number black. He compares what he sees to what he heard and knows what he is wearing.

I don't know if this actually works, but I'm going to bed now. If it works, then 19 men are alive, and 1 has a 1/3 shot.

Edited June 5, 2008 by Dragonjest22

[Guest]

Well let me also try. Bonanova is putting a nice series of hats .

The last men tells Black if he sees odd Red and White if he sees even Red. His survival has prob 1/3

If the next person sees a change in Red his hat is red and he calls red and others update whether remaining red hats are even or odd.

Now the first person who does not see a change in the evenness or oddness of red hats has either black or white hat.

So he will say black if he sees even black hats and white if he sees odd black hats. His survival has prob 1/2.

From now onwards if the prisoners see no change in parity of red and black hats they say white otherwise correspondin hat and all others update.

So 18 are guaranteed to survive.

edit2: no problem I guess

edit: I saw there could be one problem. I will think to correct that

Edited June 5, 2008 by imran

[Guest]

The first one should say red if red are even.

if red are odd then he should say white if white are even and black if white are odd.

Still the guaranteed survivors are 18. but if red are odd then 19 will be saved.

[Guest]

My non-mathematical answer

Assuming the guard starts at the front, the prisoner behind them will stomp 1 for red, 2 for black, and 3 for white. If stomping is too noticeable maybe a whistle or cough. Well, they could do the same thing, but the last person would have a 1/3 chance.

19 would be safe, 1 would have 1/3 chance.

Edit - Darn! They start at the back...

Edited June 5, 2008 by Chippy

[Guest]

Ok I am writing this fast I and I am tired so forgive me if I mess up (or someone already Suggest this)....

Each hat has a different tone ie black=shout, red= wispher, white=normal....

So the #20 person has a 33% chance and every one elese survives....

this is assuming that they can plan this before hand. and Know

[Guest]

I don't think DragonJest's answer is possible, as there can either be 2 even and 1 odd number colour at the start or 3 odd numbered colours, e.g. 1st person sees 3 black, 7 white, 9 red.

Imran's 18 is the best I can do, but slightly differently:

1st person says a colour that he sees an odd number of (there's either only 1, or he can choose from all 3). Let's say he sees an odd number of Black.

From then on, anyone who sees a difference in that colour knows they are that colour, so says it and is saved. Whenever anyone says the colour, everyone else changes the current value for it, e.g. from "black is odd" to "black is even".

The 1st person who doesn't see a difference in that colour then says the other of the two colours that they see that is odd. Let's say he sees an odd number of White.

From then on, anyone seeing a difference in either of those two colours, knows they are the one with the difference and says it. If neither are different they know they are the third colour. As with the first colour, whenever this second colour is spoken everyone else changes the current value for it - e.g. from "white is odd" to "white is even".

The 1st person in the line has a 33% chance of survival, the next one to have to say a different colour has a 50% chance of survival, but everyone else is guaranteed to survive.

This method works for any combination of hats too, so would work if they were all one colour or two colours. Note if there are only 1 or 2 colours used then 19 are guaranteed survival.

And just to beat Bononova to it, it would also work for any number of colours. E.g. if there were 4 colours then recursively using this method would guarantee the survival of 17 of them. If there were n prisoners and c colours, then n-c+1 prisoners are guaranteed survival.

[bonanova]

imran and neida save n-c+1 prisoners! Best so far.

Comment on neida's answer:

I don't think DragonJest's answer is possible, as there can either be 2 even and 1 odd number colour at the start or 3 odd numbered colours, e.g. 1st person sees 3 black, 7 white, 9 red.

Imran's 18 is the best I can do, but slightly differently:

1st person says a colour that he sees an odd number of (there's either only 1, or he can choose from all 3). Let's say he sees an odd number of Black.

From then on, anyone who sees a difference in that colour knows they are that colour, so says it and is saved. Whenever anyone says the colour, everyone else changes the current value for it, e.g. from "black is odd" to "black is even".

The 1st person who doesn't see a difference in that colour then says the other of the two colours that they see that is odd. Let's say he sees an odd number of White. [bona: this is very cool, and it works: the other two colors are either both odd or both even, initially. when a difference in the first color is not seen, it's because another color changes, producing in either case one odd and one even which guarantees there is an odd number of one of the other colors. Very nice. I wonder if the starting number were 21 prisoners, would the algorithm have to be modified here? The other two colors would be odd-even initially, and the change might produce even-even. What should the prisoner say in that case?]

From then on, anyone seeing a difference in either of those two colours, knows they are the one with the difference and says it. If neither are different they know they are the third colour. As with the first colour, whenever this second colour is spoken everyone else changes the current value for it - e.g. from "white is odd" to "white is even".

The 1st person in the line has a 33% chance of survival, the next one to have to say a different colour has a 50% chance of survival, but everyone else is guaranteed to survive.

This method works for any combination of hats too, so would work if they were all one colour or two colours. Note if there are only 1 or 2 colours used then 19 are guaranteed survival.

And just to beat Bononova to it, [bona: yikes!! how did s/he know?] it would also work for any number of colours. E.g. if there were 4 colours then recursively using this method would guarantee the survival of 17 of them. If there were n prisoners and c colours, then n-c+1 prisoners are guaranteed survival.

Anyone else ... can more than n-c+1 prisoners be saved? [n=prisoners, c=colors]

Not that the OP asked this, but ... do imran and neida's solutions work if n is odd?

[Guest]

I don't think DragonJest's answer is possible, as there can either be 2 even and 1 odd number colour at the start or 3 odd numbered colours, e.g. 1st person sees 3 black, 7 white, 9 red.

Oh, right. I didn't think of that. I blame the late-night / early-morning posting. Thanks for catching that.

[Guest]

The scheme goes like this... If the first prisoner sees 3 odd hats, he says black. This way the other prisoners will know exactly the parity of each hat and thus can answer accordingly. If there are 2 even hats and 1 odd, here are the options:

1)if the no of white hats is odd, the prisoner says white. This way, others will know that red and black hats are even and white is odd. Then they can proceed by looking at other prisoners hats and decide.

2)If either the red or black hat is odd, the first prisoner says red. In this case, the next prisoner cannot give an exact answer, so he will look at the colours of hats infront of him. The cases are:

1)If he sees 3 even hats (as only 18 prisoners in front of him), he says white. So the following prisoners can guess correctly.

2)In the case that there are 2 odd hats and 1 even hat, one odd hat has to be white(based on first prisoner's response), so the prisoners own hat is white. Now even though he knows the colour of his hat, he will sacrifice himself by saying the colour of the hat in front of him whose parity is even i.e. either red or black. so other 18 prisoners will be saved.

So overall, if we have 3 odd number of hats or odd white hats, we can save 19 prisoners.

[bonanova]

The scheme goes like this... If the first prisoner sees 3 odd hats, he says black. This way the other prisoners will know exactly the parity of each hat and thus can answer accordingly. If there are 2 even hats and 1 odd, here are the options:

1)if the no of white hats is odd, the prisoner says white. This way, others will know that red and black hats are even and white is odd. Then they can proceed by looking at other prisoners hats and decide.

2)If either the red or black hat is odd, the first prisoner says red. In this case, the next prisoner cannot give an exact answer, so he will look at the colours of hats infront of him. The cases are:

1)If he sees 3 even hats (as only 18 prisoners in front of him), he says white. So the following prisoners can guess correctly.

2)In the case that there are 2 odd hats and 1 even hat, one odd hat has to be white(based on first prisoner's response), so the prisoners own hat is white. Now even though he knows the colour of his hat, he will sacrifice himself by saying the colour of the hat in front of him whose parity is even i.e. either red or black. so other 18 prisoners will be saved.

So overall, if we have 3 odd number of hats or odd white hats, we can save 19 prisoners.

OK. This is the solution to beat. Nice going.

Can we save 19 prisoners with certainty?

[Guest]

Not that the OP asked this, but ... do imran and neida's solutions work if n is odd?

Well spotted bona that I was wrong in saying mine was a generic solution. I realised it after I'd posted but wasn't near a PC any more.

I think there would always need to be slight variations to the rule - e.g. if there were 20 prisoners and 4 colours, it could start with 4 even, 4 odd or 2 of each. Here the first person could say Black for all odd, White for all even or Red if there's a split. I think from then on the generic approach would work, although I haven't thought it through properly.

In terms of saving 19 in the original puzzle, my approach will always save 19 if there are 2 even and 1 odd to start with, without needing any variations or special rules. (You may need to think it through to verify that, but it does work!)

I don't think it's possible to ALWAYS save 19, as there are 4 opening possibilities (all colours are odd, only black is odd, only white is odd, only red is odd) but the 1st person has only 3 things they can possibly say. Because of that, most approaches would only be able to clearly identify 2 of these possibilities from what the first person says, with the other two being indistinguishable (like coolindiano's answer), so only guarantees 19 survive in 2 of the 4 possibilities. My approach guarantees 19 survive in 3 out of the 4 possibilities.

The only way I can think to cover off the 4th possibility is if a prisoner is allowed not to answer. In this case the 1st guy just wouldn't say anything if he sees all odd. Then all other 19 are guaranteed survival no matter what, but if the 1st person sees all odd he MUST sacrifice himself to save the rest, otherwise he has a 33% chance of survival. I'm not sure if this is actually allowed - technically it's not "communicating" so I don't see why not....

[Guest]

My comment added)..']The scheme goes like this... If the first prisoner sees 3 odd hats, he says black. This way the other prisoners will know exactly the parity of each hat and thus can answer accordingly. If there are 2 even hats and 1 odd, here are the options:

1)if the no of white hats is odd, the prisoner says white. This way, others will know that red and black hats are even and white is odd. Then they can proceed by looking at other prisoners hats and decide.

2)If either the red or black hat is odd, the first prisoner says red. In this case, the next prisoner cannot give an exact answer, so he will look at the colours of hats infront of him. The cases are:

1)If he sees 3 even hats (as only 18 prisoners in front of him), he says white. So the following prisoners can guess correctly.

2)In the case that there are 2 odd hats and 1 even hat, one odd hat has to be white(Dont think so as this is the case when initially either red or black was odd and white even)(based on first prisoner's response), so the prisoners own hat is white. Now even though he knows the colour of his hat, he will sacrifice himself by saying the colour of the hat in front of him whose parity is even i.e. either red or black. so other 18 prisoners will be saved.

So overall, if we have 3 odd number of hats or odd white hats, we can save 19 prisoners.

I guess there is some flaw in this logic. Also it works only if we have even number of total prisoners.

[Guest]

I guess there is some flaw in this logic. Also it works only if we have even number of total prisoners.

If the first prisoner says red, that means either red is odd or black is odd..So the second prisoner will know that is the case.

If there are odd number of hats, the first prisoner can see even no of hats, which means either all even, or two odd 1 even. You can still use the same method, just change the parity.

[Guest]

This is a proper head-scratcher but I think I'm there now!

It's quite hard to make this simple to use, but here's my best attempt.

Prisoners use a code to convert colours to numbers. When looking at other hats and listening to other prisoners they use:

BLACK=0

WHITE=1

RED=2

but when they call out a number they use

BLACK=0

RED=1

WHITE=2

Each prisoner sums up the points in front (using 1st code) and then first calls out this number, modulo 3 (using 2nd code).

The second interprets that number using the 1st code and adds it to his own number. Then he calls out the total modulo 3 (using 2nd code).

Each prisoner keeps a running total and adds it to their own number, calling out the total, mod 3.

Example:

1st: WHITE (sees 13 points in front)

2nd: RED (sees 11 points in front)

3rd: WHITE (sees 10 points in front)

4th: BLACK (sees 10 points in front)

5th: WHITE (sees 9 points in front)

1st prisoner: 13 mod 3 = 1, calls out "RED" for 1 point. Curtains for him.

Prisoners listening interpret "RED" as 2 points

2nd: 11+2 points mod 3 makes 1. Calls out "RED".

Running total = 4

3rd: 10+4 points mod 3 makes 2. Calls out "WHITE".

Running total = 5

4th: 10+5 points mod 3 makes 0. Calls out "BLACK".

Running total = 5

5th: 9+5 points mod 3 makes 2. Calls out "WHITE".

and so on...

Edited June 6, 2008 by octopuppy

[bonanova]

This is a proper head-scratcher but I think I'm there now!

It's quite hard to make this simple to use, but here's my best attempt.

Prisoners use a code to convert colours to numbers. When looking at other hats and listening to other prisoners they use:

BLACK=0

WHITE=1

RED=2

but when they call out a number they use

BLACK=0

RED=1

WHITE=2

Each prisoner sums up the points in front (using 1st code) and then first calls out this number, modulo 3 (using 2nd code).

The second interprets that number using the 1st code and adds it to his own number. Then he calls out the total modulo 3 (using 2nd code).

Each prisoner keeps a running total and adds it to their own number, calling out the total, mod 3.

Example:

1st: WHITE (sees 13 points in front)

2nd: RED (sees 11 points in front)

3rd: WHITE (sees 10 points in front)

4th: BLACK (sees 10 points in front)

5th: WHITE (sees 9 points in front)

1st prisoner: 13 mod 3 = 1, calls out "RED" for 1 point. Curtains for him.

Prisoners listening interpret "RED" as 2 points

2nd: 11+2 points mod 3 makes 1. Calls out "RED".

Running total = 4

3rd: 10+4 points mod 3 makes 2. Calls out "WHITE".

Running total = 5

4th: 10+5 points mod 3 makes 0. Calls out "BLACK".

Running total = 5

5th: 9+5 points mod 3 makes 2. Calls out "WHITE".

and so on...

Octopuppy has it.

His method works for even or odd prisoners and can be extended for hats of k different colors, as well.

So much for the sadistic Warden Smith.

[Guest]

imran and neida save n-c+1 prisoners! Best so far.

Comment on neida's answer:

Anyone else ... can more than n-c+1 prisoners be saved? [n=prisoners, c=colors]

Not that the OP asked this, but ... do imran and neida's solutions work if n is odd?

Yes, my method as stated above saves all but the last guy who has a 50/50 chance

[unreality]

this is now the hardest riddle in existence ;D it trumps the original Hats on Death Row

congrats for excavating pure gold, bonanova and congrats to octopuppy for magically solving it, lol

[Guest]

Do you really need 2 different codes?

What if you take the first Code only ie;

Black = 0, Red = 1 and White = 2.

First person adds up all the numbers infront and calls out as follows;

If the number he sees is divisible by 3 he says black (eg ,3,6,9 etc)

If divisible by 3 +1 extra he answers red (eg 4,7,10 etc)

If divisible by three + 2 extra he answers white (eg 5,8,11 etc)

The second person then adds up what he sees and does the same calculation.

Then he uses the following sequence as his reference;

Black - red - white - black - red

He then looks at what his predecessor said and what he can see and counts how many colours he has to move back along the sequence

If the colours are the same he says Black

If the colour he sees is one colour before on the seqeunce compared to his predecessor, he says red

If the colour he sees is two before the one his predecessor on the sequence he says white.

Same thing applies for everyone else except the front person who just converts his predessors answer directly using the original code of Black0, red1, white2

It could be that this is exactly the same solution only explained differently - If so please accept my apologies

Edited September 15, 2008 by Steve17

[bonanova]

Do you really need 2 different codes?

What if you take the first Code only ie;

Black = 0, Red = 1 and White = 2.

First person adds up all the numbers infront and calls out as follows;

If the number he sees is divisible by 3 he says black (eg ,3,6,9 etc)

If divisible by 3 +1 extra he answers red (eg 4,7,10 etc)

If divisible by three + 2 extra he answers white (eg 5,8,11 etc)

The second person then adds up what he sees and does the same calculation.

Then he uses the following sequence as his reference;

Black - red - white - black - red

He then looks at what his predecessor said and what he can see and counts how many colours he has to move back along the sequence

If the colours are the same he says Black

If the colour he sees is one colour before on the seqeunce compared to his predecessor, he says red

If the colour he sees is two before the one his predecessor on the sequence he says white.

Same thing applies for everyone else except the front person who just converts his predessors answer directly using the original code of Black0, red1, white2

It could be that this is exactly the same solution only explained differently - If so please accept my apologies

It runs along the same line as octopuppy's solution, maybe easier to understand.

Nice going.