11
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Possible duplicate of Infinitely many dwarves wearing hats of 2 colours $\endgroup$ – phenomist May 27 at 8:04
  • 2
    $\begingroup$ That puzzle uses the axiom of choice, but everyone except a finite number of dwarves guesses correctly, which is stronger than what this riddle here asks for. But there is a solution to this riddle that works without using the axiom of choice $\endgroup$ – Dominic van der Zypen May 27 at 8:09
  • $\begingroup$ I believe this also actually works if the numbers were real. $\endgroup$ – greenturtle3141 May 27 at 8:14
  • 1
    $\begingroup$ @aschepler, this puzzle specifies that "everyone has to guess the color of their hat" (emphasis supplied). Your solution doesn't work. $\endgroup$ – msh210 May 28 at 9:55
  • 1
    $\begingroup$ @DarrelHoffman Agreed, but I ask because a lot of answers are trying to get around that rule in some way. I looked back at the question and saw it wasn't explicitly mentioned so thought I would ask to maybe get OP to include it to prevent them. $\endgroup$ – Trenin May 28 at 14:21
18
$\begingroup$

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.

$\endgroup$
  • 7
    $\begingroup$ Would being able to count infinitely many white hats be something a normal person can do? I know the problem says each person can see each other person's hat, so they should have access each other person's hat color, but not necessarily meta-data about how those colors are distributed. So IMO the person should be able to 'easily' check "Do I see 10,000,000,000 white hats?" but should not be able to check "Do I see an infinite number of white hats?" $\endgroup$ – Hoog May 27 at 17:44
  • 1
    $\begingroup$ @Hoog I see your point but I think you're introducing a restriction from the physical world into a problem that is completely unphysical. How about this, if there were only a finite number of white hats, what would one expect to see? $\endgroup$ – hexomino May 27 at 22:06
  • 4
    $\begingroup$ You can simplify it to guess white if you see at least one white hat in front of you, otherwise guess black. if there is only a finite number of white hats, after the last one everyone will guess black and be right. If there is an infinite number of white hats everybody will guess white and infinitely many will be right. $\endgroup$ – Ross Millikan May 28 at 2:21
  • 1
    $\begingroup$ @RossMillikan That is a very neat solution. $\endgroup$ – hexomino May 28 at 9:08
  • 1
    $\begingroup$ What happens when there's an effective even mix of white and black hats? Even if there are some random clumps of white hats, there could be similarly sized clumps of black hats. Since there would be no obvious larger amount of one color of hat, what do people guess? This even applies to an even mix of an infinity of black hats and an infinity of white hats. An individual would see an infinite amount of black And white hats. $\endgroup$ – computercarguy May 28 at 20:57
22
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This is usually asked with people in line and one can only see the hats in front of you. $\endgroup$ – Ross Millikan May 28 at 2:22
  • 17
    $\begingroup$ Who cares how “This is usually asked”?  This question specifies that “everyone can see everyone else’s hat.” $\endgroup$ – Peregrine Rook May 28 at 3:06
  • $\begingroup$ This solution would work even if the problem were clarified to make clear that no individual can judge whether they can see an infinite number of white hats nor an infinite number of black hats, and that once the hats are given out, no individual can receive any information via any means whatsoever other than the colors of any individuals' hats they choose to examine. $\endgroup$ – supercat May 29 at 16:23
11
$\begingroup$

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:

  1. $a=a$ for any number $a$. (Reflexive Property)
  2. If $a=b$, then $b=a$. (Symmetric Property)
  3. If $a=b$ and $b=c$, then $a=c$. (Transitive Property)

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?

$\endgroup$
  • 1
    $\begingroup$ Of course, this would take uncountably many comparisons, for the person to evaluate their own sequence vs. uncountably many candidate representative sequences. $\endgroup$ – LegionMammal978 May 28 at 1:21
  • $\begingroup$ TL;DR.   Would this work for $\pi$ colors? $\endgroup$ – Peregrine Rook May 28 at 3:12
  • 1
    $\begingroup$ An interesting question - does a strategy exist which guarantees that both the set of wrongly guessed people is finite and the number of actions per person is at most countably infinite? $\endgroup$ – trolley813 May 28 at 7:55
  • 1
    $\begingroup$ @trolley813 Absolutley not. There are uncountably many equivalent classes. The requirement is that everyone agree on each and pick a candidate as the representative. Even if there were a countable number of equivalent classes, this would take an infinite number of 'operations' before starting the game. $\endgroup$ – Trenin May 28 at 12:38
  • 1
    $\begingroup$ @PeregrineRook 1) not really a pun but yeah ig. 3) you're right, the "im putting a REAL NUMBER on each hat ooo" throws alot of people off when i send this q to them. 5) yes, you'd need people with infinitely powerful minds that can remember an infinite number of things in finite time. But I'd argue that since we've already trespassed reality with an infinite number of people, we may as well consider the game in its most pure form and allow such antics with infinite memory and processing speed. 6) are you concerned with the aforementioned infinite memory part? 7) why yes! a beautiful color. $\endgroup$ – greenturtle3141 May 29 at 1:28
