The Prisoners' Hat Paradox is a illustration of the logical problems involved with the axiom of choice in the form of a variant on a logic puzzle, wherein the warden of a prison puts black and white colored hats on prisoner and makes them guess the color of their own hat. This illustration of weird consequences of the axiom of choice is very rarely made, compared to more common examples such as the existence of unmeasureable sets and the weirdness that goes with them, like the Banach-Tarski Theorem. Unlike unmeasureable sets, which are more an issue about the subtleties of measure theory than about the axiom of choice, I think that the consequence illustrated in this paradox hits more to the point of why the axiom of choice should intuitively be rejected.
It is best to start with the logic puzzle on which the paradox is based (A different wording of the same problem is given as problem 1 on the hard interview questions node). Some number, N, of prisoners are stood in a column, each wearing either a white or a black hat, the color being chosen for them randomly and independently from the other hats. They are standing back to front so that each prisoner can see the hats of all the prisoners in front of him, but not his own or the ones on the prisoners behind him. The warden starts from the back of the line, prompting the back-most prisoner for his hat color, and making his way forward prisoner by prisoner. The prisoners are only allowed to say "black" or "white." They are executed if wrong and spared if right. All prisoners can hear the guesses of other prisoners and their outcome. The prisoners learn of the warden's plan and the rules described above the night before this is to take place and can therefore strategize beforehand. What is their best plan? The astute puzzler, or the less-astute, but experienced puzzler who has heard this one before, will be able to come up with a strategy wherein all but one prisoner are spared.
(This strategy, if you must be told, is for the back-most prisoner to say "black" if he sees an odd number of black hats and "white" otherwise. He only has a 50% chance of being right about his own hat, but that's not important . Thereafter, by counting the black hats accounted for by previous prisoners and black hats the prisoner sees in front, the prisoner can tell whether his own hat is black or white.)
The variations on this puzzle needed to turn it into a paradox are minimal: instead of a finite number of prisoners, take a countably infinite number of them (say, one for each natural number). Any attempt to extend the solution for the previous problem to this one results in an infinite number of executions. Let's make this even harder on the prisoners: let's say they now can't even hear what has happened before they are called on, and the only thing they have to go on is just the color of hats prisoners in front of them are wearing and their own position in the line. Since each prisoner has no information that could have been influenced or changed by the color of his own hat, the situation seems hopeless. However, granting the axiom of choice, there is a strategy that allows the prisoners to save all but finitely many of them.
The strategy is to consider the set of all possible binary sequences (where each term can be either "zero," representing a white hat, or "one," representing a black hat). We can partition this set into equivalence classes, where two sequences share an equivalence class if and only if they agree for all but finitely many terms. The night before they are to be lined up, by use of the axiom of choice, the prisoners choose exactly one sequence out of every equivalence class. The next day, whenever a prisoner is called, he knows exactly which equivalence class the actual sequence of white and black hats is in since he can see infinitely many hats, and only one of their prechosen sequences will agree with all but finitely many of the hats he sees. It is therefore possible for the prisoners to go on and recite a sequence that is in the same equivalence class as the actual sequence. By construction, that means that the prisoners will give their own hat color correctly in all but a finite number of cases.
This is an example of set theory weirdness.
(I wish I could attribute this paradox to whomever came up with it, but I have forgotten who described it to me. I tried googling to discover its origin, but came up with zilch)