The impossible chessboard puzzle

An information puzzle with an interesting twist
An equally valuable form of support is to simply share some of the videos.

Thanks to these viewers for their contributions to translations
Hebrew: Omer Tuchfeld

------------------
0:00 Introduction
3:58 Visualizing the two-square case
5:46 Visualizing the three-square case
12:19 Proof that it's impossible
16:22 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.

If 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:

Stream the music on Spotify:

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.

------------------

Various social media stuffs:

[nikanj]

Ah the classic mathematics career path.
Undergraduate > Masters > Doctorate > Postdoc > Assistant Professor > Associate Professor > Professor > Prison Warden

[MinePhantom]

That bit sequence actually maping to "Do math!" and "Do meth!" is the type of small things that makes this channel amazing

[quinn]

He's hiding messages in the checkerboards. They're all in ASCII.
0:29 "3b1b :)"
0:51 "3b1b :("
0:57 "Tau < Pi"
1:26 "FlipBits"
1:27 "BlipBits"
1:30 "ClipBits"
1:33 "ChipBits"
1:36 "ChipBats"
1:38 "ChipRats"
1:41 "ChipVats"
1:44 "ChipFats"
1:47 "ChapFats"
2:08 "Do Math!"
4:06 "To 2 bit"
5:50 "3 Fails!"
16:11 "Please, "
16:13 "go watch"
16:16 "Stand-up"
16:19 "Maths on"
16:22 "YouTube."
Let me know if I missed any!

[kellymacdonald]

After seeing this video a few days ago I could not stop thinking about it, and even after learning the solution I was so amazed by how this could even be possible. I started learning some basics of Python this summer, and today I wrote some code that would allow prisoner 1 to determine which coin to flip and then prisoner 2 to determine where the key was based on the new arrangement. It was the most fulfilling thing I've coded so far and I'm grateful to have been introduced to this puzzle! Thanks for making such an inspiring video!

[kanyenortheast]

There's always the chance I just randomly choose the right square, blowing the warden's mind and my comrade's with sheer dumb luck

[hebl]

Why do mathematicians always set their puzzles in prisons?
Simple: min-maxing. You have maximum amount of time, minimum amount of distractions and maximum motivation to solve the puzzle correctly.

[ridwansetiadi]

A: "Wanna go to their wedding ?"
B: "Nah, I'm busy, I'll just send them present."
A: "There will be an extremely complicated math puzzle which related to higher dimension and computer science."
B: "Done, let's go."

[standupmaths]

This was impossibly good fun. Thanks for getting me involved!

[rishabhpatil]

'The impossible chessboard puzzle' - Me: "Okay! You got this"
ALSO ME: *Stumbles in 2 square case*

[nienke]

This is honestly the first time I understand what that representation of a 4D cube is supposed to convey, it's not about somehow imagining how it would look like, it's just representing the relation of how the vertices are connected

[fakestory]

0:04 don't you hate when you walk into a room and a chessboard just sit there

[athysw.e.]

Grant Sanderson is definitely a master at making you feel these "Eureka" moments.

[gabrielz]

"im doing meth"
police: jail time
computer scientists: interesting correction...

[dasmilekat]

1:03 before flip in ascii code: Tau > pi
1:03 after flip in ascii code: Tau < pi
1:25 in ascii code: 3b1b :)

[thievingonions]

The universe is built on subatomic kn-44s

[ygabvftwfvdawdfasfaytwgtag]

Who would have known this would be the icebreaker to the puzzle in black ops 3, somebody give Jason a raise...

[johnchessant]

3Blue1Brown uploaded: "The impossible chessboard puzzle"
Stand-up Maths uploaded: "The almost impossible chessboard puzzle"

Hmm...

[pikchassis]

If you convert the arrangement of heads and tails at 0:49 into binary then translate it into english the readable text will say this: "3b1b :)"

[ethanlam]

