wu :: forums (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
riddles >> hard >> strategy to guess Infinite hats correctly
(Message started by: inexorable on Nov 1st, 2005, 7:41am)

Title: strategy to guess Infinite hats correctly
Post by inexorable on Nov 1st, 2005, 7:41am
At the annual Commencement ceremony of 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, i.e he can see if a color occurs infinite times.  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(one can't write on other's slip or exchange etc); all slips are turned in to the dean.(here dean collects and checks the correctness of each student one after another)  If all but finitely 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
Hint:- Axiom of choice

Title: Re: strategy to guess Infinite hats correctly
Post by Joe Fendel on Nov 1st, 2005, 9:05am
As the first step to developing such a strategy, I would propose that if you view only a finite number of blue caps, then guess "red" and if you view only a finite number of red caps, then guess "blue".

But what if there are an infinite number of each?

Perhaps we need an ultrafilter?  But how would we describe it?  (The hint is disquieting: using AC to develop a "strategy" seems paradoxical - AC is non-constructive.)

Title: Re: strategy to guess Infinite hats correctly
Post by Barukh on Nov 1st, 2005, 9:25am
Very interesting!

Somewhat relevant is the following thread (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1112748623;start=0#0).



Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board