The impossible chessboard puzzle (early view)

oh yeah error correcting codes is very fascinating subject!

Glenn Wo

A series on error correcting codes would be fantastic, I really enjoyed learning about them when i studied wireless comms and seeing the maths visualised would be amazing. Trellis codes were pretty mind blowing. Just a whole series in information theory would fantastic

Great video as usual! A video on error correction would also be very cool.

I would love a video on the coding theory error correction stuff! :) Keen to see the way you and Matt did the trick. I learned how to do it for a 4x4-field (and with it for every number that is a power of two) a few years back and have since found, shown and explained a few ways to it to many students. Of course all have the same fundamental trick to it, but there are so many ways to spice it up and confuse people who thought they knew how it works.

No 3B1B video is complete without a hypercube in there somewhere.

No worse than the South Dakota, "Meth. We're on it", campaign.

Your video made me smile again. Thank you.

Hitoshi Yamauchi

I just watched this interview, and it is incredible. Thank you for suggesting it

I thought of alternative puzzles.... The jailer hides 2 keys and you only need one. What boards work then? Alternative puzzle two, There may be up to n squares with no coin but still only one key. What sizes work then?

William Smith

It would be nice to point out that the coloring of the hypercube is not unique. For example the following is not totally homologous to the one in the video: Y G B G R B R Y Y R B R G B G Y 0000 R 0001 R 0010 B 0011 Y 0100 G 0101 G 0110 B 0111 Y 1000 Y 1001 B 1010 G 1011 G 1100 Y 1101 B 1110 R 1111 R

Grant, what a beautiful way to introduce quantum computing. Bravo!

Reginald Carey

Yes! You'll see in the video on Stand-up Maths I talk about seeking some system where X + X always equals 0. I talk about adding bit-vectors mod 2 instead of xor, but of course, it's all the same thing.

3blue1brown

Good suggestion.

3blue1brown

Ah, I tried to have a number of "pause to consider" moments but hadn't thought about doing that from the beginning. Thanks!

3blue1brown

Hi Alex, I just shot you a DM. If there's any confusion on the patreon tiers, don't hesitate to ask or let me know how I can make the page clearer.

3blue1brown

Hi Grant! Thanks for the video, I really enjoyed the head scratching induced :) Thank you, cheers! And keep up the good work Edit: Thanks Grant, there was a misunderstanding on my side, no worries! Thanks for responding so fast! Cheers

I was expecting the video to have a "pause here if you want to try it for yourself" (which should have happened at 1:25). I realized I was being given hints already and paused at 2:00 to try it, but sadly already with some clues. Is it too late to add something like that for other viewers? I know you did it at the end but there's already a lot of info by then. I really did have a blast figuring out the solution on my own and then watching the video and compare our thought processes.

Nicolas Berube

The "do meth!" joke is really funny, but I hope YouTube doesn't demonetize you for it.

Dachannien

Interesting how different the problem is between you must turn over one coin and you may turn over one coin (or not).

white beard geek

Great video. The 3D -> 2D squishing of a cube made the famous 4D -> 3D representation finally click for me. Accessibility note - please consider improving some scenes (e.g. 16:55) to be more color-blind friendly, by marking the 4D cube corners with a letter corresponding to the color, as you have in other scenes.

Really good one!

Gabe

Another way to think about this would be to encode the state of the board using XOR. Bit-flips corresponds to XOR operations. First label all the cells in the board from 0 to 63. Then the state of the board is the XOR of all the cells with 1. One of the most important properties of XOR is that A^A = 0 and this also leads to the fact that changing from H->T is the same T->H. The state of the board corresponds to the location of key.

Indeed, error correction is a sexy mather.

Daniel Armesto

Please do the error correction codes as well :)

Paolo Torelli

Noooo, that's my super secret magic trick, don't share it with the world :D Here's my setup (SPOILERS for a solution of the puzzle): My accomplice is blindfolded, then someone in the audience set's up a 4x4 square with coins randomly heads-up or hands down. Then I tell them that we'll both flip over a coin and then my accomplice will tell them which coin THEY flipped. I even offer them to go first, because the way I do the cube-coloring, no matter which coin they flip over, it will always encode itself. The code is also super easy to learn and perform on-the fly. I imagine 4 sets: The lower half of the coins, every second row of coins, the right half of the coins and every second column. The code is then that if the number of coins in each of the sets is odd, the encoded coin is part of the set, if it's an even number it is not. Each coin that is flipped changes a unique combination of the sets. Each combination of sets encodes a different coin. All I have to do is to flip the coin that is originally encoded, which flips all the sets to zero (i.e. an even number of heads). All my accomplice has to do is to identify the encoded coin. This can easily be scaled up to the 8x8 board. This is the same as labeling the coins from 0-15 in binary and then bit-wise add all the heads-up coins. The result of this sum gives the encoded square. An easy way to calculate it on the 4x4 grid is to only look at the lower three rows and see which rows have an even number of heads and which rows have an odd number of heads. If all rows are the same (i.e. all are even or all are odd), then the encoded coin is in the first row. If two are the same and one is different (e.g. two rows are even one is odd) then the encoded coin is in the row that's different. Repeat for the columns. This way I can find the encoded coin in less than 3 seconds. (For the 8x8 board I manage to do it in 20 seconds on a good day :))

lets hope this does not end up being a Parker square of a video :)

I don't have the solution explicitly in my head yet, but I *think* this sounds like it ought to look very similar to the construction of the Gray codes. But maybe that's just my brain making a false connection?

Kevin

Fantastic video, Grant - cheers!

Thanks Grant! This is amazing! :)

The error correction part is really fitting to this amazing interview I watched a couple hours ago: https://youtu.be/jDW9bWSepB0

jonas.app