Mathematics Problem Of the Week

Fall 2003

POW #12

Talking Turkeys – Roasted or Released?

A turkey farm specializes in raising particularly intelligent turkeys that can talk and reason mathematically. When slaughtering time comes, the farm manager makes the turkeys the following deal. As the turkeys are lined up for final “processing”, they will each be given a neck band that is either white or black (chosen at random for each bird). No turkey can see its own band, but each can see all of the bands on turkeys that are in front of them in line – but not those behind. Starting at the back of the line, the manager will ask each turkey to guess its band color. The turkey can only say “black” or “white”, all the turkeys hear the answer, but no other communication is allowed. If it guesses correctly, the turkey will be released, otherwise it will be roasted. The turkeys are allowed to meet the night before and devise a strategy to spare as many of them as they can.

Your job is to describe a scheme that will optimize the expected number of turkeys that are released. For example, the turkey at the back of the line could agree to say the color of the turkey directly in front of it. The back turkey would have a 50/50 chance of being released and the next one would know its color and be guaranteed a release. Repeating this process could guarantee that half of the turkeys are released. Can you improve on this?

You might start with a small number (say N=6 turkeys), but try to find a method that can be generalized (and effective) for a larger number (say N=100).

Due Friday, December 5th at Noon.

Last POW for the Fall semester!