Problem of the Week 928

The Wizards' Hats

Each graduating class at a college for wizards is given a final exam as follows: The Dean lines up the student-wizards in a row and places a hat -- either red, white, or blue -- on the head of each student. Each student sees the colors of the hats on people standing in front of him or her, but sees neither the color of his or her own hat, nor the colors of any hats on people standing behind him or her.

At the end of every minute, one of the wizards must announce a color, and each wizard can speak out once only. When all of the wizards have spoken, the dean passes those wizards whose statement matched the color of his or her hat.

This year's class consists of 928 wizards. Before the exam, the class gets together to devise a strategy that will minimize the number of failures.

How many students will graduate, if the class performs optimally?

Source: From the 23rd Russian Olympiad of Secondary Schools; published in Crux, Nov 2000.

© Copyright 2001 Stan Wagon. Reproduced with permission.

15 Feb 2001