Hat problems
Joe: Hat problems is a genre, many people like to use it to frame various combinatorial problems.
If you go far enough with these you end up with error correcting codes, (of course your smartphone depends on those),
but today I'm just going to show you several hat problems.
The two hat problem, uh, involves two people, each of whom is going to have a blue or a red hat placed on their head
by an impartial referee who's going to flip a coin to determine whether I'm going to have a blue hat
or a - whoops - a red hat
*laughs*
Brady: So you're wearing a blue or a red and I'm playing too, aren't I?
J: That's right you have a blue or red -
B: on my head. I can't see it.
J: There are a bunch of rules here
You might imagine me doing that and looking up like that and that's not allowed.
In fact, if this were being played for money,
we would each be locked in a jail cell with a TV screen
and the only thing we would see is our names.
And under your name, I would see a hat. And under my name, I would see a choice.
I can predict my hat colour. I can say either blue or red. Let me talk you through a game.
OK, so the hats have been placed on our head by a referee
and now I see your hat and I'm supposed to, first of all, predict my hat colour on a signal.
Simultaneous with your prediction, we each make a prediction of our hat colour.
I haven't seen mine, which means my prediction is 50/50,
your prediction is 50/50.
B: Because both of our hats were randomly chosen and the choice isn't connected in any way.
J: The choice is not connected the referee flipped a coin for each one.
There are four possible ways the hats could be.
They're: two reds; blue red; red blue; and two blues.
We make a prediction but the goal is a little unusual.
The goal is that exactly one of us is right. In other words, we succeed if you're right, and I'm wrong or vice versa,
we fail if we're both wrong or both, right.
B: So one of us has to be right, one of us has to be wrong about the colour on our own head
J: This looks awfully challenging. [Mhm] My guess about my head color is just a guess.
It has 50% chance of success. Your guess has 50% chance of success,
and the goal is not only to try to be one right, one wrong, but to get that all the time.
Somehow combining these 50/50 s and coming up with certainty
certainly sounds impossible at first glance.
Once you see the idea you'll see that your mental Image of that was not right.
B: Oh yeah, that's not bad. Not bad
Not bad
J: OK, here's the winning strategy: the night before we agree that, on the following, you will be agreeable
and you will say whatever colour you see and I will -
B: So I'll say red, you're wearing red.
J: I'm wearing red, so you're gonna say red. B: OK
J: And, on the other hand, I'm going to be disagreeable,
and I will say the opposite of what I see.
And, you're wearing blue, so I'm gonna say red.
We're both going to say red in that circumstance.
You can make a table and figure out why we're -- there's always going to be one of us correct,
but if you think about it, there's a very intuitive reason.
I'm betting that the colours are opposite,
and you, being much more agreeable, are betting that the colours are the same.
And so therefore, clearly, one of us is right and one of us is wrong.
B: What if the rules of the game had been that we both have to be right? Could we have had a winning strategy then?
J: If we both have to be right there is just no way we can do it.
And so there's something about this particular set of rules that enables this magic trick.
3 Hats
There's a famous three hat problem that arose about twenty years ago, it got a lot of press.
And let me describe that one to you. There are now three players:
Alice, Bob, and Charlie.
And the rules are still: we're going to have hats placed randomly on our heads;
we are not allowed to communicate once that's done;
At a bell, say, ten seconds after the hats are replaced,
the three possible answers are red blue and pass.
And those are predictions for my hat colour
and of course the rules include the fact that everybody sees to hat colours, but not their own.
and ag-- maybe I should have this off of at this p-- B: I like it! But anyway, it's up to you.
*laughter*
B: What's the idea to win the game here?
J: So here the, uh, each of the three of us makes a prediction or passes.
And we win If there are no incorrect predictions, and at least somebody makes a prediction.
Or, we lose if anybody says something wrong or if everybody passes.
Have to scratch your head a little about that, but it's actually, uh, fairly natural
B: So at least one person has to make a guess and everyone who makes a guess must be correct. J: That's right
So if we do that, we're all freed from jail, or get a million dollars. Pick your favourite reward. Now --
B: Yeah, well, it depends on your current circumstance.
J: You might start thinking of some strategies.
One that you might take, if you didn't have a strategy session, was: everybody guesses.
OK, let's think about that.
Alice Bob and Charlie each make a guess
By the rules, namely, each hat is randomly chosen, each of those has probability of 1/2 of being right,
so the chance that we would win with that strategy is one out of eight.
If you think about it a little bit it would be better if just one person, say, Alice, guessed.
One reasonable strategy is Bob and Charlie pass, Alice guesses.
Now that comes down to a coin flip. Alice is betting on her hat colour,
so she has 1 and 2, or 50%, chance of being right.
B: OK, well, that's a OK strategy.
J: It may seem that nothing better can be done. Why is that?
Because, anybody who doesn't pass, (and somebody has to not pass), is making a 50/50 guess.
So that almost seems like it's a proof that you can't do any better
B: Because there's no connection between the hats. There's no quantum entanglement here. Like,
like, the hats are all completely independent. Random.
J: The hats are all placed by a coin flip. So how could anything improve one half,
improve the probability of one person guessing.
There is an amazing strategy, the first time you see it, that gives you a chance three out of four of winning,
B: Huh! seventy-five percent
J: and that's 75%, and you can't do any better than that,
so you're not always going to win this game.
It's not like the, the two-person game. But three quarters seems pretty amazing.
But let's start with the strategy,
then I'm gonna do, of all things, draw a cube and work you through how you could have come up with that strategy.
Here's the strategy you're two friends. You don't know your hat colour.
If you see two hats of the same colour, you say the opposite.
May seem a little odd. That's what you say.
B: So if you see two blues, you say "I've got a red"
J: That's right. If you see two hats of opposite colour, one blue and one red, you pass.
I actually want to work you through how you might come up with this answer
Really there are two cases.
Let's think about what happens if all three hats are the same colour.
If all three hats are the same colour, for instance, everybody, like me, has a red hat on,
according to this strategy, we all say blue.
The only other case is two hats of one colour and the third hat of the other colour.
Let's think about what happens in that case.
Alice Bob and Charles have these colour hats.
What is going to happen?
Both Alice and Bob each see one hat of each colour, so they're gonna pass.
What about Charles?
Charles sees two hats of that colour and he announces the opposite colour, red.
So now that's a win. Now we have to ask the following interesting question:
First of all, how many ways are there to place the hats?
There's two choices for each of the three players,
two times two times two means there's eight ways to place those hats [2x2x2=8]
How many [cases] are there where the hats are all the same colour? Two! All blue, all red.
Those are the cases where you're going to fail. You have a 1/4 chance of failing.
The other six cases are all the two and one, and in that case you succeed.
So your winning strategy is to do this, and you win with probability [3/4] three fourths.
B: Easy peasy! J: Easy peasy.
B: I don't know what you're talking about cubes and stuff for, this is li--, this is j--, this is sorted.
J: Yeah, it's cute so far.
What I want to try to do is give you a feeling about how to think about it, and how you might come up with it.
Brady insists I draw pictures, so I'm going to draw a picture of a cube.
*laughter*
Um, here's a cube. Now, of course, your immediate reaction is: what does this have to do with anything?
Well, we agreed there are eight possible hat placements.
Being a mathematician, it's very hard for me to keep track of colours like blue and red.
All I can keep track of is zeros and ones.
So I'm going to label these with all possible triples of zeros and ones.
OK, and they're labeling the vertices of the cube and
and uh, Bradys being kind and not pointing out that I didn't label this one
*laughter*
And if you look at it carefully you'll see that any adjacent vertices
differ in one symbol.
fine. Here, 101 and 100
B: Is that the reason that the triple zero and the triple 1 are at opposite ends of the cube
J: Ye-- uh, they are as far apart.. you have to make three changes: 1, 2, 3.
Of course, you can make those in in many different ways,
but they have to be antipodal.
So why are we looking at this?
Well these correspond to the hash placements.
And now, suppose that you're Charles.
I claim if you see two blue hats and blue is 0 and red is 1,
you don't know whether you have red or blue.
In some sense, you are sitting on that edge of the cube and you want to know what to do.
Your choices are to name a hat colour or pass.
I'm gonna put a dot on the edges on which you should pass and an arrow so we know what Charles did
He said red.
I'm recording the strategy on this cube.
And here Alice says red.
Here, Bob says red.
Here, Charles sees two alike and therefore says the opposite.
So there's this funny picture that emerges.
What's happening here? OK, who is this? Well the coordinate that changes is Alice.
So Alice sees blue and red, so she knows that she's supposed to pass.
Six edges have labels and the other
Six are all passes
Somehow the magical secret of this is: there are two land mines
Here and here.
B: These are the times we lose the million dollars. J: These are the monochromatic hat placements
And we don't want to step on the landmine. So we predict we
aren't on a landmine.
And maybe rather than saying we're not trying to step on it,
what we're really saying is, if the landmine happens,
we all three want to get blown up at the same time.
The magic way we've converted these coin flips into a three quarters advantage
is to having all the correct answers in separate cases,
and the incorrect answers happen in two cases where everybody is incorrect.
So if we have more than three players the situation starts getting interesting. Let's consider four players.
Well, one thing we know we can do in that case is: in our strategy session Dave agrees to pass,
and Alice Bob and Charlie play this game,
and what that means is the probability that team of four with that strategy is three quarters.
Rather surprisingly they can't do any better than that.
If there are five people. There's a more complicated strategy that is a little better.
It's it's messier than this one is how I would describe it. Same with six people.
All of a sudden with seven people there's a nice strategy again.
It's not quite as easily described as this but it gives you the best possible probability of success.
If you work through what's happening here the property that makes this work
is that these two points are adjacent to every point on the cube.
Why is that necessary?
Well, if you're talking about strategies, in other words, labeling in this way,
it turns out that if you have a losing position you might as well have all arrows coming out from it.
And the next little thing, (I'm leaving this for you to figure out in your mind),
Every vertex either has to be in that losing set or adjacent to it.
OK, so now you can draw a four dimensional cube. Well, what would that be? What is a four dimensional cube?
Um. It would have vertices labeled by all strings of length
four symbols of zeros and one.
There are 16 vertices, and there's a lot of ways to draw that.
But it really doesn't matter whether or not you can visualize these higher, uh, dimensional cubes,
all you have to think about is these strings of zeros and ones.
So this makes gives you some way to at least think about the problem for any number of players.
B: What if everyone in the world was playing?
J: So, the magic numbers, like 7, are powers of two minus one
And for those, these magic sets are completely explicit,
and they're called Hamming single-error correcting codes.
They are perfect codes because they touch everything perfectly, without duplication.
B: Professor, does that mean when we get to 15 players and when we get to 31 players.
we see sudden jumps in the probability of winning?
J: Well, so when you come to 15 players, you can describe a very nice solution.
If we could find the best possible ones after that,
the probability would slowly increase until it 31 it would again be nice.
In fact, [of] the numbers right below 31 it's not known what the best number is.
So your probability of winning is only going to go up, but it's as elegant elegant solution
When N is a power of two minus one, [N=(2^x)-1]. at those places,
the probability is one over, well, N plus one. One over that power of two. [P=1/(N+1), or P=1/(x^2)]
So with 31 players, our chance of failing is 1 over 32, our chance of winning is 31 over 32.
If it was the population of the planet,
our chance of losing would be 1 over well, I don't, know four billion, let's say.
Its distinctive feature is that all the players have infinitely many hats,
each one of them equally likely to be blue or red.
So here is just the beginning of infinitely many hats. B: And that would go all the way
J: All the way up to the ceiling and through.
And now, um, maybe if they get smaller, it will only have finite height.
So now the game sounds pretty impossible,.
You have some number of players. Each players, of course, sees every...
Numberphile Subscribe