Harder hat problem

The Problem:

Setup: There are n prisoners standing in a circle so that everyone can see each other's hats but not their own. An executioner will use a fair coin toss to put a black or white hat on every prisoner. He will then proceed clockwise around the circle and ask each prisoner if they want to guess their hat color. Prisoners may guess or choose to pass, but at least one prisoner must guess. If ANY prisoner guesses their hat color wrong, everyone will be killed.

Question: What strategy can the prisoners use to maximize their chances of living?

The "Default" Solution

The default solution is to have everyone pass until the last prisoner who must guess. They have a 50% chance of being right. Not so hot.

Our First Attempt: 75% chance of getting saved

If the 1st prisoner says "pass", it means the 2nd prisoner's hat is black. They can guess correctly, and everyone else will pass.

Unfortunately, if the 2nd prisoner's hat is white, the 1st prisoner will have to guess his own hat color with 50% chance of success.

Therefore, there's a 75% chance overall that this strategy will be effective.

Our Final Solution

My wife came up with a solution that gives the prisoners a 1 - 1/2^n chance of being saved. Here it is:

Rule: If there are any black hats ahead of you in the questioning, pass. If there aren't, guess black.

This strategy will fail if everyone has a white hat. In that case, the first prisoner will incorrectly guess black and everyone dies. But it works for all the other possibilities. Here's why:

There's always going to be a "last" black hat in the questioning order (so long as there's a black hat at all). Using the strategy, everyone before this person will pass. Since this person is the last black hat, they can only see white hats ahead of them, so they will correctly guess "black".

With n people, there are 2^n possible assignments of hat color. Only one of these (all white hats) will fail with our strategy. Therefore, the chances of dying are 1/2^n. So the chances of living are 1 - 1/2^n.

Prisoners with k-colors of hat

The Problem:

Setup: This is exactly the same setup as the prisoners-with-hats problem, only now there are more than 2 possible hat colors.

Here (again) is the setup: There are n prisoners standing in a line, facing front. The executioner starts at the back of the line and randomly gives each prisoner one of k colors of hat to put on. No one can see their own hat color or the hat colors of anyone behind them, but they can see all the hats of the people in front of them. The executioner will walk down the line starting from the back and ask each prisoner to guess their own hat color. Each prisoner can only say one of the possible hat colors. If they guess right, they will be set free at the end. If they guess wrong, they will be killed at the end. The prisoners realize that they can try to use their guesses to communicate information to the prisoners in front of them that might help the others guess their own hat colors right.

Question: What strategy can the prisoners use to save as many of themselves as possible? How many can we expect to save?

Solution

Surprisingly, it doesn't matter how many colors of hat there are. It's still possible to guarantee that all the prisoners but the first get saved. The solution is a clean (though maybe not obvious) generalization of the solution to the 2-color hat problem.

First, number your colors 0 to (k-1).

The 1st prisoner will figure out what (p2 + p3 + ... + pn) mod k is. Since it's guaranteed to be a number between 0 and k-1, he can use his guess to communicate this number to the other prisoners.

Now prisoner 2 can figure out his own hat color as follows. He can calculate (p3 + p4 + ... + pn) mod k from what he sees. The difference between this number and what prisoner 1 told him must be the value of his own hat color, allowing him to guess correctly.

Prisoner 3 can assume prisoner 2 was correct in his guess, and can apply similar reasoning.

Prisoners with hats

The Problem:

Setup: There are n prisoners standing in a line, facing front. The executioner starts at the back of the line and randomly gives each prisoner a black or a white hat to put on. No one can see their own hat color or the hat colors of anyone behind them, but they can see all the hats of the people in front of them. The executioner will walk down the line starting from the back and ask each prisoner to guess their own hat color. Each prisoner can only say "black" or "white". If they guess right, they will be set free at the end. If they guess wrong, they will be killed at the end. The prisoners realize that by saying "white" or "black" they can try and communicate information to the prisoners in front of them that might help the others guess their own hat colors right.

Question: What strategy can the prisoners use to save as many of themselves as possible? How many can we expect to save?

* * *

(Too) Easy Solution ("Cheater Solution")

You can easily save everyone except the first person like this: No matter what a prisoner says, if they say it in a high, squeeky voice, that tells the next prisoner their hat is white. If they say it in a deep, low voice, that tells the next prisoner their hat is black. Now everyone (except the first person who still has to guess) has been told their hat color by the tone-of-voice of the previous prisoner.

This was the solution one of my students thought of. It clearly works, and we shouldn't turn up our noses at a creative solution that works. But the puzzle is deeper then that, and will yield interesting things if we disallow this type of solution.

So, let's say that there is no communicating in sneaky other ways: each prisoner only hears one bit of information--"black" or "white" with no additional information.

