5.00 (3 votes)
Loading...
Can you figure out which color hat you’re wearing? If you’re confused, check out this fun math game/puzzle.
You and infinitely many other people are wearing hats. Each hat is either red or blue. Every person can see every other person’s hat color, but cannot see his/her own hat color; aside from that, you cannot share any information (but you are allowed to agree on a strategy before any of the hats appear on your heads). Everybody simultaneously guesses the color of his/her hat. You win if all but finitely many of you are right. Find a strategy so that you always win.
Its calles the blue eye puzzle: http://xkcd.com/blue_eyes.html
And you need a external source, which adds the information, that one person wears a blue hat.
It’s not the same puzzle. In this case there are infinitely many.
We assign a natural number to each person, and let person n+1 stand next to person n, turned the same way if person n wears red, the opposite way if person n wears blue. Then they all look to the side and correctly guess their hat color.
Granted, this does translate into communicating some information, but I don’t see how the strategy can not involve some sort of information transfer.
well., there are two special cases in which it will be very easy to win: if there are infinitely many red and finitely many blue hats, or infinitely many blue and finitely many red. If you see there are only finitely many blue, you can guess that you are wearing red., in which case everyone guesses red. As a result those people wearing blue hats are incorrect but as mentioned in the hypothesis there are only finitely many of them and as such the group reaches the win condition.
As far as a winning strategy for if there are infinitely many red and blue hats., I don’t yet see a solution that doesn’t involve communication of some sort. Perhaps I’ll think of one later…
Answer(spoilers):
ok, so we line up (ie. map everyone into the natural numbers one to one) and we define a function f from the naturals to {0,1} were f(n)=0 if the nth person has a red hat and and f(n)=1 if the nth person has a blue hat.
Now, define an equivalence relation on all infinite sequences on {0,1} as follows:
two sequences are equivalent if they are eventually equal (ie. h~g iff there exist k such that for all j>k, h(j)=g(j) where h,g:N–>{0,1}).
Split up the set of all sequences into equivalence classes and choose a representative from each eq. class. Let [f] be the equivalence class containing f.
Since everyone can see the whole tail of the sequence f, we know what [f] is, so we all guess as though the representative from [f] is equal to f. Since f and the representative from [f] are eventually equal only finitely many people guess wrong.
lily, your argument has a transcendence error: it holds for any finite subset of people wearing hats, but it doesn’t transfer to the infinite set IN. The problem when you try to formalize it is that the k you need to exist actually doesn’t.
To me, for the case of initely many hats of both colors, this puzzle is a math fail.
sure it exists, if 2 sequences are eventually equal then such a k exists by definition.
And the representative from [f] and f are eventually equal, since thats how the equivalence classes were defined, so such a k exists.
The problem is that there doesn’t exist such a k that works for all n – and that makes your proof collapse because you can’t go from “each n” to IN.
In short, your proof goes like this:
For each finite n in IN, there is only a finite number of people guessing wrong.
Therefore, in IN there is only a finite number of people guessing wrong.
With the same logic you can “prove” that IN is finite – which it’s not.
Your proof dwells on the fact that the “head” of the sequence is finite, which in case of infinitely many guessers it is not.
im not sure where “for each n only finitely many guess wrong” comes from.
I’m not saying that, i’m saying that everyone after the kth person guesses right. You have to agree with that, otherwise the sequences wouldn’t be eventually equal.
“I’m saying that everyone after the kth person guesses right.” Well, that’s contradicting your premise, which is that everyone sees the complete tail after k – but the people after k do not know their own hat color and hence do not know the whole tail, so they’re likely to guess wrong.
If you can argue that everyone after the kth person guesses right, then yes, obviously there can only be finitely many wrong guesses, but I don’t see the proof of that.