The impossible chessboard puzzle

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

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.

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!

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

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

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

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

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!

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."

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

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

(Without these complex strategies) I think it would be really funny if the warden put every coin on heads except for tails on the key square so you can’t flip it because then they’re all heads and flipping another one would give you like a 50/50

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

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

Matt Parker and I talk about the solution to the original puzzle on his channel: https://youtu.be/as7Gkm7Y7h4 This solution is highly connected to Hamming error correction codes, so much so that doing this puzzle inspired me to make a video about them: https://youtu.be/X8jsijhllIA

For those who are intrested in the general case: The problem of how to encode data with a limited number of bitflips was treated in 1989 in the paper "Coding for write-efficient memory" by Ahlswede and Zhang.

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 :)"

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!

You heard this at a wedding? WHY??!

> color the vertices of a cube "It's all graphs?" "Always has been"