First Attempt

Since we always start with the most obvious thing we can think of, here it was!

Rule: Each person should say whatever hat color the next person has on.

How does this rule fare? The first person helps the 2nd person go free, and has a 50% chance of being right about themselves. But since the second person will say their own hat color (to go free), they can't also tell the next person what their hat color is. Since the 3rd person can't be helped, they'll help the 4th person go free by telling them their hat color, and only have a 50% chance of being right about themselves. In general, every odd numbered person will say the hat-color of the next person in line, with a 50% chance of being right about themselves. Every even numbered person will be told their hat color by the prisoner behind, and so will have a 100% chance of survival. All together we should expect to save about three quarters of all the prisoners with this strategy.

This seemed ok, be we thought we should be able to do better.

What Makes it Hard

The problem with our 1st solution seems to be a problem with *any* solution. Whenever a prisoner knows their own hat color, they have to say it to go free; but in that case they can't also be communicating information to the other prisoners since they can't base what they say on what they see--that have no choice about what to say if they want to go free.

Solution

This solution can guarantee that everyone is saved except the first prisoner who has a 50% chance.

Rule: 1st prisoner says 'black' if he can see an odd number of black hats. He says 'white' if he can see an even number of black hats. The other prisoners deduce their own hat colors, and say them.

Here's how this works. The 1st prisoner and the 2nd prisoner can both see all the others. Whether or not a number is even or odd is called its parity. If the 1st prisoner and 2nd prisoner see a different parity of black hats, the 2nd prisoner knows that his hat must be black. If the 2nd prisoner's hat were white, then he and he 1st prisoner would see the same number of black hats.

Therefore, the 2nd prisoner will be able to say his own hat color correctly by checking if the parity of black hats he sees is the same as what the 1st prisoner said or not. The 3rd prisoner heard what the 1st prisoner said about the hat parity, and knows that the 2nd prisoner said the true color of his own hat. With this information the 3rd prisoner can deduce his hat color in the same way the 2nd prisoner did, and say it correctly. This reasoning continues down the line to the very last prisoner and they are all saved.

This solution gets around what seemed to make the problem hard because the parity of black hats seen by the first player depends on the state of all the other hats. When each prisoner says their own hat color correctly, they're also giving information to the later prisoners: namely, what their hat colors actually are. The later prisoners use this information, combined with what the first prisoner said, to figure out their own hat color.

A Different Way To Look At It

Here's a different way to look at it. The way each prisoner figures out his own hat color is by solving a simple equation of modular arithmetic.

First, let's give all our colors numbers.

white is 0

black is 1

Lets record each prisoner's hat-color in a variable. The 1st prisoner is p1, the 2nd prisoner is p2, and so on.

The 1st prisoner says the parity of the number: p2 + p3 + p4 + ... + pn

Another way to describe the parity of a number is as its remainder when divided by 2. If you divide a number by 2 and get remainder 0, you know the number was even. If you divide a number by 2 and get remainder 1, you know the number was odd.

The conventional way to write the remainder of a number S when divided by 2 is: S mod 2

Just to make sure you understand. Say W = 53. What's W mod 4?

It's the remainder left over when you divide W by 4. Since W = 53, W mod 4 is 1.

With that in mind:

Let's call the parity of black hats the 1st prisoner can see, S. In other words:

S = (p2 + p3 + p4 + ... + pn) mod 2

Let's call the parity of black hats the 2nd prisoner can see, T. In other words:

T = (p3 + p4 + ... + pn) mod 2

Player 2 knows that:

The parity of the hats player 1 sees = his own hat parity + the parity of the hats he sees

In other words:

S = (p2 + T) mod 2

The only thing he doesn't know in this equation is p2--his own hat color. He can figure it out by solving the equation.

This seems more complicated, but is the key to generalizing the solution later.

Private Coast

The Problem

