# Prisoners in Hats Puzzle: two variations

It's time for a maths puzzle!
And this is a variation on one of my favorite types of logic puzzles.
I actually came across this when I was in Norway last month.
I was over there to do some maths talks, I was at the university of Oslo,
where they gave me this fantastic T-shirt from their science festival, I'll show you the back at the end of the video.
And I was also in Trondheim, at the Norwegian University of Science and Technology. There, instead of a T-shirt, they gave me a maths puzzle.
The puzzle they gave me in Trondheim is a classic Prisoners in Hats puzzle.
In case you haven't seen these before, I'm gonna give you the standard Prisoners in Hats puzzle first,
if you have seen it before, you can just click here, to skip straight to the new variation.
Okay! Standard Prisoners in Hats puzzle, do have a go if you have not tried one of these before.
What happens is some evil mastermind has captured N people, we'll start with 6, just to make our life easy.
He has decided he wants to kill some, but not all of them.
He wants to make it reasonably fair, so the night before the possible execution he drops by all of them,
they're in the one cell together, and goes: "Hey guys, just so you know, tomorrow I'm gonna walk you all outside...
I'm gonna stand you in a line, all facing the same direction, possibly facing a wall.
You can't see any of the people behind you, but you can see all of the people in front of you.
Then I'm going to put hats on you. Each hat will be randomly either white or black.
...I don't know, I'll flip a coin or something to make sure, no one could possibly know if they were wearing a white or black hat.
And if you're wearing a hat and you can't see what color it is, but you can see all the hats in front of you, but that's all you know.
The people in front of you, have no idea what color your hat is, you have no idea what color the hats are behind you.
And you can't deduce anything, because for all you know, there could be 6 white hats
there could be 6 black hats, there could be any other combination of white and black hats.
The execution will go as follows:
I'm gonna start with the person at the back of the queue, they can see all of the hats in front of them,
but they have no idea if their hat is white or black. I'm gonna say: What color is your hat?
They are only allowed to say white or black, if they get it correct, they get to live and go,
if they get it incorrect, they are shot on sight or they fall through a trapdoor or something suitably appropriate.
So yeah, that's pretty much what's gonna happen to you all tomorrow. I'll leave you guys to have a chat overnight.
You can come up with any kind of plan you want, anyway you can try and work together to save as many people as possible, but just so you know,
I'm gonna put you in a randomized order tomorrow, so you don't know who's gonna be in front or who's gonna be at the back. Good luck."
So here you are, that's the puzzle. Can you find a strategy that the 6 prisoners can agree on to save as many people as possible?
You can actually save quite a few people. I'm not gonna give you the solution to that puzzle.
I'd like you to have a think about it, but I am gonna give you one clue to get you going:
It is definitely possible to save half of the people in this situation.
They could simply agree, whoever is at the back, they have no idea if they have a black or white hat.
So they look at the hat in front of them and they say that color, there's a 50/50 chance they will live or die,
but the person in front of them can hear what they say and go: "Oh there you go! I now know if I've got a white or black hat." They say the correct one.
Then the next person guesses, but they say the color of the person in front of them, and that way you can save every second person down the line,
and the people who are in the positions who don't get saved, each have a 50/50 chance.
So I guess on average you'll save 3 quarters of the people, but you're guaranteed to get at least half.
If you really really wanna know the solution to that puzzle or want to check if you're correct,
I have made a video explaining how it can be done but
I have left it unlisted on YouTube. you could only see it if you go direct to
the URL for that video and here is the code to find it, if you're prepared to
type that out. You can go to the video and you can see if you were right or not.
Here is the new variation that they gave me in Trondheim.
They said: "Right you've got a thousand prisoners in this jail.
The evil mastermind or whoever they are comes along the night before and says: "By the way,
have one thousand and one hats, that I'm gonna put on you tomorrow. They are numbered
one to a thousand and one. You may have noticed that is one more hat then there
are prisoners. I am going to completely randomly remove one of the hats, and then
take the remaining one thousand of them. I'm gonna shuffle them up and I'm gonna
randomly place them on all one thousand of you who are all facing forward and you
can only see the numbers in front of you and not the ones behind."
So effectively instead of having white and black hats like normal, this time you got a thousand people.
They can't see the number on their hat. They can't see any of the
hats behind them, but they can somehow see and read all of the hats in front of them.
As is tradition they have the evening to come up with a strategy.
They go out the next morning, they're put in a random ordering, the random hats are put on them,
and then they're asked from the person at the back on the way down:
"What number hat are you wearing?" If they get it correct, they get to live.
If they get it incorrect... They don't get to live. Now you could just try and
use the same strategy we had before where every second person says the
number of the hat directly in front of them thereby saving that person.
Well this evil mastermind has seen it all before and says: "Oh by the way guys,
extra rule for those of you who've seen this sort of scenario before. You're not
allowed to say a number which is already been said. So I'm gonna start at the back, I'm
gonna say what number is on your hat, if you guess it correctly you live, if you
guess it incorrectly you die. You cannot say a number which is already been used."
So that's the puzzle, and I quite liked it because it was a new variation
on quite a standard genre of puzzle. On top of that it led to some fantastic
debates and almost arguments. I was given this puzzle at the Trondheim maths jam.
for those of you who haven't come across maths jams before, on the second last Tuesday of the month
people get together in pubs and bars and cafes all around the world and they do maths while drinking.
It's great fun! I started in London many years ago and it
spread all across the globe and the great thing is, wherever I am, on holidays
or for work, if I'm somewhere in the world on the second last Tuesday of the month,
I can find some people to go and hang out with and do some mathematics.
If you wanna find your local maths jam, simply go to mathsjam.com, there you are.
Of course, if you're in America and you'd rather say "math jam", that's fine, I'm bilingual.
I can go with math then just go to "math-jam.com". Yes we're at the Trondheim maths jam.
fork in the solution, because I thought I'd come up with a strategy, where you can
definitely save everyone, but two people. Or you're guaranteed to save everyone but two.
And there's a chance you might save those two but it's certainly not guaranteed.
But then someone said: "But hang on, what if you don't know if people get the answer correct or not?"
And so we decided as a bonus round can you solve the same puzzle,
but when someone says a number behind you, so you hear the number they say,
you then don't hear they were right or not. So that person is then taken away and
either disposed of, or released. And in that situation I'm pretty sure you can
guarantee saving everyone, except for three people. If anyone thinks they can
do better than that please do let me know. If you think you've got a solution
as always put it in the comments underneath. I wanna see a nice civil
conversation, you generally serve me proud, my fantastic YouTube watching community.
Every so often someone insists on going: "Uhhh this is obvious."
Yes it's obvious if you know the solution and some of you will have seen these puzzles before.
I wanna see you all playing fairly and I wanna see some nice educated edifying conversations.
Oh yeah, and the T-shirt. I promised to show you the back of the T-shirt. Right, lemme just get this off.
Okay so you can see there's the logo from their science
festival over there, and if I very very carefully swing this around you can
see there's some of the back and there is more of it. Right, so look at all that cool
mathematics. You got Pascal's triangle. There's a Feynman diagram. There's even some Fermat going on.
What a fantastic T-shirt. So do be sure to check all of that out and of course as well as the T-shirt,
do check out mathsjam.com or math-jam.com!