Countably Infinitely Many Hats
Countably infinitely many mathematicians have been taken hostage. They are indexed by the positive integers (each mathematician knows their integer) and are standing in a line so that mathematician can see each mathematician for .
The mathematicians are each given a red or blue hat; they cannot see their own. Starting from the back (mathematician 1), each mathematician will guess their own hat color (one at a time) . They can hear all previous answers. All mathematicians who guess correctly may leave after their turn. The mathematicians are not allowed to communicate extra information other than their guess (e.g. by gesturing or changing tone on pain of death) to all the participants--they must simply guess.
Beforehand, the mathematicians have agreed upon a strategy to minimize the number of mathematicians who might guess incorrectly. Ignoring problems like limited vision or finite memory capacity and assuming the axiom of choice holds , what is the greatest possible number of mathematicians that might guess incorrectly?
This problem is original but based off of the famous red/blue hat puzzle . If you are stuck, try this problem first.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
The mathematicians apply an equivalence relation to the set of all sequences of red and blue hats. They agree that two sequences are equivalent if they differ in at most finitely many places (I will not prove here that this is an equivalence relation, but it is very easy to check for yourself). By the axiom of choice, they may agree on a representative sequence from each equivalence class. When it is time to guess, the first mathematician looks ahead and determines which equivalence class the actual sequence lies in. S/he then counts the number of places at which the actual sequence differs from the agreed upon representative (not include their own hat, of course). If the number of differences is even , mathematician one will say red . If the number of differences is odd . mathematician one will say blue .
Mathematician two will look ahead and count the number of differences. If they count the same parity as communicated by mathematician one, then they will guess the second element of the agreed upon representative. If they count the opposite parity, they will guess the opposite color. (This ensures mathematician two guess correctly.)
After hearing mathematician two's answer, mathematician three will still know the parity of the differences by noting whether or not mathematician two guesses as if s/he were in the representative sequence. Thus, mathematician three will similarly guess correctly. So on down the line, each mathematician will know the parity of the differences in front of/including themself by listening to previous answers. Thus, all mathematicians (except possibly mathematician one) will guess correctly.
Unfortunately for mathematician one, their knowledge remains unchanged if their hat changes color (since they are the first to guess, nothing can be communicated to them). Thus, they cannot guarantee that mathematician one will guess correctly. Therefore, the answer is 1 .