Problem of the Week 1035

Infinite Hats

At the annual Commencement ceremony at AlephZero College, the infinite graduating class is lined up in a row as #1, #2, #3, .... Each student wears a gown with the integer indicating his or her position clearly marked on the gown (very small pens are used). The dean places a hat, either red or blue, on each student's head. Each student can see the hats and gowns of all the other students, but requires one second to determine the color of a particular hat. No other communication between the students is allowed.

After all hats are placed (the dean is very experienced at doing this, requiring only a minute to place them all), a bell rings and each student looks at the hats of the others. In one hour the bell rings again, and each student must write down a color on a piece of paper; all slips are turned in to the dean. If infinitely many students correctly name the color of their own hat, all students graduate. Otherwise, none do.

The students can get together in advance to agree on a strategy. Find a strategy that guarantees that all students graduate regardless of how the hats are placed.

SOURCE: This arose during conversations over the summer among Jim Henle, Jim Guilford, John Guilford, Alan Taylor, Joe Buhler, and Stan Wagon. The discussion was inspired by work of Chris Hardin, Yuval Gabay, and Mike O'Connor, who came up with a beautiful hat-color problem and solution that is a little beyond the scope of the PoW, but which I will share here as an extra credit problem.

EXTRA CREDIT: The set-up is as above except that each student now can look at the hats of all the other students. In such a case it is easy for the students to get infinitely many right: a student simply checks to see if RED occurs infinitely often. If it does, he or she (indeed, all students) guesses RED; if it does not then the student (indeed all students) guesses BLUE. But here is the surprise: Find a strategy that guarantees that ALL BUT FINITELY MANY students guess correctly. Hint: You may use the Axiom of Choice. Indeed, as essentially proved by Chris Hardin and Alan Taylor, some use of AC is required. To be precise, their proof is for the case where each student sees all the hats of students with a higher number.

7 September 2005