You walk alone into a room to find a chessboard.

Each of the 64 squares has a coin sitting on top of it.

Backing up, this is going to be one of those classic prisoner puzzles, where a strangely

math-obsessed warden offers you and a fellow inmate a chance for freedom, but only if you

can solve some elaborate scheme they’ve laid out.

In this case, that warden has carefully turned over the coins to be heads or tails according

to whatever pattern they want, and they then show you a key, and put it inside one of the

chessboard squares [each square is a secret compartment or something like that].

So you know where the key is, and your goal is to get your fellow prisoner to also know

where the key is, but the only thing you’re allowed to do before leaving the room is turn

over one, and only one, of these coins.

At that point, you walk out, your fellow prisoner walks in, and with no information other than

the set of heads and tails they’re looking at, which you’ve barely tweaked, they’re

supposed to deduce where the key is hidden, potentially winning freedom for both of you.

You can strategize ahead of time, but you won’t know what the specific layout of heads

and tails will be.

Moreover, the warden can listen in to your strategy and do their best to thwart it with

some adversarial arrangement of the coins and the key.

So I first heard about this puzzle over during dinner conversation at a wedding actually,

and it just totally sucked me in.

I remember the drive home was, maybe, 3 hours, and I think my mind was on flipping coins

and encoding states that whole time.

But the puzzle sticks with you, even after solving it, I fell into these two surprisingly

interesting rabbit holes.

One was to prove this challenge is impossible if you vary the setup a little bit, for example

if the chessboard was 6x6, or if you removed one of its squares.

To give you some sense for where that rabbit hole leads, this video will end with an especially

pleasing way to paint the corners of a 4-dimensional cube.

The other rabbit hole was to work out how closely you could connect the solution of

this puzzle with error-correction, which is a super important topic in computer science

and information theory.

The idea is that when computers send and store data, the messiness of the real world inevitably

flips a bit now and then, which completely changes how that data is read, so error correcting

codes are a way to add a shockingly small amount of added information to a message that

makes it possible for a receiver to identify that there was an error, and more impressively

how to fix it.

It turns out the intuitions for solving this puzzle are basically identical to the intuitions

behind these things called “Hamming Codes”, which are one of the earliest examples of

highly efficient error correction.

Which is all to say that time spent mulling over this problem is not as useless as you

might think.

We actually won’t talk about the solution here; instead I filmed a video all about that

over on StandupMaths with Matt Parker, who many of you may recognize from his combined

YouTube, stand up and book fame.

We talk about our thought process in solving it, and it’s good fun because there are

multiple ways of looking at it.

Instead what I want to do here is take a more global view of all possible strategies for

this puzzle, and bring you with me down that first rabbit hole of proving why certain variations

must always leave room for the warden to thwart you, no matter how clever you are.

The proof itself involves one of those satisfying moments where a shift in perspective reveals

a solution, and the whole context leading to it is a nice chance to practice reasoning

about higher dimensional objects as a way to draw conclusions about information and

data.

Plus, it’ll do more to help you appreciate the solution to the original puzzle when you

can see how it is, in a sense, almost impossible.

We want some kind of visualization for what it even means to solve this puzzle.

To build up to the general case, let’s knock things down to the simplest possible case

we can that still has any kind of meaning to it: Two squares, two coins, two possibilities

for where the key is.

One way you could solve this is to simply let the second coin communicate where the

key is; if it’s tails, it means the key is in the left square, and if its heads, the

key is in the right square.

So if it needs to be changed, you can flip it, and if it doesn’t, just flip the other

coin.

First thing’s first, let’s stop thinking of these as heads and tails, and start thinking

about 1’s and 0’s; much easier to do math with.

Then you can think of these pairs of coins as a set of coordinates, where the four possible

states now all sit on the corners of a unit square.

This might feel like a silly thing to do when we already know how to solve this case, but

it’s a good warmup for turning the larger cases into geometry.

Notice, flipping one of the coins moves you along an edge of this square, since it’s

only changing one coordinate.

The strategy of letting that second coin encode the key location can be drawn by associating

those bottom two corners, where the y-coordinate is 0, with the “key is under square 0”

state, and the top two corners with the “key is under square 1” state.

Think about what it means for our solution to work: No matter where you start, if you’re

forced to take a step along an edge, forced to flip one coin, you can always guarantee

you end up in whichever of these two regions you want.

Now the question is, what does all this look like for bigger chess boards?

The next simplest case would be three squares, three coins, three possibilities for where

