My Favorite Riddle

[jonottawa]

Okay, this isn't as elegant as I would have liked, but I think it's a solution for specifically 10 dwarves. I took a completely different tack this time:

 

 

There are 12 possible distributions of the hats as seen by the guinea pig dwarf:

 

a 9-0-0

b 8-1-0

c 7-1-1

d 7-2-0

e 6-2-1

f 6-3-0

g 5-4-0

h 5-3-1

i 5-2-2

j 4-4-1

k 4-3-2

l 3-3-3

 

He's gonna say Blue if it's distribution

 

c 7-1-1

f 6-3-0

k 4-3-2

 

He's gonna say Red if it's distribution

 

a 9-0-0

d 7-2-0

h 5-3-1

 

He's gonna say Green if it's distribution

 

b 8-1-0

e 6-2-1

g 5-4-0

i 5-2-2

j 4-4-1

l 3-3-3

 

Once he's narrowed down the distribution set like this, there's no more ambiguity and the dwarves will each know exactly what hat they are wearing.

 

Edit: Sigh. g and j conflict. Back to the old drawing board.

 

[jonottawa]

Okay, my last kick at the cat:

 

 

There are 12 possible distributions of the hats as seen by the guinea pig dwarf:

 

a 9-0-0

b 8-1-0

c 7-1-1

d 7-2-0

e 6-2-1

f 6-3-0

g 5-4-0

h 5-3-1

i 5-2-2

j 4-4-1

k 4-3-2

l 3-3-3

 

He's gonna say Blue if it's distribution

 

a 9-0-0

d 7-2-0

g 5-3-1

 

He's gonna say Red if it's distribution

 

c 7-1-1

f 6-3-0

i 5-2-2

j 4-4-1

l 3-3-3

 

He's gonna say Green if it's distribution

 

b 8-1-0

e 6-2-1

h 5-4-0

k 4-3-2

 

Once he's narrowed down the distribution set like this, there's no more ambiguity and the dwarves will each know exactly what hat they are wearing.

 

Edit: I hate this problem. This solution is wrong too (it tells you the distribution, but not the specific shortness/fragment.) I give up. :)

 

[helene_t]

Suppose there are three colors. We call them color zero, color one and color two, Now the lastmost dwarf encodes the 3-parity of the sum of the colors: say there are 6 dwarfs and the five he can see are colors 1-0-1-2-1, then the sum is 5.

- If the sum of the colors is dividable by 3 (0, 3, 6, 9....) he says "color zero"

- If the sum of the colors is one above dividable by 3 (1, 4, 7, 10....) he says "color one"

- If the sum of the colors is two above dividable by 3 (2, 5, 7, 10....) he says "color two"

 

Now the second-backmost dwarf can compute the parity of the caps he can see. If it is the same parity as was indicated by the color he just heared from the backmost dwarf, he knows his own cap is color zero etc.

 

This is easily generalized to more than three colors.

[jonottawa]

How did I know it would be a simple and elegant solution that I never would have thought of in a million years? :)

[jtfanclub]

Suppose there are three colors. We call them color zero, color one and color two,

I knew somebody would post it...I finally figured it out in the freakin' car on the way home. It had not occurred to me until that moment that I could encrypt it 2-1-0 mod 3. I should have recognized it, because that's how the new RAID systems work.

 

This is completely applicable to bridge...instead of using binary signals to determine if a suit is odd or even, I can use a fourpart signal to encode all four suit lengths. No wonder they don't allow them to be used!

[helene_t]

I think they do (at least here in NL it wont be a problem), the problem is that you don't always have a card of the parity you want to signal. Odd/even can be a pain already.

[Codo]

Suppose there are three colors. We call them color zero, color one and color two, Now the lastmost dwarf encodes the 3-parity of the sum of the colors: say there are 6 dwarfs and the five he can see are colors 1-0-1-2-1, then the sum is 5.

- If the sum of the colors is dividable by 3 (0, 3, 6, 9....) he says "color zero"

- If the sum of the colors is one above dividable by 3 (1, 4, 7, 10....) he says "color one"

- If the sum of the colors is two above dividable by 3 (2, 5, 7, 10....) he says "color two"

 

Now the second-backmost dwarf can compute the parity of the caps he can see. If it is the same parity as was indicated by the color he just heared from the backmost dwarf, he knows his own cap is color zero etc.

 

This is easily generalized to more than three colors.

A wonderful problem and solution.

[kfay]

