[kfay]

10 dwarves are sentenced to death. On the day they are fated to die they climb the scaffolding to the executioner who looks them up and down and says to them from under his black hood, "Look, guys, I've never had to do this sort of thing to dwarves before and frankly you look like a good group of guys so I'm going to cut you a deal..."

The executioner then outlines his plan whereby he will line the dwarves up in a straight line, each facing the same direction, so that each dwarf can see all the dwarves in front of him (if he pokes his head out) but cannot see anyone behind him, nor is he allowed to turn around. The executioner then puts either a red or a black cap on each dwarf entirely at random (there does not need to be an equal number of black or red caps) and proceeds from the back of the line to the front of the line and asks each dwarf in turn what color their cap is. If they guess correctly, they live. If they guess incorrectly, they die (by beheading... an axe).

The dwarves get together and figure out a way so that - given this information - 9/10 of the dwarves are guaranteed to survive this ordeal.

When the executioner asks the first dwarf the color of his cap, what must he say? The inflection of his voice plays no part in the solution and he is only allowed to say either "red" or "black". Each dwarf can hear what all the other dwarves behind them say.

[jtfanclub]

Not quite as easy as it looks...

Spoiler

The dwarf in the back can see 9 hats. He says "Red" if there are an odd number of red hats he sees, and "Black" if there are an odd number of black hats.

Let's say that the dwarf in the back says "Black". The next dward can see four red and four black hats. He knows that there's an odd number of black hats, so he must have a black hat. He says "Black". He lives.

