The impossible chessboard puzzle
3.05M subscribers
SUBSCRIBED
An information puzzle with an interesting twist Solution on Stand-up Maths:
Paid for by viewers, like you: https://3b1b.co/chess-thanksHome page: https://www.3blue1brown.com-----------------
Introductio
Visualizing the two-square cas
Visualizing the three-square cas
Proof that it's impossibl
Explicit painting of the hypercube ------------------ Thanks to everyone who endured me probing them with this puzzle and provided helpful discussion, especially Cam Christensen, Matt Parker, and Mike Sklar. Mike, by the way, deserves credit for coming up with the particularly clean way to see that it's impossible when n is not a power of 2. These animations are largely made using manim, a scrappy open-source python library: https://github.com/3b1b/manimIf you want to check it out, I feel compelled to warn you that it's not the most well-documented tool, and it has many other quirks you might expect in a library someone wrote with only their own use in mind. Music by Vincent Rubinetti. Download the music on Bandcamp:https://vincerubinetti.bandcamp.com/a...Stream the music on Spotify:https://open.spotify.com/album/1dVyjw...If you want to contribute translated subtitles or to help review those that have already been made by others and need approval, you can click the gear icon in the video and go to subtitles/cc, then "add subtitles/cc". I really appreciate those who do this, as it helps make the lessons accessible to more people. ------------------ 3blue1brown is a channel about animating math, in all senses of the word animate. And you know the drill with YouTube, if you want to stay posted on new videos, subscribe: http://3b1b.co/subscribeVarious social media stuffs: Website: https://www.3blue1brown.comTwitter: https://twitter.com/3blue1brownReddit: https://www.reddit.com/r/3blue1brownInstagram: https://www.instagram.com/3blue1brown...Patreon: https://patreon.com/3blue1brownFacebook: https://www.facebook.com/3blue1brown
Caption author (Korean)
Caption author (Portuguese)
00:04
You walk alone into a room to find a chessboard.
00:07
Each of the 64 squares has a coin sitting on top of it.
00:11
Backing up, this is going to be one of those classic prisoner puzzles, where a strangely
00:15
math-obsessed warden offers you and a fellow inmate a chance for freedom, but only if you
00:21
can solve some elaborate scheme they’ve laid out.
00:23
In this case, that warden has carefully turned over the coins to be heads or tails according
00:28
to whatever pattern they want, and they then show you a key, and put it inside one of the
00:34
chessboard squares [each square is a secret compartment or something like that].
00:39
So you know where the key is, and your goal is to get your fellow prisoner to also know
00:44
where the key is, but the only thing you’re allowed to do before leaving the room is turn
00:49
over one, and only one, of these coins.
00:52
At that point, you walk out, your fellow prisoner walks in, and with no information other than
00:58
the set of heads and tails they’re looking at, which you’ve barely tweaked, they’re
01:03
supposed to deduce where the key is hidden, potentially winning freedom for both of you.
01:10
You can strategize ahead of time, but you won’t know what the specific layout of heads
01:15
and tails will be.
01:17
Moreover, the warden can listen in to your strategy and do their best to thwart it with
01:21
some adversarial arrangement of the coins and the key.
01:26
So I first heard about this puzzle over during dinner conversation at a wedding actually,
01:30
and it just totally sucked me in.
01:32
I remember the drive home was, maybe, 3 hours, and I think my mind was on flipping coins
01:38
and encoding states that whole time.
01:41
But the puzzle sticks with you, even after solving it, I fell into these two surprisingly
01:45
interesting rabbit holes.
01:47
One was to prove this challenge is impossible if you vary the setup a little bit, for example
01:53
if the chessboard was 6x6, or if you removed one of its squares.
01:56
To give you some sense for where that rabbit hole leads, this video will end with an especially
02:01
pleasing way to paint the corners of a 4-dimensional cube.
02:05
The other rabbit hole was to work out how closely you could connect the solution of
02:09
this puzzle with error-correction, which is a super important topic in computer science
02:14
and information theory.
02:16
The idea is that when computers send and store data, the messiness of the real world inevitably
02:21
flips a bit now and then, which completely changes how that data is read, so error correcting
02:27
codes are a way to add a shockingly small amount of added information to a message that
02:31
makes it possible for a receiver to identify that there was an error, and more impressively
02:37
how to fix it.
02:38
It turns out the intuitions for solving this puzzle are basically identical to the intuitions
02:44
behind these things called “Hamming Codes”, which are one of the earliest examples of
02:48
highly efficient error correction.
02:49
Which is all to say that time spent mulling over this problem is not as useless as you
02:54
might think.
02:55
We actually won’t talk about the solution here; instead I filmed a video all about that
03:00
over on StandupMaths with Matt Parker, who many of you may recognize from his combined
03:05
YouTube, stand up and book fame.
03:07
We talk about our thought process in solving it, and it’s good fun because there are
03:11
multiple ways of looking at it.
03:13
Instead what I want to do here is take a more global view of all possible strategies for
03:18
this puzzle, and bring you with me down that first rabbit hole of proving why certain variations
03:23
must always leave room for the warden to thwart you, no matter how clever you are.
03:29
The proof itself involves one of those satisfying moments where a shift in perspective reveals
03:33
a solution, and the whole context leading to it is a nice chance to practice reasoning
03:38
about higher dimensional objects as a way to draw conclusions about information and
03:42
data.
03:43
Plus, it’ll do more to help you appreciate the solution to the original puzzle when you
03:48
can see how it is, in a sense, almost impossible.
03:59
We want some kind of visualization for what it even means to solve this puzzle.
04:04
To build up to the general case, let’s knock things down to the simplest possible case
04:08
we can that still has any kind of meaning to it: Two squares, two coins, two possibilities
04:14
for where the key is.
04:17
One way you could solve this is to simply let the second coin communicate where the
04:20
key is; if it’s tails, it means the key is in the left square, and if its heads, the
04:25
key is in the right square.
04:27
So if it needs to be changed, you can flip it, and if it doesn’t, just flip the other
04:34
coin.
04:36
First thing’s first, let’s stop thinking of these as heads and tails, and start thinking
04:39
about 1’s and 0’s; much easier to do math with.
04:44
Then you can think of these pairs of coins as a set of coordinates, where the four possible
04:49
states now all sit on the corners of a unit square.
04:54
This might feel like a silly thing to do when we already know how to solve this case, but
04:58
it’s a good warmup for turning the larger cases into geometry.
05:01
Notice, flipping one of the coins moves you along an edge of this square, since it’s
05:07
only changing one coordinate.
05:08
The strategy of letting that second coin encode the key location can be drawn by associating
05:15
those bottom two corners, where the y-coordinate is 0, with the “key is under square 0”
05:20
state, and the top two corners with the “key is under square 1” state.
05:28
Think about what it means for our solution to work: No matter where you start, if you’re
05:34
forced to take a step along an edge, forced to flip one coin, you can always guarantee
05:39
you end up in whichever of these two regions you want.
05:47
Now the question is, what does all this look like for bigger chess boards?
05:50
The next simplest case would be three squares, three coins, three possibilities for where
05:54
the key is.
05:56
This gives 8 possible states the coins could be in, and playing the same game of interpreting
06:02
these states as coordinates, it now brings us to 3d space, with each state sitting at
06:07
the corner of a unit cube.
06:10
The usefulness of a picture like this is that it gives a very vivid meaning to turning over
06:14
one of the coins.
06:15
Each flip is a step along one edge of the cube.
06:23
Now, what would it mean for you and your fellow inmate to have a strategy for this puzzle?
06:29
Whenever prisoner 2 walks into the room, they need to be able to associate the state they’re
06:34
looking at, 3 bits, essentially, with one of three possible squares.
06:38
We’re already thinking very visually, so let’s think of those three possibilities
06:43
as colors, red for square 0, green for square 1, blue for square 2.
06:48
In this conception, coming up with a strategy, any strategy, is the same thing as coloring
06:54
each of the 8 corners of a cube either red, green or blue.
07:02
For example, coloring the whole cube red would – well, I don’t know if you’d call this
07:06
a strategy exactly – it would correspond to always guessing that the key is in square
07:10
0.
07:12
If instead you let the sum of the first two coins encode the key location, the cube would
07:20
look like this.
07:21
What’s kind of fun is that we can count how many total strategies exist.
07:26
With three choices for the color of each vertex, we get 38.
07:31
Or, if you’re comfortable letting your mind stray to the thought of painting a 64-dimensional
07:36
cube, you can think about the sense in which there are 64(264) total possible strategies.
07:45
This is the size of the haystack when we’re looking for a needle.
07:50
Another attempt might look like taking 0coin0 plus 1coin1 + 2*coin2, and reduce it mod
08:00
3 if needed; over on Stand-up Maths Matt and I talk about trying a version of this for
08:05
the 64 square case, why it works decently well for a random arrangement of coins, and
08:10
why its ultimately doomed.
08:11
From our view here, it’s just one more way to color the cube, but let’s take a moment
08:17
to walk through some of the corners.
08:19
Let’s say you walk in and all three coins are tails, so it’s like you’re starting
08:24
at the corner (0,0,0).
08:26
Flipping coin 0 doesn’t change the sum, so it takes you to another red corner.
08:32
Flipping coin 1 increases the sum to 1, so that takes you to a green corner.
08:40
And flipping coin 2 takes you up to 2, bringing you to a blue corner.
08:44
The fact that you have access to whatever color you want is a reflection of the fact
08:49
that this strategy will always win if that’s the corner you start on.
08:55
On the other hand, let’s say you started at (0,1,0).
08:59
Flipping coin 0 takes you to another green corner, but flipping either coin 1 or coin
09:07
2 will take you to a red corner, and there’s no way to get to a blue corner.
09:14
Basically what’s happening here is that you have the options to subtract 1, or add
09:20
2, and working mod 3 those are actually the same operation.
09:40
But even without thinking about sums mod 3 or anything like that, you can see this in
09:46
our picture manifested as a corner with two neighbors of the same color.
09:51
If you don’t have a birds eye view of all possible strategies, when you find that any
09:55
specific one that you try doesn’t work, you’re kind just left to wonder if maybe
09:59
there’s some sneaky clever trick you just haven’t thought of.
10:03
But thinking of colors on the cube, you’re naturally led to an interesting combinatorial
10:07
question: Is there a way to color the cube so that the three neighbors of any given vertex
10:14
will always represent red, green and blue.
10:19
Maybe it seems bizarre, even convoluted to go from a puzzle with chess boards and coins
10:23
to talking about painting the corners of a cube, but this is actually a much more natural
10:27
step than you might expect.
10:29
I’ve talked with a lot of people about this puzzle, and what I love is that many of the
10:33
experienced problem solvers immediately jump, unprompted, to talking about coloring corners
10:38
of a cube, as if it’s a kind of de facto natural language for this puzzle.
10:43
And it really is.
10:44
Thinking about binary strings as vertices of a high dimensional cube, with bit flips
10:48
corresponding to edges, actually comes up a lot, especially in coding theory, like the
10:53
error correction stuff I referenced earlier.
10:55
What’s more, you very often hear mathematicians talk about coloring things as a way to describe
11:00
partitioning them into different sets.
11:04
If you’ve ever heard of the hilariously enormous number Graham’s constant, for example,
11:08
the problem where that came up was phrased in terms of assigning to colors to a high
11:13
dimensional cube.
11:14
Though in that case, colors were given to pairs of vertices instead of individual ones.
11:19
The point is, analyzing how to color a potentially high dimensional cube is a more transferable
11:23
skill than you might think.
11:25
So to our question, can you make it so that every vertex has a red, green and blue neighbor?
11:31
Remember, this is the same thing as having an encoding for key locations so that you’re
11:37
always one flip away from communicating whichever key location you want.
11:41
It would actually be enlightening if you paused the video and tried this, it’s like a weird
11:46
3-dimensional sudoku.
11:48
Very similar to a sudoku, in fact, in the sense that you want certain subsets to be
11:53
filled with all 3 possible states.
11:56
You might start painting one corner an arbitrary color, say red, then painting its three neighbors
12:02
red, green and blue.
12:04
It’s red neighbor needs to be adjacent to a green and a blue, so you can draw that in.
12:13
But at least how I’ve done it here, you’re stuck, unable to choose the right colors for
12:17
the next two; can you see why?
12:19
What I’d like to share is a lovely little argument that explains not only why this can
12:24
never work in three dimensions, but why it can’t work in any dimension that’s not
12:28
a power of 2.
12:30
The idea is that the symmetry in the property we want implies that there should be an equal
12:35
number of red, green and blue vertices.
12:38
But that would mean 8/3 of each, which is not possible.
12:43
Before I go on, pause to see if you can think of a way to solidify that intuition; it’s
12:48
a fun exercise in turning a vague instinct into a solid proof.
12:57
One way is to imagine a process where you go through each corner, and count how many
13:02
of its neighbors are a particular color, say red.
13:07
So each step here we’re looking at the three neighbors of a given vertex, counting up the
13:11
red ones, and adding that to a total tally.
13:17
For this coloring that count came out to be 12, but if we had the property we wanted,
13:23
every corner would have exactly 1 red neighbor, so you’d get 8.
13:27
On the other hand, every red corner will be counted exactly 3 times, once for each instance
13:33
when it’s somebody’s neighbor, so that final tally must be 3 times the total number
13:38
of red corners.
13:40
So it’s simple, just find a coloring where 8/3’s of the corners are red!
13:44
Isn’t that nice?
13:46
Counting how many times some corner has a red neighbor is the same as counting how many
13:50
times a red corner has some neighbor, and that’s enough to get us a contradiction.
13:55
What’s also nice about this argument is that it immediately generalizes to higher
13:59
dimensions.
14:01
Think about solving the chessboard puzzle with n squares; again, the puzzle is to associate
14:06
each arrangement of coins with some state, some key location, so that the arrangements
14:15
you can get to with one flip represent all the possible states; any possible key location.
14:23
Even if we can’t visualize most high dimensional cubes we can still talk about vertices of
14:28
such a cube and their neighbors as a way to describe bit strings and those which sit one
14:33
bit flip away.
14:34
There are really just two relevant facts: Standing on one of these vertices, you have
14:41
n different neighbors, and the total number of vertices is 2n, one for each bit string
14:48
of length n.
14:50
You can now play the same game we did in 3 dimensions, going through each corner and
14:55
counting its red neighbors.
14:57
If it’s possible to do the coloring you want, this sum will be 2n, one for each vertex.
15:03
On the other hand, since each red corner is counted once for each of its neighbors, that
15:09
count should be n times the total number of red corners.
15:13
Since the left-hand side is a power of 2, the right hand side needs to be a power of
15:19
2, which can only ever work if n itself is some smaller power of 2.
15:25
For example in four dimensions, or 64 dimensions, there is no contradiction; it’s at least
15:31
possible to evenly divide the vertices among the colors.
15:35
To be clear, that’s not the same as saying there necessarily is a solution for powers
15:40
of two, just that it can’t be ruled out yet.
15:44
This, to me, is completely delightful.
15:48
Just by imagining coloring the corners of a cube and counting how many are of each color,
15:52
you can conclude that no possible strategy, no matter how clever you are, can work in
15:57
all cases for this chessboard puzzle if the number of squares is not a power of 2.
16:03
So if we knocked off a square, or if the board was 6x6 instead of 8x8, the task is hopeless.
16:10
It also means that the solution to the chessboard puzzle, which I’ll point you to in a moment,
16:14
can be viewed as a particularly symmetric way to color the corners of a high dimensional
16:19
cube in a manner disallowed in most dimensions.
16:23
If you’re curious, I couldn’t resist showing this explicitly for a 4-dimensional cube.
16:28
In the same way that you can take a 3d cube and project it down into two-dimensions with
16:33
a little perspective to show the same graph structure of vertices and edges on a flat
16:38
plane, we can do the same projecting a 4d cube into 3d space and still get a full view
16:44
of how all the vertices and edges are connected.
16:48
If you wanted to try your hand at a sort of 4-dimensional cousin of a sudoku, you could
16:53
pause and see if you can figure out how to color these vertices in such a way that the
16:59
four neighbors of any vertex represent all four colors.
17:05
Using essentially the same computation that solves the chessboard puzzle for the four-square
17:10
case, I can get the computer to draw it out for us.
17:17
At this point, I’d like you to hop over to StandupMaths where Matt and I show how
17:28
this solution works.
17:29
If any of you are somehow not yet familiar with StandupMaths, it’s one of my favorite
17:33
channels, run by one of my all-time favorite people, so please do immediately subscribe
17:37
once you land over there.
17:38
You’re in for quite a few delights with everything else the channel has to offer.
17:43
Before explaining it he and I just show what it looks like for us to actually perform the
17:47
solution, and as we do I really want you to try thinking of the solution yourself and
17:51
predict what it is we’re doing before we tell you.
17:55
And if you’re curious about the connection with Hamming codes and error correction, I’m
17:59
certainly game to make a video on that, let me know in the comments.
18:02
I’ve been told that not everyone is as interested in symmetrical ways to paint a 64-dimensional
18:08
cube as I am, but reliable data transmission?
18:11
I think we can all agree that’s universally sexy.