A new graduation requirement for math/CS majors is under discussion. Each year's class will be gathered in a room and a professor will place hats that are either black or white on each student's head. The hats will be chosen completely randomly. Each student can see the hats of all the others, but not his or her own.
At a certain time, all the students will vote on the color of their own hats, but they can vote as many times as they like. For example, one student might say: "I vote 100 times that my hat is black." A student can choose not to vote.
If the majority of votes (i.e., > 50%) cast is correct, then all the students graduate; if not, none graduates. The students can get together in advance to decide on a voting strategy. If you were such a student, what strategy would you advise your classmates to follow?
Notes:
The idea is to come up with the best strategy. For ease of computation, we can assume that the number of students is 12. State the strategy clearly in case we have to program it to check its probability of success in all 2^12 hat distributions.
The votes are to be SIMULTANEOUS! The students all go into separate rooms and see computer screens telling them the colors on all other students' hats. They then vote, ignorant of the other votes.
Source: Joe Buhler, in his EMISSARY(the MSRI Newsletter) column, and also his forthcoming paper Hat Tricks, for The Mathematical Intelligencer. Modeled after a theorem in a paper of James Aspnes et al, Combinatorica (1994) 135-148.
© Copyright 2002 Stan Wagon. Reproduced with
permission.