# 10 little dwarves

A dwarf-killing giant lines up 10 dwarfs from shortest to tallest.

Each dwarf can see all the shortest dwarfs in front of him, but cannot see the dwarfs behind himself.

The giant randomly puts a white or black hat on each dwarf. No dwarf can see their own hat. The giant tells all the dwarfs that he will ask each dwarf, starting with the tallest, for the color of his hat.

If the dwarf answers incorrectly, the giant will kill the dwarf.

Each dwarf can hear the previous answers, but cannot hear when a dwarf is killed.

The dwarves are given an opportunity to collude before the hats are distributed.

What strategy should be used to kill the fewest dwarfs, and what is the minimum number of dwarfs that can be saved with this strategy?

My approach: 1st guy counts which color is max, says it, all others copy his ans. This way, we save at least 5, but I think we can optimize this, just can't figure out how....

## 6 Answers

Parity: Dwarves agree that black = 1 and white = 0. First dwarf adds up all the hats he sees mod 2 and calls that out. The rest of the dwarves need to rememeber this. Each dwarf adds up the hats he sees mod 2 and if it's the same, considers his hat white, if it's not the same parity, then he considers his hat black.

After that each dwarf in turn calls out his presumption of hat color, except that the listening dwarves must change their guess each time someone before them calls "black" (after the first dwarf). That way they only have to add up the hats once, and do not need to remember each call, only to change their color when "black" is called.

All dwarves but the first are guarenteed to survive.

• Only the first guy is a 50/50 shot. – amcalde Aug 21 '14 at 17:01
• This solution generalizes to any number of colors for hats. If there are $k$ colors, the first dwarf has a $1/k$ chance of being saved and all other dwarves are guaranteed to be saved. – user2566092 Aug 21 '14 at 17:08
• Right, you just have to agree beforehand on some mapping to the integers mod k. – amcalde Aug 21 '14 at 17:13
• This of course assumes the unsub giant has a psychological compulsion to stick with his own rules, and doesn't just plan to kill the dwarfs after playing with them. However, this is an excellent delaying tactic, giving the CSI hobbits some extra time to track them down and save the day at the last minute. – Graham Kemp Aug 21 '14 at 23:34
• And, amazingly, if there is an infinite row of dwarves, you can save all but finitely many of them, provided you believe in the Axiom of Choice. – Théophile Aug 26 '14 at 16:27

This video from Khan academy might be of use:

https://www.youtube.com/watch?v=K4pocYXOmTQ

Solution 1: If the last shout the first color and the second last the second color, at least for sure first five in row will survive. Solution 2: Since there is no obligation on the way they answer, they can agree on this; If I say the color only, "black" or "white" it means the one in front of me is white If I say the color in a sentence, "It's black" or "It should be white", then it means the one in front of me is black.

By following these rules 9 will survive and there is 50% chance for 1.

Example: The last says "black" means the next is white. so the next will say "white" if in front is white and he says "it's white" if the next is black.

My Answer is : Minimum 9 dwarves can be saved .

Assumption :The question is asked in the decreasing order of height strating from the tallest.

The giant starts asking the longest dwarf the colour of his hat . The probability of the answer being correct is 50% . So he can say white or black ; but since they all have formulated a strategy : the longest dwarf will see the colour of the dwarf next to him and speak his colour.

Hence the next dwarf knows his colour with 100 % surity and will speak it out next ; all 9 remaining dwarves give the correct answer.

• But if the second dwarf call out his own color he cannot tell the third one what his color is... This way you can only save half of the dwarfs. – SPK.z Oct 29 '14 at 11:05

The dwarves all look up what happened in the bible and arm themselves with sling shots. Ten stones against the head, and the giant falls down, at which point they cut his throat. All the dwarves survive.

Answer is 5 (Five). Explanation : Consider shortest dwarf as D1 and tallest dwarf as D10 Giant will ask D10 first about the color of his hat, as D10 can see all the dwarfs hat, instead of guessing his hat color he needs to tell the hat color of D1 , D9 should tell the hat color of D2 and so on , by this way when giant reaches D5 rest of the dwarfs including D5 will know their hat color , so D1,2,3,4,5 will be saved for sure , D6,7,8,9,D10 will have to purely depend on their own luck.

• Please read the first answer – Saurabh Raje Sep 26 '14 at 16:23