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.