We are given countably many people numbered $1,2,3,\ldots$ for all $n\in \mathbb{N}$, each wearing a hat that is either black or white. No-one can see the color of their hat, but everyone can see everyone else's hat.
Now everyone has to guess the color of their hat.
Give a strategy that guarantees that an infinite number of people guess the color of their hat correctly.
How about this strategy
If you see an infinite number of white hats, guess white. Otherwise, guess black.
Reasoning
This guarantees that everyone guesses either white or black and each will be guessed only if there is an infinite number of that colour.
Here is another strategy, which requires looking at just 1 other person's hat:
Pair off the people $2k+1$ and $2k+2$.
Person $2k+1$ supposes that their hat colors are different, and person $2k+2$ supposes that their hat colors are the same. Exactly one of them will be right. This guarantees a 50% density of correct guesses.
So I just wanted to solve an amazing extension of this puzzle that I happen to know of.
Suppose that there were more than two colors. In fact, let's suppose that there were an uncountably infinite number of colors (so we're effectively writing a real number on each hat). And of course, we still have a countably infinite number of people in line. Is there a strategy that permits only a finite number of people guessing wrong?
Amazingly, the answer is still yes. The answer uses some abstract algebra, but I'll try to simplify it.
Firstly a relation is basically a relation between two things. For example, the relation "is greater than" is $>$, and we have statements such as $2>1$, $3>2$. If we define a relation $R$ to be "has a crush on" then $\text{Me}\ R\ \text{Grace}$ would be true, but $\text{Grace}\ R\ \text{Me}$ probably isn't.
There is a special type of relation called an equivalence relation. It's a relation that is very similar to equality. Some properties of equality that you may remember are:
So, equality is a relation that is reflexive, symmetric, and transitive. Similarly, a relation $R$ is an equivalence relation if it satisfies these three properties.
For example, the relation $M$, defined as "is in the same math class as" is an equivalence relation, assuming everyone takes exactly one math class. So $\text{Me}\ M\ \text{Sophia}$ is true because Sophia and I both take AP Calculus BC. Likewise, it should be obvious that $\text{Sophia}\ M\ \text{Me}$, so we have the symmetric property. I'm in the same math class as myself, i.e. $\text{Me}\ M\ \text{Me}$, so we have the reflexive property. Lastly, since $\text{Sophia}\ M\ \text{Allison}$, it is obvious that $\text{Me}\ M\ \text{Allison}$, confirming transitivity. These three properties imply that $M$ is indeed an equivalence relation.
The relation $R$, defined as "has a crush on", is not an equivalence relation, because it violates all three conditions. I don't particularly like myself, and nobody that I have a crush on feels the same way, so we have many counter-examples here.
The relation $C$, defined as "is within one mile of", is not a equivalence relation either. While it is true that $\text{Me}\ C\ \text{Me}$, and $\text{Me}\ C\ \text{Person B}$ implies $\text{Person B}\ C\ \text{Me}$, the transitivity condition does not hold. That is, just because $A$ and $B$ are within one mile, and $B$ and $C$ are within one mile, does not mean that $A$ and $C$ are within one mile.
Equivalence relations are extremely important because they can split up a set into equivalence classes. Let's consider again the math class relation $M$. Notice how it literally splits all students in my school into classes. In each class, you can take any two students $A$ and $B$, and it will follow that $A\ M\ B$. However, no two students $C$ and $D$ in different math classes will satisfy $C\ M\ D$.
In other words, everyone in Ms. Dwyer's Calculus BC class is related under $M$. Likewise, everyone in Mr. Holden's Calculus BC class is related under $M$. However, no two students, one of which is in Dwyer's class with the other being in Holden's class, are related under $M$.
Thus, $M$ splits the students of my high school into equivalence classes, and each equivalence class is a set of students in a literal math class. Another example is the relation $X$, defined as "has the same last digit as". This splits the positive integers into 10 equivalence classes: $\{1, 11, 21, \cdots\}$, $\{2, 12, 22, \cdots\}$, $\cdots$, $\{10, 20, 30, \cdots\}$. Because of how equivalence relations are defined, they will always split sets into disjoint equivalence classes.
Now we're ready to go back to the puzzle. We start by assigning an order to the people, so the colors will form a sequence:
$$\text{Red, Green, Blue, Fuschia, Brick Red, }\cdots$$
We define a relation $R$ on the set of hat color sequences. Two possible hat color sequences $A$ and $B$ satisfy $A\ R\ B$ if they are eventually the same after a finite number of terms. That is, consider the two sequences:
$$A = \text{Red, Green, Blue, Fuschia, Brick Red, Green, Purple, Hot Pink, }\cdots$$ $$B = \text{Black, White, Magenta, Fuschia, Brick Red, Green, Purple, Hot Pink, }\cdots$$
For a few colors, $A$ and $B$ aren't on the same page. But eventually, they are the same for the rest of the sequence! (I know I didn't show an infinite number of terms in each sequence to convince you, but just trust me lol)
Is $R$ an equivalence relation?
Well, any sequence is the same as itself. And, if $A$ and $B$ are eventually the same, then $B$ and $A$ are eventually the same. Finally, if $A$ and $B$ are eventually the same, and $B$ and $C$ are eventually the same, it will follow that $A$ and $C$ are eventually the same. Thus, $R$ is an equivalence relation. That means $R$ splits the set of possible hat color sequences into equivalence classes.
Now what's the strategy? The countably infinite number of people, before the puzzle starts, will discuss. They define the relation $R$, and note the infinite number of equivalence classes created by $R$ on the set of possible hat color sequences. Then, they invoke the Axiom of Choice by choosing a representative element from every class.
For example, for the (only!) equivalence class that contains the sequence $\text{Blue, Green, Red, Red, Red, Red, Red, }\cdots$ (that is, the set of sequences that all eventually become completely Red), they may choose the representative $\text{Hot Pink, Fuschia, Magenta, Red, Red, Red, Red, }\cdots$. Everyone makes sure that they agree on which representative to choose, and that they remember exactly which representative to choose given the equivalence class.
Now the game starts, and the plan is set into action. They stand in the agreed order, and open their eyes. Suddenly, everyone can see the infinite hat colors down the line. That means that everyone knows which equivalence class this particular hat sequence is in. And, everyone remembers which representative to choose from this equivalence class. Everyone then guesses their hat color in accordance to this representative.
For example, if the third person sees:
$$\text{Green, Blue, ???, Blue, Red, Red, Red, Red, Red, Red, }\cdots$$
Then that third person knows they are in the "eventually all red" equivalence class, and recalls the agreed-upon representative sequence $\text{Hot Pink, Fuschia, Magenta, Red, Red, Red, Red, }\cdots$. That means the third person will guess Magenta. Likewise, the two people behind him will guess Hot Pink and Fuschia, while everyone else guesses Red.
Why does this strategy work? Exactly because of the way we defined $R$. If we know that our representative sequence is eventually the same as the actual sequence after a finite number of terms, then only a finite number of people could possibly guess wrongly until they start getting the rest of the colors right. In the example above, the first four people were dead-wrong, because the actual sequence was:
$$\text{Green, Blue, Sewage Green, Blue, Red, Red, Red, Red, Red, Red, }\cdots$$
And the chosen representative sequence that they used to guess was:
$$\text{Hot Pink, Fuschia, Magenta, Red, Red, Red, Red, }\cdots$$
But both sequences were eventually the same after a finite (4) number of terms, so all the people that starting guessing red from the fifth person onwards got it right.
Yeah math makes no sense. And yet it does, somehow. Isn't that great?
I think this should work:
If everyone guesses randomly black or white, then 50% of the infinite number of people will guess it correctly, which is still an infinite number of people.
Save infinetely many people:
Every odd-numbered person says the color of the hat of the even-numbered person before them, so the even-numbered person can save themself. Saves 50% of the people.
Save 100% of the people (counted by limit of "save X% of the people out of first N" as N goes to infinity):
Every
2^nth person will say "white" if the number of white hats between the next2^n-1people is odd, or "black" if it is even. From this the2^n-1people can decude their hat color, same as in the non-infinite version of this problem.
Sacrifice only finitly many people:
I think this solution is from a Numberphile video, and it requires an axiom of choice. It works like this: Consider an equivalency on all countable boolean sequences defined as "2 sequences are equal if they have differn only in finitly many values". Then, every person knows which class does their sequence of white and black hats fall into, all they haveto do is choose one sequence from the same class (everyone needs to choose the same) and their guess their hat color accorting to that. Only finetly many of them will be wrong, because the guessed and real sequences were equivalent.
This could be a simple solution
Form a group of 2 people each, and since N supposedly tends to infinity, there is no way to say that it is odd. Hence we can assume that there are infinite pairs of two people. Note that there is no condition on communication like "a person cannot tell someone else the color of the latter's hat".
Proceeding with this fact, every person can know their hat color from their group partner. This guarantees that with infinite people, everyone will eventually know about their hat color.
P.S.
N could be a finite even or odd number. In case of even N, we can proceed with the above strategy, and in case of odd N, the last group will be of 3 people.
To me, this seems pretty simple. It avoids statistics, grouping people into random groups, and is fairly straight forward.
! This assumes that someone has already guessed their hat color correctly, but simply asking "Is my hat the same color as your's" to someone who already knows their hat color will allow a single Q&A, and will also allow the spread of correct guessing at an exponential rate. As long as people are within listening distance of the question, they can learn the correct question without having to ask a question to get the correct question. Also, it would only take 1 person to correctly guess their hat color and 1 other person to know this question to start this chain reaction.
Ok, so thinking about it again, the answer is different, but still simple.
If there are an infinite amount of guessers, there will always be an infinite amount of correct answers regardless of what they guess. Statistically, 50% would be correct, but 50% of infinity is still infinity. If only 10% were correct, then it's still an infinite amount of correct answers. The same applies if only 1% or 0.00001%, since it would still be an infinite number that would be correct. Even if 10% guessed primary colors and another 10% guessed pastels, there would be an infinite number of people who guessed each color.
To go further:
It doesn't matter what algorithm is used to product guesses, they will all produce an infinite amount of correct guesses, as long as it doesn't produce 100% wrong answers.
It's pretty simple every person should exchange his/her hat with any other person whose hat colour he exactly knows, now that makes a pair have their hats guessed correctly, likewise, since there are infinite people, infinite pairs will be formed and every pair would guess correctly
