samedi 7 janvier 2006

Ten elves and a witch

Ten elves have been taken from Elfland by an evil witch. Worse still, the witch is planning to turn some of them into frogs.
But the witch isn't all bad: she gives the elves a chance.
The witch lines up all ten of the elves in single file, so that the elf at the back can see nine other elves in front of him, the next elf has eight other elves in front of him, and so on. The elf at the front can see no other elves.
The witch has a large number of hats in her wardrobe. Some are black and some are white, but there is no necessarily the same number of black hats as white hats. The witch randomly places a hat on each elf's head. The elf at the back can see nine elves with hats in front of him, the next elf eight, and so on. No elf can see his own hat.
The witch then takes out her magic wand and asks the elf at the back; "What color is your hat?" If the elf answers correctly, he will go free; if not, he is turned into a frog. The witch continues along the line saying the same thing. The elves can only say 'white' or 'black', and cannot add other information (by changing the pitch of their voice, for example).
The elves have been allowed to meet with you beforehand, and plan a strategy to save as many of them as possible. What do you tell the elves to do, and how many can you guarantee to save?