the key is.

This gives 8 possible states the coins could be in, and playing the same game of interpreting

these states as coordinates, it now brings us to 3d space, with each state sitting at

the corner of a unit cube.

The usefulness of a picture like this is that it gives a very vivid meaning to turning over

one of the coins.

Each flip is a step along one edge of the cube.

Now, what would it mean for you and your fellow inmate to have a strategy for this puzzle?

Whenever prisoner 2 walks into the room, they need to be able to associate the state they’re

looking at, 3 bits, essentially, with one of three possible squares.

We’re already thinking very visually, so let’s think of those three possibilities

as colors, red for square 0, green for square 1, blue for square 2.

In this conception, coming up with a strategy, any strategy, is the same thing as coloring

each of the 8 corners of a cube either red, green or blue.

For example, coloring the whole cube red would – well, I don’t know if you’d call this

a strategy exactly – it would correspond to always guessing that the key is in square

0.

If instead you let the sum of the first two coins encode the key location, the cube would

look like this.

What’s kind of fun is that we can count how many total strategies exist.

With three choices for the color of each vertex, we get 3^8.

Or, if you’re comfortable letting your mind stray to the thought of painting a 64-dimensional

cube, you can think about the sense in which there are 64^(2^64) total possible strategies.

This is the size of the haystack when we’re looking for a needle.

Another attempt might look like taking 0*coin0 plus 1*coin1 + 2*coin2, and reduce it mod

3 if needed; over on Stand-up Maths Matt and I talk about trying a version of this for

the 64 square case, why it works decently well for a random arrangement of coins, and

why its ultimately doomed.

From our view here, it’s just one more way to color the cube, but let’s take a moment

to walk through some of the corners.

Let’s say you walk in and all three coins are tails, so it’s like you’re starting

at the corner (0,0,0).

Flipping coin 0 doesn’t change the sum, so it takes you to another red corner.

Flipping coin 1 increases the sum to 1, so that takes you to a green corner.

And flipping coin 2 takes you up to 2, bringing you to a blue corner.

The fact that you have access to whatever color you want is a reflection of the fact

that this strategy will always win if that’s the corner you start on.

On the other hand, let’s say you started at (0,1,0).

Flipping coin 0 takes you to another green corner, but flipping either coin 1 or coin

2 will take you to a red corner, and there’s no way to get to a blue corner.

Basically what’s happening here is that you have the options to subtract 1, or add

2, and working mod 3 those are actually the same operation.

But even without thinking about sums mod 3 or anything like that, you can see this in

our picture manifested as a corner with two neighbors of the same color.

If you don’t have a birds eye view of all possible strategies, when you find that any

specific one that you try doesn’t work, you’re kind just left to wonder if maybe

there’s some sneaky clever trick you just haven’t thought of.

But thinking of colors on the cube, you’re naturally led to an interesting combinatorial

question: Is there a way to color the cube so that the three neighbors of any given vertex

will always represent red, green and blue.

Maybe it seems bizarre, even convoluted to go from a puzzle with chess boards and coins

to talking about painting the corners of a cube, but this is actually a much more natural

step than you might expect.

I’ve talked with a lot of people about this puzzle, and what I love is that many of the

experienced problem solvers immediately jump, unprompted, to talking about coloring corners

of a cube, as if it’s a kind of de facto natural language for this puzzle.

And it really is.

Thinking about binary strings as vertices of a high dimensional cube, with bit flips

corresponding to edges, actually comes up a lot, especially in coding theory, like the

error correction stuff I referenced earlier.

What’s more, you very often hear mathematicians talk about coloring things as a way to describe

partitioning them into different sets.

If you’ve ever heard of the hilariously enormous number Graham’s constant, for example,

the problem where that came up was phrased in terms of assigning to colors to a high

dimensional cube.

Though in that case, colors were given to pairs of vertices instead of individual ones.

The point is, analyzing how to color a potentially high dimensional cube is a more transferable

skill than you might think.

So to our question, can you make it so that every vertex has a red, green and blue neighbor?

Remember, this is the same thing as having an encoding for key locations so that you’re

always one flip away from communicating whichever key location you want.

It would actually be enlightening if you paused the video and tried this, it’s like a weird

3-dimensional sudoku.

Very similar to a sudoku, in fact, in the sense that you want certain subsets to be

filled with all 3 possible states.

You might start painting one corner an arbitrary color, say red, then painting its three neighbors

red, green and blue.