Suppose there are three colors. We call them color zero, color one and color two, Now the lastmost dwarf encodes the 3-parity of the sum of the colors: say there are 6 dwarfs and the five he can see are colors 1-0-1-2-1, then the sum is 5.

- If the sum of the colors is dividable by 3 (0, 3, 6, 9....) he says "color zero"

- If the sum of the colors is one above dividable by 3 (1, 4, 7, 10....) he says "color one"

- If the sum of the colors is two above dividable by 3 (2, 5, 7, 10....) he says "color two"

 

Now the second-backmost dwarf can compute the parity of the caps he can see. If it is the same parity as was indicated by the color he just heared from the backmost dwarf, he knows his own cap is color zero etc.

 

This is easily generalized to more than three colors.

This is actually the way that I solved the original problem when I first heard it. Although on later contemplation I realized it's basically the same as saying which color has an even or odd population amongst the dwarves. I never considered more than 2 colors so that is pretty neat.

[Mbodell]

I guess having a computer science education makes one think this way automatically as it seems the "obvious" solution to me. I was surprised to see so many incorrect attempts after my "use mod K adding" hint which seems not to have been read/understood until helene explained that with a full example in the K=3 case.

[nige1]

If they guess incorrectly, they die (by beheading... an axe).

Even the 2 color solution is more tricky than people realize. Tell ten people the solution....line them up to be killed, I bet more than one dies......the Math/adding or subtraction......etc..... is just too hard.

Accentuate the positive!

Eliminate the negative!

IMO, in the 2-color case, provided that at least one of the dwarves behind you is an accurate arithmetician, then you can save yourself, even if the others behind you make random mistakes :( ignoring the fate of the backmost dwarf, each subsequent swish of the axe flips the parity :)

[slothy]

And there was me thinking that death by execution, never mind discrimination of vertically-challenged people, was outlawed in many of the United States....

 

a more interesting variation of this puzzle is where the 10 people are siamese twins and colour-blind, with each one of the twins suffering from chronic dandruff, their height being irrelevant

[Fluffy]

Alex this has nothing to do with United States, otherwise all dorfs would be killed for wearing caps.

[kenberg]

I came late to this but let me suggest a modest variation where it's important that the number of dwarfs be even.

 

First I want to change the rules in another way: If all dwarfs except the rear dwarf get the right answer then all dwarfs will be spared. This seems more in the spirit of the season and also gives the rear dwarf proper motivation.

 

 

Now suppose the game is as follows: The Executioner announces that each hat will be of one of two colors but he doesn't say what the colors are. Now if we say that there are only finitely many different colors, 500 perhaps, the dwarfs could make a list of the colors and treat it as a 500 color problem (solved). So let's say the Ex will place one of two objects on their heads but doesn't say what the objects are.

 

 

The game begins:

 

Dwarf 10 (in the rear) looks at the nine dwarfs in front of him and sees an odd number of heads with, say, apples on them. He says Apple.

 

Dwarf 9 either sees an even number of apples, and so says Apple, or he sees an odd number of apples and then knows that the object on top of his head is not an apple. But Dwarf 9 is looking at 8 heads and so, when he sees an odd number of apples he also sees an odd number, in particular not zero, of the other object (a banana, say) and so he can say Banana.

 

 

 

For Dwarf 8, the same solution works because he really "sees" 8 heads. He sees the 7 heads in front of him and he trusts that dwarf 9 in back of him has correctly identified the object on top of his head. And so on down the line.

 

This doesn't work with 11 dwarfs since dwarf 11 will either see two odds or two evens when he counts objects.

 

 

 

This thinking leads to still another possible game with 10 (or any even number) of dwarfs:

The Ex says that he will place one of two identifiable objects on each head and he does not give the dwarfs time to discuss their strategy. Credit the dwarfs with the following reasoning: Each dwarf imagines a strategy that he would suggest if they had time to discuss it. In fact, when the dwarfs do not know what the objects will be then, I am pretty sure, the "announce the object you see an odd number of" is the only strategy that will work and so is the strategy they would come to IF they had the opportunity to discuss. So each dwarf trusts the other dwarfs to follow this uniquely defined strategy.

 

 

Interestingly (if any of this is interesting) if the dwarfs are told the two colors but not given time to discuss, then uniqueness of discussed strategy fails and the dwarfs will not be able to be sure each of the other dwarfs, undiscussed, has chosen the same strategy.

[han]

There is never uniqueness, even in the original problem. In fact, there are many different correct solutions (can you count them?).

[kenberg]