For those interested in this puzzle, this puzzle is also known as "The Devil's Chessboard." Of course there are multiple ways to attack this problem, but interestingly one solution you will find online also has a "computer science" flavor to it, similar to the error correction motivation as seen in this video. A possible solution to this puzzle is to label the the cells of the 8x8 board from 0 to 63 (we do this because we are putting our computer science hats on and start counting from 0). We then note the labels of each cell holding a coin with heads (or tails ... it doesn't matter) facing up. Convert each of those labels into its corresponding 6 bit integer (note that every cell on the board is in one to one correspondence with a binary string of length 6) and XOR all those integers ALONG WITH the label of the cell holding the secret key location. Now convert the result back into an integer which points to the cell holding the coin you should now flip. When your friend looks at the board, he/she will then (using the same labeling as you) XOR all the cells with heads facing up (or tail ... if that was what you used earlier). The final XOR result will be the cell location holding the key! For those not familiar with XORing two numbers, you basically need to line up the two 6-bit integers and look at each column where if you see two 1’s or two 0’s you write a 0 below and write 1 otherwise. Another interpretation is to write a 0 if the two bits are the same and write a 1 if the two bits are different. For example, 111000 XOR 010101 = 101101. You can play around with this strategy, by using a programming language. To XOR two numbers N and M you typically would need to type “N ^ M”.

 To see the connection to computer science, check out an encryption technique called a "One Time Pad." It works exactly through XORs similar to the solution of this puzzle. Let's say you want to encrypt a message, M, to send your friend, and supposed it is N bits long. For a secure encryption, you and your friend should generate a (uniformly) random N bit key, K, beforehand. Then to generate your ciphertext, C, you should compute C = K XOR M (or M XOR K because XOR is commutative which is fairly straightforward to verify). Then your friend would compute C XOR K (or K XOR C) to reveal the message M! The reason this works is because K XOR K always equals 0 for any choice of K (in technical terms K is called the "inverse" of K) and 0 XOR C always equals C for any choice of C (in technical terms 0 is called the “identity”). In addition to being commutative, XOR is also associative. If these properties sound very familiar, it is because it is! XOR sounds kinda like a special addition where negative numbers are just the numbers themselves! With this in mind, I’ll use “+” to denote XOR for brevity. Putting this all together, we know that C = K + M and that when revealing your message your friend will compute C + K = K + C = K + (K + M) = 0 + M = M!

 How does this relate to the Devil’s Chessboard? Well we can think of XORing all the cells with heads (I will ignore the situation where we use tails instead but the analysis is the same) as our “key” K and the key location being our message M. Formally, let K = X_1 + … + X_N where X_i is a cell with heads facing up and let M be the cell holding the key location. To generate our “ciphertext” which will be the cell holding the coin we flip, we perform as stated above C = K + M. The ingenuity of this solution lies in the fact that when your friend comes in and performs the XORing procedure stated above, he/she will compute C + K which as seen before will expose our message M! To see why this is case, note that either C will have been turned from tails to heads or turned from heads to tails. In the first case, your friend will see X_1, …, X_N, and C as heads and compute X_1 + … + X_N + C = K + C. In the second case, C will have flipped a coin that was previously heads (call this X_j), and your friend will then compute X_1 + … + X_(j-1) + X_(j+1) + … X_N = X_1 + … + X_(j-1) + 0 + X_(j+1) + … X_N = X_1 + … + X_(j-1) + (X_j + X_j) + X_(j+1) + … X_N = K + C. The second to last equality used the fact that X + X = 0 (mentioned above) and the last equality was due the commutative nature of XOR. As we see, no matter the case, your friend will ALWAYS compute K + C revealing the location of the key! This puzzle is indeed very cool, and surprisingly has another computer science angle that motivates not only ideas from coding theory but also cryptography!

[OlGreg-pl]

KN-44 gang rise up!! @3blue1brown get on this EE hunt and help us solve it!