It’s red neighbor needs to be adjacent to a green and a blue, so you can draw that in.

But at least how I’ve done it here, you’re stuck, unable to choose the right colors for

the next two; can you see why?

What I’d like to share is a lovely little argument that explains not only why this can

never work in three dimensions, but why it can’t work in any dimension that’s not

a power of 2.

The idea is that the symmetry in the property we want implies that there should be an equal

number of red, green and blue vertices.

But that would mean 8/3 of each, which is not possible.

Before I go on, pause to see if you can think of a way to solidify that intuition; it’s

a fun exercise in turning a vague instinct into a solid proof.

One way is to imagine a process where you go through each corner, and count how many

of its neighbors are a particular color, say red.

So each step here we’re looking at the three neighbors of a given vertex, counting up the

red ones, and adding that to a total tally.

For this coloring that count came out to be 12, but if we had the property we wanted,

every corner would have exactly 1 red neighbor, so you’d get 8.

On the other hand, every red corner will be counted exactly 3 times, once for each instance

when it’s somebody’s neighbor, so that final tally must be 3 times the total number

of red corners.

So it’s simple, just find a coloring where 8/3’s of the corners are red!

Isn’t that nice?

Counting how many times some corner has a red neighbor is the same as counting how many

times a red corner has some neighbor, and that’s enough to get us a contradiction.

What’s also nice about this argument is that it immediately generalizes to higher

dimensions.

Think about solving the chessboard puzzle with n squares; again, the puzzle is to associate

each arrangement of coins with some state, some key location, so that the arrangements

you can get to with one flip represent all the possible states; any possible key location.

Even if we can’t visualize most high dimensional cubes we can still talk about vertices of

such a cube and their neighbors as a way to describe bit strings and those which sit one

bit flip away.

There are really just two relevant facts: Standing on one of these vertices, you have

n different neighbors, and the total number of vertices is 2^n, one for each bit string

of length n.

You can now play the same game we did in 3 dimensions, going through each corner and

counting its red neighbors.

If it’s possible to do the coloring you want, this sum will be 2^n, one for each vertex.

On the other hand, since each red corner is counted once for each of its neighbors, that

count should be n times the total number of red corners.

Since the left-hand side is a power of 2, the right hand side needs to be a power of

2, which can only ever work if n itself is some smaller power of 2.

For example in four dimensions, or 64 dimensions, there is no contradiction; it’s at least

possible to evenly divide the vertices among the colors.

To be clear, that’s not the same as saying there necessarily is a solution for powers

of two, just that it can’t be ruled out yet.

This, to me, is completely delightful.

Just by imagining coloring the corners of a cube and counting how many are of each color,

you can conclude that no possible strategy, no matter how clever you are, can work in

all cases for this chessboard puzzle if the number of squares is not a power of 2.

So if we knocked off a square, or if the board was 6x6 instead of 8x8, the task is hopeless.

It also means that the solution to the chessboard puzzle, which I’ll point you to in a moment,

can be viewed as a particularly symmetric way to color the corners of a high dimensional

cube in a manner disallowed in most dimensions.

If you’re curious, I couldn’t resist showing this explicitly for a 4-dimensional cube.

In the same way that you can take a 3d cube and project it down into two-dimensions with

a little perspective to show the same graph structure of vertices and edges on a flat

plane, we can do the same projecting a 4d cube into 3d space and still get a full view

of how all the vertices and edges are connected.

If you wanted to try your hand at a sort of 4-dimensional cousin of a sudoku, you could

pause and see if you can figure out how to color these vertices in such a way that the

four neighbors of any vertex represent all four colors.

Using essentially the same computation that solves the chessboard puzzle for the four-square

case, I can get the computer to draw it out for us.

At this point, I’d like you to hop over to StandupMaths where Matt and I show how

this solution works.

If any of you are somehow not yet familiar with StandupMaths, it’s one of my favorite

channels, run by one of my all-time favorite people, so please do immediately subscribe

once you land over there.

You’re in for quite a few delights with everything else the channel has to offer.

Before explaining it he and I just show what it looks like for us to actually perform the

solution, and as we do I really want you to try thinking of the solution yourself and

predict what it is we’re doing before we tell you.

And if you’re curious about the connection with Hamming codes and error correction, I’m

certainly game to make a video on that, let me know in the comments.

I’ve been told that not everyone is as interested in symmetrical ways to paint a 64-dimensional

cube as I am, but reliable data transmission?

I think we can all agree that’s universally sexy.