This is a solution to problem 1 on the hard interview questions node. If you have not read the question, the following will make no sense to you:

The dwarves have a strategy that will cost the life of at most one dwarf. If you want to know what this strategy is, read on.

Let black hats signify 1's and white hats signify 0's. Each dwarf calculates the parity (sum modulo 2) of the hats in front of him. The first (tallest) dwarf announces the color corresponding to the parity he calculated. He may or may not be killed (depending on his luck... of course the Wizards can always engineer it so he dies, because they know this is the optimal strategy).

The next dwarf compares the parity he calculated and the parity the first dwarf announced. If the two parities are the same, that means his hat is white, otherwise it is black. He announces this color, and lives.

Each successive dwarf, armed with the original parity of all but the first dwarf and the colors of the hats of all the preceding dwarves (but the first), can easily calculate the color of his own hat. An inductive proof of correctness is pretty easy.

Thus only the first (and tallest) dwarf dies... which I guess explains why dwarves are so short.

There is a less mathematical but equally valid way for the dwarves to convey what they see to the next in line, which is to simply encode it in the response (alternating the pitch of the response, the pause before the response, the length of the response, etc. according to coded values for black v. white) - without saying anything but their response to the Question. This is basically just a different way than the parity solution of conveying information to the next dwarf.

While this isn't a very CS-answer, it is legal and superior to using parity since it removes the necessity for the dwarves to be able to see every dwarf before them - the existing answer becomes infeasible if the village's numbers approach normal (sizable) population levels (or the dwarves' eyesight approaches normal dwarf eyesight...). Thus the given solution can't solve without additional conditions.

One can also argue that this solution keeps the death toll close to the optimal '1', since "all dwarves in the village" includes those young, uneducated, and shortsighted (and thus less able to calculate parities for the remaining dwarves).

Log in or register to write something here or to contact authors.