Mark Gritter (markgritter) wrote,
Mark Gritter

Infinite Hats

Via bramcohen, a puzzle in higher mathematics.

Suppose there are countably infinite number of people (or angels, if you prefer.) Each angel has either a red hat or a blue hat. Each angel can see all the other angels' hats, but not his own. Is there a strategy for each angel to guess her hat color (without further communication among angels) which produces only a finite number of wrong guesses?

It helps to think of the angels as being numbered (which we can do since they're countable.)

Informal proof: Two assignments of hats are "almost the same" if they differ by only a finite number of hat assignments. "almost the same" forms an equivalence relation, because two assignments of red and blue to angels must differ by either a finite number or an infinite number of hats. (If A and B are "almost the same" and B and C are "almost the same" then A and C must differ by only a finite number of assignments as well.)

That means the set of hat assignments can be split into equivalence classes, i.e, sets of assignments, where all assignments are "almost the same" as every other member of the set. The axiom of choice says that there is a new set S consisting of one element from each of the equivalence classes--- a representative of that equivalence class.

Now, each angel can observe the colors of all the other hats. That means that the angel can figure out which equivalence class the hat assignment is in (under the working assumption that he has a red or blue hat--- since this is a difference of just one hat so the result is in the same equivalence class either way.) The angel picks the representative assignment from S for that equivalence class, and guesses that his hat is the color given in that representative. Note that the representative assignment will usually differ--- by a finite amount--- from the actual assignment the angel observes.

Since every angel guesses an assignment within the same equivalence class as the real assignment, the total number of wrong guesses must be finite. (However, the expected number of wrong guesses is unbounded!)

Unfortunately, many of these steps require an infinite amount of work. But (if we're not happy in terms of angels) we can recast the problem in terms of proving the existence of a higher-order function.

An assignment of hats to angels is a function c:N->{red,blue}. (N is the natural numbers, and let RB={red,blue}.) Angel i observes c_i:N/{i}->RB. The desired strategy is a function F : ( N/{i}->RB ) -> RB. The proof is nonconstructive--- the axiom of choice tells us that there is such an F but not what it looks like.
Tags: geek, math
  • Post a new comment


    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.