Now, the next dwarf can see four black and three red hats. He knows that there are an even number of black hats (started with an odd number for the nine of them, minus one for guy #9), and he can see an even number of black hats, so it must be a red hat. He says "Red". He lives.

Und so weiter.

[Trumpace]

Yes, this is a very nice puzzle. In fact it can even be generalized to k colours.

[Echognome]

Have also seen this problem and the generalization.

I'm offended you chose to execute dwarves in your story. They are distant cousins of gnomes, however they always seem to be getting into trouble.

[bid_em_up]

With my luck, Dopey is the one standing at the back of the line.....

[helene_t]

I must have missed something, but it seems to me that the executioner should ask the dwarfs in random order, and that each dwarf should be allowed to see the color of all other caps. As it is stated, the backmost dwarf could simply name the color of the cap of the 2nd backmost dwarf, couldn't he?

[bid_em_up]

helene_t, on Nov 7 2007, 03:18 PM, said:

I must have missed something, but it seems to me that the executioner should ask the dwarfs in random order, and that each dwarf should be allowed to see the color of all other caps. As it is stated, the backmost dwarf could simply name the color of the cap of the 2nd backmost dwarf, couldn't he?

No, because the next to the last dwarf has to say "red or black".

The last dwarf says, "Black" for the guy in front of him. He lives or dies depending on how lucky he is.

Now the next to the last dwarf knows what color he has, so he will live by saying the same thing the last dwarf did. But he can't also tell the one in front of him what color he has.

Now the third from the last dwarf is back to naming the color of the guy in front of him.

The most you could save with certainty under this scenario is 5.

10 lives or dies (names color of guy in front of him, hopes he has same color),
9 lives (names his color),
8 lives or dies (names color of guy in front of him, hopes he has same color),
7 lives (names his color),
6 lives or dies (names color of guy in front of him, hopes he has same color)

and so on.

[jonottawa]

Perhaps this is kfay's revenge for the F's puzzle.

I agree with bid's analysis. I don't see how it's remotely conceivable to save more than 5 with certainty. You can either save yourself (which conveys no helpful information to your buddies) or you can tell the guy in front of you how to save himself (which means you have only a 50-50 shot of surviving yourself.) There's surely no way to guarantee that the front 9 dwarves all live.

I'm 99.999% sure that either the problem was posed incorrectly or that there's some cheesy 'solution' that violates the parameters of the problem (since it's not explicitly stated that a dwarf can't take off his own cap and look at it.)

[Echognome]

jonottawa, on Nov 7 2007, 12:47 PM, said:

Perhaps this is kfay's revenge for the F's puzzle.

I agree with bid's analysis. I don't see how it's remotely conceivable to save more than 5 with certainty. You can either save yourself (which conveys no helpful information to your buddies) or you can tell the guy in front of you how to save himself (which means you have only a 50-50 shot of surviving yourself.) There's surely no way to guarantee that the front 9 dwarves all live.

I'm 99.999% sure that either the problem was posed incorrectly or that there's some cheesy 'solution' that violates the parameters of the problem (since it's not explicitly stated that a dwarf can't take off his own cap and look at it.)

That's not true. You can save all of the dwarves bar the first one. Furthermore, you could do so even if there were more colors. Keep thinking about it. As a start, imagine there were 3 dwarves. Could you save 2 for sure?

[Trumpace]

jonottawa, on Nov 7 2007, 03:47 PM, said:

Perhaps this is kfay's revenge for the F's puzzle.

I agree with bid's analysis.  I don't see how it's remotely conceivable to save more than 5 with certainty. 
<snip>

I'm 99.999% sure that either the problem was posed incorrectly or that there's some cheesy 'solution' that violates the parameters of the problem (since it's not explicitly stated that a dwarf can't take off his own cap and look at it.)

What bid_em_up posted was not his analysis of the problem. I think he was responding to helene's post. I don't think bid_em_up ever claimed that 5 is max. I might be mistaken though, but it does look like he is talking about helene's solution.

Let me assure you, there is no "cheesy" solution to this. It is a very legitimate answer and is very clever. All but one can survive, even with more than 2 colours.

[edit] Gnome beat me to it [/edit]

[jonottawa]

Echognome, on Nov 7 2007, 08:52 PM, said:

jonottawa, on Nov 7 2007, 12:47 PM, said:

Perhaps this is kfay's revenge for the F's puzzle.

I agree with bid's analysis.  I don't see how it's remotely conceivable to save more than 5 with certainty.  You can either save yourself (which conveys no helpful information to your buddies) or you can tell the guy in front of you how to save himself (which means you have only a 50-50 shot of surviving yourself.)  There's surely no way to guarantee that the front 9 dwarves all live.

I'm 99.999% sure that either the problem was posed incorrectly or that there's some cheesy 'solution' that violates the parameters of the problem (since it's not explicitly stated that a dwarf can't take off his own cap and look at it.)

That's not true. You can save all of the dwarves bar the first one. Furthermore, you could do so even if there were more colors. Keep thinking about it. As a start, imagine there were 3 dwarves. Could you save 2 for sure?

No, you couldn't save 2 for sure.

I'm the guy at the back of the line. Nobody can see my cap. So you definitely can't save me for sure.

The guy in front of me has a black cap. If I don't tell him that he has a black cap you definitely can't save him for sure.

So I say 'black'.

I have a red cap and die. (Or if our code was to say the opposite of what he has on, I say 'red' and have a black cap and die.)

He says 'black' and lives.

Now the guy in front of him is on a pure guess and can't be saved for sure.

I really hope I'm wrong here. I love being outsmarted (or outclevered, perhaps.) But assuming there's not some cheesy 'cheat' (like looking at your own cap or the executioner cutting off his own head if you say black or some such nonsense) then it can't be done.

[Echognome]

Let me help you with a hint and see if you can take it from there.

Let's start with 3 dwarves and 2 colors.

Our dwarf at the end of the line is Mr. Altruistic. He is only going to call out a color in an attempt to save the lives of the other two dwarves. If the dwarves in front of him have on the same color hat, he says "Black". If they have on different colored hats, he says "Red".

Take it from there...

[gwnn]

this is so cool, it reminds me of bidding system thingies (unfortunately i know the result )

it can be generalized to k colors and n-1 saved from n

[bid_em_up]

jonottawa, on Nov 7 2007, 03:47 PM, said:

Perhaps this is kfay's revenge for the F's puzzle.

I agree with bid's analysis.  I don't see how it's remotely conceivable to save more than 5 with certainty.  You can either save yourself (which conveys no helpful information to your buddies) or you can tell the guy in front of you how to save himself (which means you have only a 50-50 shot of surviving yourself.)  There's surely no way to guarantee that the front 9 dwarves all live.

I'm 99.999% sure that either the problem was posed incorrectly or that there's some cheesy 'solution' that violates the parameters of the problem (since it's not explicitly stated that a dwarf can't take off his own cap and look at it.)

It wasnt so much an analysis as an explanation of why each dwarf couldnt just say what the one in front of him has on, as Helene appeared to be suggesting.

See the hidden text in jtfanclubs post for the solution to saving 9/10.

(And be prepared to be "outsmarted" when you do.)

Actually, I'm not sure his solution works either. What if there is an uneven number of black hats vs. red hats? ie. 7 blacks vs. 3 reds originally. Does it still work?

[jonottawa]

Echognome, on Nov 7 2007, 09:04 PM, said:

Let me help you with a hint and see if you can take it from there.

Let's start with 3 dwarves and 2 colors.

Our dwarf at the end of the line is Mr. Altruistic.  He is only going to call out a color in an attempt to save the lives of the other two dwarves.  If the dwarves in front of him have on the same color hat, he says "Black".  If they have on different colored hats, he says "Red". 

Take it from there...

Wow. Neat. Outclevered indeed. That gets you up to 1 dwarf saving 2. I'm still too dense to see how that gets you all the way down the line (1 dwarf saving 9.)

First guy says black (next 2 have same color) he has a red cap and dies.

Second guy sees that guy in front of him is red. He knows it's the same color as his cap. He says red. He has a red cap and lives.

Third guy knows that his cap is red because the first guy said he had on the same cap as the 2nd guy. He says red. He has a red cap and lives.

I'm the 4th guy. What color's my cap? What do I say?

With that last bit of foot-inserting into mouth, I am off to google the solution. Thanks for the puzzle.

[jonottawa]

bid_em_up, on Nov 7 2007, 09:56 PM, said:

jonottawa, on Nov 7 2007, 03:47 PM, said:

Perhaps this is kfay's revenge for the F's puzzle.

I agree with bid's analysis.  I don't see how it's remotely conceivable to save more than 5 with certainty.  You can either save yourself (which conveys no helpful information to your buddies) or you can tell the guy in front of you how to save himself (which means you have only a 50-50 shot of surviving yourself.)  There's surely no way to guarantee that the front 9 dwarves all live.

I'm 99.999% sure that either the problem was posed incorrectly or that there's some cheesy 'solution' that violates the parameters of the problem (since it's not explicitly stated that a dwarf can't take off his own cap and look at it.)

It wasnt so much an analysis as an explanation of why each dwarf couldnt just say what the one in front of him has on, as Helene appeared to be suggesting.

See the hidden text in jtfanclubs post for the solution to saving 9/10.

(And be prepared to be "outsmarted" when you do.)

Actually, I'm not sure his solution works either. What if there is an uneven number of black hats vs. red hats? ie. 7 blacks vs. 3 reds originally. Does it still work?

That is TOO cool. Great puzzle.

[Mbodell]

jonottawa, on Nov 7 2007, 03:47 PM, said:

Perhaps this is kfay's revenge for the F's puzzle.

I agree with bid's analysis. I don't see how it's remotely conceivable to save more than 5 with certainty. You can either save yourself (which conveys no helpful information to your buddies) or you can tell the guy in front of you how to save himself (which means you have only a 50-50 shot of surviving yourself.) There's surely no way to guarantee that the front 9 dwarves all live.

I'm 99.999% sure that either the problem was posed incorrectly or that there's some cheesy 'solution' that violates the parameters of the problem (since it's not explicitly stated that a dwarf can't take off his own cap and look at it.)

When all the hats are just red or black it is easy if you have any experience with error correction codes or thinking in binary.

You can generalize to K colors as long as all the dwarfs know the value of K and are decent/good at math (to generalize to the K value one

Spoiler

use mod K adding

).

[Echognome]

bid_em_up, on Nov 7 2007, 01:56 PM, said:

Actually, I'm not sure his solution works either. What if there is an uneven number of black hats vs. red hats? ie. 7 blacks vs. 3 reds originally. Does it still work?

It works for any number of hats, the solution was just stated slightly incorrectly.

Anyone want to try to figure out the strategy for three colors? As a hint, the last guy in line can shout out any of three colors instead of two.

I'll leave it as hidden for those that want to work out the two color example on their own:

Spoiler

The last guy can see all the hats less his own. From all the hats he can see, he will yell out "Black" if there are an even number of black hats and "Red" if there are an odd number of black hats. Then you can deduce whether there are an odd or even number of red hats. So with 9 hats visible, if there are an even number of black hats, there must be an odd number of red hats and vice versa. If there were 11 dwarves, then they must both be odd or both be even.

[jtfanclub]

bid_em_up, on Nov 7 2007, 04:56 PM, said:

See the hidden text in jtfanclubs post for the solution to saving 9/10.

Actually, I'm not sure his solution works either. What if there is an uneven number of black hats vs. red hats? ie. 7 blacks vs. 3 reds originally. Does it still work?

It's just odd-even. Black if the number of black caps is odd, Red if the number of black caps is even.

Much tougher with 3 colors. Offhand, I don't see how to do that. Hmmmm...

Suppose you have 9 caps. Either all 3 will be odd, or two will be odd and one will be even. That's four odd/even states. How to get it down to 3....hmmm...

If all three are odd, then it's easy. If two are even and one is odd, then after one is removed you'll either have 3 even or two odd and one even. But if all 3 are even, it's guaranteed that it wasn't all three even to start with.

Hmmm...

So, if the last dwarf could announce "All the remaining are odd", that would solve it for the others.

If the last dwarf could announce "All the remaining are odd if we added these two colors" and named the colors, that would do it.

What if we double encoded it from the back...arrgh, too complex. Anybody else solve it for three colors without killing two dwarves?

[jonottawa]

I'll try to redeem myself and take a stab at the 3-colors problem.

Spoiler

If you have 3 colors, Red Blue Green, you can have (in order, RBG)

Odd odd odd
Even even odd
Even odd even
Odd even even

I think if you say anything for the first state, 'green' for the second state, 'blue' for the third state, and 'red' for the fourth state that the rest of the dwarves should be able to muddle through because they know that the other two colors are either both even or both odd and should be able to deduce the hat on their head accordingly.

If there were instead 11 dwarves, then the 11th dwarf would see 10 hats which must be:

Even even even
Odd odd even
Odd even odd
Even odd odd

And again, you'd always call out whichever color's frequency is 'not like the others'.