Friday, July 26, 2013

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?

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. 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?

Source: http://www.businessinsider.com/toughest-job-interview-questions-2013-7?op=1#ixzz2a9upxPNJ

9 comments:

Anonymous said...

There is one big assumption that has to be made here; namely that the giant has 5 black hats and 5 white hats that he puts on randomly. without that assumption, there is no strategy that works as there will be a 50-50 chance of a white or black hat on EVERY dwarf regardless of any or all prior hat colors.

Assuming 5 black and 5 white, the next dwarf listens to all prior answers and calculates the odds remaining of what his hat color will be. At least 1 dwarf will be saved this way as the final dwarf will know all 9 hat colors and know if the black or white one remains. Previous dwarfs just play the odds. If for example, dwarf 6 heard 4 blacks and one white, he should guess white as there is only one black left and four whites left. Ditto for all other elves but the tallest -- who will have to make a 50/50 call.

Lieke said...

That is not correct, because the giant starts asking the tallest dwarf, who is able to see all the other dwarfs. So if there are 5 black hats and 5 white hats, the tallest counts the other nine and calls the one with only four in front of him. And so on. All dwarfs can be saved.

If the assumption that there are 5 black hats and 5 white hats cannot be made, the following is the best strategy I think:
The tallest (nr 10) calls the color of the hat of the dwarf in front of him. That dwarf (nr9) calls the same color (his own hat) thereby saving himself. Nr 8 calls the color of nr 7. Nr 7 calls his own color and so on. All uneven numbered dwarfs are saved (so that makes 5) and the other ones have a 50% change of surviving.

brave heart said...

Lieke.. considering the 5 black & 5 white assumption not made and if tallest (10) guy speaks the color of 9th guy and if that doesn't matches with him. he is dead and 9th guy cannot hear that answer. so no one will survive.
The better way is the tallest(10) guy will know what is the majority no of hats in either or black white color. the two extreme cases are out of 9(1b, 8w) or (8b,1w)other way it could be 5w, 4b or reversal. If every one adopts the same strategy a minimum of 1 person and maximum of 9 persons can be saved

Perry said...

Regardless of how many hats there are in each colour, there is actually a strategy that will save a _minimum_ of 9 dwarves.

Anonymous said...

Although you can easily save 5, that's not the optimum.
You can save at least 6 Dwarfs! (Splitting the Problem in 'save 3 out of 5'). Perhaps more.
The idea is, that you have more information by let a dwarf choose, if he uses his color, or if he scarifies himself. So you get more information!
The Theory of 9 saved Dwarfs can't be correct, according to you have ONE information and 2^9 possibilities.

Anonymous said...

One strategy that will save at least 7 is the following:

Dwarves 8, 9 and 10 count the number of white hats in positions 1 through 7. There can be anything from 0 to 7 hats. They then encode this number in binary, requiring 3 bits, and then answer "black" for a zero and "white" for a one.

Dwarves 1 through 7 now know how may white hats (call it W) they have between them. Dwarf 7 counts the number of white hats in front of him. If the number is less than W, he knows his hat is white, otherwise it is black.

Dwarf 6 follows the same procedure, remembering to subtract one from W each time a taller dwarf declares a white hat. And so on down to dwarf 1.

Anonymous said...

You can save a minimum of 9 as follows:

Dwarf 10 counts up the number of white hats in front of him. If there is an even number be says "black" otherwise if an odd number he says "white". He has a 50% chance of being right about his own hat, but passes crucial information to the remaining 9 dwarves.

Dwarf 9 counts whether there are an even or odd number of white hats in front of him. If this differs from what dwarf 10 declared (encoded as black=even and white=odd), then he knows he has a white hat, otherwise a black hat. He gives the correct answer.

All subsequence dwarves 8 down to 1 can calculate the number of white hats in positions 1 through 9, including their own, by counting both the hats they can see and the ones they have heard behind them (ignoring dwarf 10). If there is a disparity between the even/odd-ness of this number, and what dwarf 10 originally declared, then they know they have a white hat. If not, they have a black hat.

(In boolean logic terminology they can use the XOR "exclusive or" to calculate the answer).

Mai said...

You can save at least 9 dwarfs - even without assuming there is an equal number of hats. The only dwarf that has a 50/50 chance is the tallest one. The key is telling the dwarf in front of you the color of their hat while naming the color of your hat at the same time. One way to do this may be to whisper for white and scream for black. You tell the dwarf in front of you that no matter which color I say, my pitch determines the color of your hat. The actual color that is said will be based on whether or not the dwarf behind me whispered or screamed. So for example - if the dwarf behind me screams white, I know I have a black hat on (scream = black). At the same time I see the dwarf in front of me has a white hat on. I would then whisper black.

Anonymous said...

I think Mai has it right, except I was leaning toward using intonation to indicate "same" or "different". Dwarf 10 (first one) says "Black" to indicate that the dwarf in front has a black hat. Dwarf 9 then says "Black?" to simultaneously note that his hat is black (correct) and the hat in front of him is not. If the hat in front of him was black he would say "Black" without the question mark. Dwarf 9 then says "White" if the hat in front of him is white, and "White?" if the hat in front of him is black. etc., this should reasonably save 9 dwarfs, but the first dwarf will have a 50/50 chance of dying.