Prove that S must be countable.

[This question was asked in the qualifying exam of a Berkeley math PhD student by the Functional Analysis examiner. I have no idea why he chose to ask an elementary question (meaning, a question that can be answered from first principles) like this, but the student had some trouble coming up with the right answer]

The following are three versions of this problem, in increasing order of difficulty.

- The hats can be either red or blue. The prisoners are lined up and face forward, so that prisoner 1 can see the hats of prisoners 2, 3, ..., n, but not his own, prisoner 2 can see the hats of prisoners 3, 4, ..., n but not his own nor the hat of prisoner 1, and so on. Prisoner n sees nothing. The game is that each prisoner says his guess aloud, in the order in which they are lined up, so that is prisoner 1 is first, prisoner 2 is second and so on. Everybody can hear what everybody before him says. The prisoners are all released if at most one of them makes a mistake. Prove that, with the proper strategy, they get released no matter the initial hat colors.
- The hats can be of any of n colors; the list of n allowed colors is known. Every prisoner can see the hats of everybody else (but not his own). Every prisoner writes down his guess for his own color on a slip of paper and gives it to the guards, so no prisoner knows anything about the other prisoners' guesses. The prisoners get released if at least one of them makes the correct guess. Prove that there is a strategy that, if followed, allows the prisoners to always get released

[This is tricky. The solution uses modular arithmetic] - The hats can be either red or blue. There are infinitely many prisoners, each one identified by a natural number, so there is prisoner 1, prisoner 2, ... and so on. Each prisoner sees everybody else's hat colors. As in the second problem above, each prisoner makes a guess that is unknown to everybody else. The prisoners are released if only finitely many of them make a mistake. Prove that there is a strategy that allows them to always get released.

[This is much harder than the other two. The solution uses equivalence classes]

Prove that, for every k, every sufficiently large graph must have either a clique of size at least k or an independent set of size at least k. That is, prove that for every k there is a number n_{k} such that in every graph that has at least n_{k} vertices there must be either a clique of size at least k or an independent set of size at least k.

Here is a hint: try to prove the seemingly stronger (but actually equivalent) statement that for every k and every i there is a number n_{i,k} such that in every graph that has at least n_{i,k} vertices there must be either a clique of size at least k or an independent set of size at least i. Here is another hint: proceed by induction on i+k.