There is not uniqueness in the original problem, for example dwarf 10 could either announce whichever color that appears an odd number of times or the color that appears an even number of times. Since both colors are known, announcing one leads to knowledge of both.

 

With the rules I suggest, where two unknown objects are to be placed on heads, I believe that uniqueness of the discussed strategy holds. In the original game if dwarf 10 informs his friends that an even number of dwarfs have red hats then they know that an odd number have a black hat. In the modified game they would know only that an odd number of dwarfs all have the same object on their heads and that object is not a red hat.

 

With 10 dwarfs, here is the argument.

 

 

Dwarf 10 looks to see how many of each object are there. For starters, say he sees one apple and 8 bananas. If their agreement is that he will say banana, the dwarf with the apple on his head is in trouble no matter where he is in the line. Say dwarf 3 has an apple on his head, the rest have bananas. Suppose that as a result of dwarf 10 saying banana, dwarfs 9 through 4 have correctly said banana. Even if dwarf 3 somehow knows that he dopes not have a banana on his head, how is he to know he has an apple rather than a cupcake, a green hat, or a roll of toilet paper?

 

Thus, when dwarf 10 sees 8 bananas and 1 apple, he must say Apple if the dwarf with an apple atop his head is going to get the right answer.

 

Similarly (well, inductively) with how ever many objects of each type there are. For example, suppose dwarf 10 sees 2 apples and 6 bananas. Maybe dwarfs 2 and 6 have bananas. Suppose dwarfs 9,8,7 get it right, and dwarf 6 is up. He knows that if he has a banana on his head then dwarf 10 would have said Apple (the argument above shows that he must, because he would be looking at only 1 apple). But if dwarf 10 would also say apple sometimes when he sees two apples, the dwarf 6 has a guess to make. The strategy must be that when dwarf 10 sees exactly two apples then he says Banana. And so on.

 

Changing the problem from two known colors to two objects that are not known in advance is what produces the uniqueness. Knowing the two colors, or the two objects, destroys uniqueness, Not knowing what the two objects will be produces a solvable game with a unique strategy.

 

 

This change also requires an even number of dwarfs. Try it with three dwarfs: Dwarf 3 sees an pineapple on dwarf 1 and a peach on dwarf 2. If dwarf 3 says Pineapple then even if, through their agreement, this information suffices to tell dwarf 2 that he does not have a pineapple on his head it will not help him in deciding that he has a peach on his head. Similar problems for dwarf 1 if dwarf 3 says Peach.

 

With an even number of dwarfs and the Odd strategy, these problems don't appear. Dwarf 9 knows that one of the objects must appear an odd number of times. If he sees an even number of them he knows the remaining one is on his head. If he sees an odd number then, since he is looking at 8 dwarfs, he must be looking at an odd number of the other object as well and can not only tell he has the "other object" (other than what dwarf 10 called) he can also know what that object is by looking at it.

 

Anyway, I seriously doubt that you can supply either an alternative strategy for ten dwarfs or any strategy for 3 dwarfs (or 11) under these modified rules: Two previously unknown objects, one or the other on each of the heads (possibly 0 of one type, all of the other type). I've been wrong before, but this seems right.

[kenberg]

When there are k colors in use and the colors are known, it's clear that there are at least k factorial ways for the dwarfs to code the information (take and successful coding and any permutation of the colors, the composition will give another successful coding assuming the remaining dwarfs know what the permutation is so they can undo it). When k=2 this gives 2 ways of coding and that is (or so I think) correct. I am finding the proof that k factorial is the right general answer to be elusive enough so that I am not confident that it is correct. I'll give it some more thought. It's a nice counting problem.

 

As probably is clear, by successful coding I mean a way for the rear dwarf to announce a color, based n which other dwarfs have which color hats, that will provide the other dwarfs who know the code to identify their own color hat.

 

The basic example is to identify the colors with the numbers 0 through k-1. The rear dwarf adds the numbers, divides by k, converts the remainder back to a color, and announces the color. Each dwarf in turn convert the colors to a number, calculates the sum of the numbers (from colors) that he either he sees on dwarfs in front of him or hears from the other non-rear dwarfs, calculates what number must be added to this sum so the remainder upon division by k will be correct, converts back to a color, announces that color.

 

In this telling the k factorial arises directly from the fact that there are k factorial ways to assign the numbers 0 through k-1 to the k different colors.

 

 

I have a nagging feeling I have missed some ways.

 

 

I have to clear my mind of this since we are about to have company and they would, I am pretty sure, not care.