2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ It can happen that all the hats are white, but "by chance" everyone guesses that their hat is black, so $0$ people guess the color of their hat correctly, right? $\endgroup$ – Dominic van der Zypen May 27 at 8:07
  • $\begingroup$ No because the limit of the probably that x people will guess wrong as x goes to infinity is zero. (lim x->inf 1/x=0). So there is zero chance of that happening. $\endgroup$ – Alto May 27 at 22:14
  • 4
    $\begingroup$ @Alto The question didn't ask for a strategy that almost certainly results in an infinite number of correct guesses, but a strategy that guarantees one. (This is equivalent to the hat colors being arranged by an adversary with access to the people's strategy.) $\endgroup$ – LegionMammal978 May 28 at 0:47
  • 1
    $\begingroup$ @Alto I agree with Legion. Lets say the adversary knows your RNG. He then orders the hats such that you always guess wrong. $\endgroup$ – Trenin May 28 at 12:48
  • $\begingroup$ That's just the deal with infinity: it's big enough to actually make the chance of failure into exactly zero. Nothing "almost" about it. $\endgroup$ – Bass May 29 at 6:22
2
$\begingroup$

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 next 2^n-1 people is odd, or "black" if it is even. From this the 2^n-1 people 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.

$\endgroup$
  • $\begingroup$ (1) If the question had any restrictions on people talking to each other, and making their “guess” based on what other people have said, I would want to look at that closely, as your answer seems to be pushing that envelope.  Absent any such restriction, I suppose that your first two answers work.  (2) Your third answer seems to be very similar to greenturtle3141’s answer.  Even if you didn’t know about that, you should specifically identify the video that provided that answer.  … (Cont’d) $\endgroup$ – Peregrine Rook May 29 at 0:52
  • $\begingroup$ (Cont’d) …  (3) I believe that “countable sequence” is redundant.  You can have an uncountable set, but not an uncountable sequence. $\endgroup$ – Peregrine Rook May 29 at 0:52
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ In problems like this, it goes without saying that people aren’t allowed to tell each other what color their hats are. $\endgroup$ – Peregrine Rook May 29 at 0:49
  • $\begingroup$ But like where do you draw the line? They can't tell each other what color their hats are? ok. What about what color their hats are not? If white say black or vice versa. Use some alias for the colors? Implement parity concept from dwarves and hats problem and we could still get to solving this problem. $\endgroup$ – Venkateshwara Rao May 29 at 5:19
  • $\begingroup$ A standard line-in-the-sand is that each person is allowed (in fact, required) to announce their guess / conclusion as to the color of their own hat, and nothing else.   That, of course, is after the game has begun (i.e., after the hats have been placed).  It’s common to allow unlimited strategy communication before the hats have been placed. $\endgroup$ – Peregrine Rook May 30 at 7:55
  • $\begingroup$ @PeregrineRook Thank you for explaining. $\endgroup$ – Venkateshwara Rao May 31 at 5:30
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ (1) I’m glad you struck through your first answer, because it seems to have a logic loop.  How would any one person first ‘‘know’’ their hat color?  Besides, in problems like this, it goes without saying that people aren’t allowed to tell each other what color their hats are.  (2) (Spoiler alert!)  You say “If there are an infinite amount of guessers, there will always be an infinite amount of correct answers regardless of what they guess.”  That is wrong.  If there are an infinite number of guessers from a finite list of possible choices, … (Cont’d) $\endgroup$ – Peregrine Rook May 29 at 0:49
  • $\begingroup$ (Cont’d) … then it is infinitely unlikely that there will be only a finite number of correct answers.  But this question isn’t about probabilities; it’s about a guarantee. (3) You say “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.”  Again, wrong.  It would be possible that there are 42 correct guesses (or a million).  Then there would not be an infinite number of correct guesses, but there would not be 100% wrong answers either. $\endgroup$ – Peregrine Rook May 29 at 0:49
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.