Setup: There is a cluster of n perfectly circular, flat islands in the Pacific, each with the same radius of R. A point on the coast of an island is private if it cannot be seen from the coast of any other island. (We're assuming they're forested islands so you can't see across the land of an island to the coast on the other side). It's easy to see that if there are 2 islands, then exactly half of the coast-line of each island is private, so the total private coast-line of both islands is 2πR.

Question: What's the maximum total private coast-line possible with 10 islands? How must they be arranged?

Experimentation:

Our first step, as usual, was to play about with it. Since the 2 island case is obvious, we tinkered with 3 islands, starting with the simplest two configurations we could think of: All in a line, and as the corners of an equilateral triangle.

Clearly when all 3 islands are arranged in a line, there is no private coast on the middle island, and half a circle's worth on the ends. So, again, the total private coast is a full circle's worth: 2πR.

What about the equilateral triangle? Here it looks like the inward facing parts of the islands are not private, but the outward facing parts are.

The way I like to imagine which parts are private and which aren't, is I imagine little people (the red dots) standing at different places with binoculars, trying to see everywhere they can. Something like this:

It looks like the "outside" red dots are able to see the furthest around to the back side. But even so, no one can see the bold shaded section...and that looks like about 1/3 of the circle. Since the whole arrangement is symmetric, the other two islands will also have the same amount of private coast. It's looking like ~1/3 + ~1/3 + ~1/3 = ~1 whole circle's worth of private coast-line again! Can't be too sure yet, but that's what it's starting to look like.

"Ok", we thought, but maybe those answers looked so nice because the shapes were so simple. What if we make a triangle that's not so nice.....

If I imagine taking the private parts in bold and putting them together, they kind of look like they'll make a full circle of private coastline! This led us to make a...

Conjecture: No matter how you arrange 3 islands, there will always be 1 full circle's worth of private coastline.

Kind of seemed true, but how could we prove it? Imagine drawing a triangle connecting the centers of the islands, and another that's just tangent to the edges. Actually, you don't need to: here it is!

Let's see. I want to know how much private coastline there is. In the picture, that's however much coast is in the arcs of b1 + b2 + b3.

What I know already is that a1 + a2 + a3 = 180, because they're the angles of a triangle.

So, I need a way to connect what I know with what I want to know. I need to find a relationship between the a's and the b's.

Looking at the upper left-hand circle, we know all the angles must sum to 360, because they're in a circle. Since two of them are 90 degree angles, that means that a1 + b1 = 180. Really, that's true of all 3 circles.

a1 + b1 = 180

a2 + b2 = 180

a3 + b3 = 180

Since we know (a1 + a2 + a3), and we want to know (b1 + b2 + b3), let's add the 3 equations above together to get...

a1 + b1 + a2 + b2 + a3 + b3 = 180 + 180 + 180

Re-grouping a bit, we get...

(a1 + a2 + a3) + (b1 + b2 + b3) = 540

And since (a1 + a2 + a3) = 180, we get...

180 + (b1 + b2 + b3) = 540 or b1 + b2 + b3 = 360. A full circle!

So that proves it. But that was only for 3 islands, and the original problem asks about 10.

Feeling optimistic we made another...

Conjecture: Any number of islands in any arrangement will always have exactly one full circle's worth of private coast-line.

The same argument as before extends easily to larger numbers of islands that are the vertices of some larger convex polygon. For example...

Since an n-gon is made up of n-2 triangles (here, the 5-gon is made of 3 triangles), all the internal angles must sum to 180(n-2). That gives us...

a1 + a2 + ... + an = 180(n-2)

And the same argument with the circle gives us for all a's and b's that a + b = 180.

This time let's re-write the equation as a = 180 - b, and substitute in for each of the a's in the first equation.

(180 - b1) + (180 - b2) + ... + (180 - bn) = 180n - 360

How many 180's on the left side? n. Re-ordering a bit, we get...

180n - (b1 + b2 + ... + bn) = 180n - 360

Cancel the 180n on both sides, multiply by -1 and you end with...

b1 + b2 + ... + bn = 360 The sum of all the private areas is a full circle's worth!

But wait. This only proves it for configurations where the islands form the verticies of convex polygons! What about something like this, where there are islands scattered around?

If an island lies inside the convex polygon created by the centers of the others (inside their "convex hull"), then it clearly has no private coast at all, so we can safely ignore it in our calculation. Now the problem is only about the islands that are the verticies of the polygon--but that's exactly the situation we've already proven for. So that, finally, does it! Any situation that isn't of the kind our proof was for easily reduces to another one that our proof covers.

Solution: Any number of radius R islands arranged in any arrangement at all will have exactly 2πR distance of private coast-line!

100 Prisoners

The Problem:

Setup: 100 prisoners are being transported to a very special facility. While there, they will be kept in solitary confinement in 100 completely isolated rooms. There is, however, a "day room". Every morning, one of the prisoners is selected at random and spends the day in the day room. The only lasting effect a prisoner can have on the room is deciding whether to leave its single lightbulb on or off. The next day, whichever prisoner enters will see the light in whatever state the previous prisoner left it.

If a prisoner in the day room declares "We've all been in here by now!", then, if he's right and all 100 prisoners have been in the day room, everyone is set free. If he's wrong, however, everyone is killed.

The prisoners make an agreement and a plan. They agree that no one will say the magic words until they're *sure* that everyone has really been in the day room. But how can any prisoner ever be sure? They devise a plan to communicate using the single light bulb, so that way they can be sure that eventually someone will know.

The questions: What was a plan that would work? What's the plan that will get them all free in the shortest expected time?

Thoughts about the Solution:

Since we're slow thinkers, it took a good 15 minutes before anyone thought of any approach that would work. As it happened, I thought up the first idea, and although it "works", it would take several thousand years on average before anyone was sure.

Solution #1: Since this is prison, let's give all the prisoners numbers for easier accounting. We'll label them 1-100. Now, let's say all the prisoners are keeping track of how many days it has been since they reached the prison. This gives each prisoner a special day. Day 1, is prisoner 1's day. Day 58, is prisoner 58's special day. When we reach 100, we start over again. So day 1023, is prisoner 23's special day again.

Plan: A prisoner can only turn on his light if he enters the day room on his special day. Whoever enters the room the next day now knows exactly which prisoner was in the room the day before. He will then turn out the light again (if its not his special day). Eventually, some single prisoner will randomly be in the day room the day after all the other prisoners on their special days. Then he'll know everyone has been in the room, can say the magic words, and get everyone released.

You can see why this strategy will take a long time.

An improvement: Special windows

If I remember right, this improvement is due to our friend Nathan. His idea was: one special day is too short a time window to get randomly chosen to be in the room, and even after you're chosen, only 1 person will ever know what happened--the person who's in the room the next day.

So instead of one day, let's give everyone more days--a special "window" of days. Say, 10, for example. So now prisoner 1's special window are days 1-10. Prisoner 2's special window are days 11-20. Prisoner 58's special window are days 571-580.

Modified Rule: If a prisoner enters the day room any time in his special window, he turns on the light.

Before, only the prisoner on the day after would ever know what happened, because he would immediately turn off the light. Now the light stays on until the window ends--so everyone else who enters will know! If prisoner 1 enters the room on day 3, all the prisoners for the next 7 days will know that prisoner 1 was in the room!

Another nice feature of this idea, is that we have a parameter: the length of the window. If the window is length 1, then the solution is the same as before. A window of length 100 is probably too long because it would take 10,000 days just to make it through prisoner 100's special window! What's the optimal length for a window? We're not sure, but it's nice that you can systematically vary the window length to try and find out.

Another improvement: Rebroadcasting

This improvement, due to my wife Jen, is really a revolution. A problem with the old scheme is that if prisoner 72 knows that almost all the other prisoners have been in the room, he has no way of communicating that information to anyone else! He has to keep waiting to see the rest, or hope someone else does first. So let's modify the rule from the previous solution:

Modified Rule: You may turn on the light in prisoner n's special window of days if you are prisoner n, or if you know prisoner n has already been in the room.

This will let prisoner 72 act as a substitute or a proxy for the prisoners he knows have been in already so he can communicate that information!

Another improvement: Special "multi-prisoner" windows

Here is another idea (also Jen's) to allow faster communication about what a prisoner has seen. Let's say prisoner 72 knows that prisoners 1-50 have been in already. Even with re-broadcasting, he can't really communicate all this knowledge quickly through the single light. So let's add two more "special window" that come after prisoner 100's window before we loop back to prisoner 1's window again. The first window is the "prisoner 1-50 window" and the second one is "prisoner 51-100 window". Here's the rule for the new special windows:

New Rule: You may only turn on the light in a special window if you know all the prisoners represented by that window have already been in the room.

This means that if prisoner 72 enters the room during the first special window, he can turn on the light, since he knows prisoners 1-50 are covered. Then everyone else who enters in the special window will see the light on, and also instantly know that prisoners 1-50 have been in the room.

A different way to think about this is that it's a way of breaking the problem into smaller pieces. Rather than the 100-prisoner problem, you just have to solve 2 50-prisoner problems.

Notice that this improvement also contains a parameter: What size grouping of prisoners should each special window represent? Is it better to have 2 special window, each representing 50 prisoners? Or is it better to have 10 special windows, each representing 10 prisoners?

Totally Different Idea

The previous solution has become rather elaborate. Here's a different, very elegant solution (due to our friend I-Heng):

Plan: Designate 1 prisoner the "collector". Only he may turn off the light in the room. Every other prisoner will turn on the light exactly once. Once the collector has turned the light off 99 times, he may safely conclude everyone has been in the room.

Clean, eh?

Concluding Thoughts

Clearly we've found lots of different types of solution. Which is the best? Which gets the prisoners out in the least expected time? We've had difficulty answering this question, because some of our improvements to the original idea made it very hard for us to figure out what the expected time to release is! There has been some discussion of writing computer simulations of the strategies and running millions of trials to find out, but no one has really wanted to do this yet.

If you've thought of other ideas or have done expected time-to-release calculations, we'd love to know!

Hello Problem Blog!

It occurred to me that it might be nice to record my thought processes on some of the math puzzles I'm always thinking about. Like a sort of math show-and-tell.....so.....here we go!