Wizards and Drawves

There is a village of wizards and a village of N dwarves.

Once a year, the wizards go over to the village of dwarves and line all the dwarves up in increasing height order, such that each dwarf can only see the dwarves shorter than himself.

The wizards have an infinite supply of white and black hats. They place either a white or black hat on the head of each dwarf. Then, starting with the tallest dwarf (in the back of the line), they ask each what color hat he is wearing. If the dwarf answers incorrectly, the wizards kill him (the other dwarves can hear his answer, but can’t tell if he was killed or not). What is the most number of dwarves that will be killed using this optimal strategy?

Do note that the dwarves already know that the wizards will do as stated above. So, they can get together and devise an optimal strategy to minimize the people that get killed.

• Case 1 : Answer is a function of N. Output it with N with multipliers or divisor numbers following N. For example, N * 2, N / 2, N * 3 / 4.
• Case 2 : Answer is a integer. Just put the number without any decimal places if its an integer. If the answer is Infinity, output Infinity.
• Case 3 : Floating point number. Round it off to 2 decimal places and output it as I.xx where I is the integer part of the answer, and xx are 2 decimal digits after rounding off.

Feel free to get in touch with us if you have any questions