Home Creators Posts Import Register Favorites Logout
haven't archived this post yet. have a subscription? use the importer!

Content

The two videos on the chessboard puzzle are now live!  Give that I've already shared the first with you, linked above is the other part done with Matt Parker on Stand-up Maths.

In it, we demonstrate what it looks like to actually carry out the solution, and then share the details of what we were doing.  More than that, though, it's a discussion of how each of us thought about it when we first heard it.  Simply showing the puzzle and solution would be a fairly short video, but I think laying out the problem-solving process, meandering though it may have been, offers a little more for the audience.

I also had some fun overlaying animations on this, shooting for a kind of blend of the two channels' styles.  Enjoy!

Files

Previews only

The almost impossible chessboard puzzle

Check out the meta-solution on 3Blue1Brown: https://www.youtube.com/watch?v=wTJI_WuZSwE Thanks to Gordon' s Wine Bar for letting us film in their bar. Ha! It wasn't a dungeon, it was a wine bar all along! (An amazing wine bar at that; definitely visit it next time you're in London (and things are open again)). https://www.gordonswinebar.com/ For those of you want it all, and you want it now, we've put the complete, unedited footage of Matt and Grant completing the puzzle scenario on Matt's second channel. We'll put the deleted footage on the Stand-up Maths patreon page: https://www.patreon.com/standupmaths Sorry the audio is a bit hit and miss. Matt's microphone dropped out for a bit so we tried to rescue the audio from Grant's lapel mic. With some success. Puzzle as emailed by Grant to Matt: Prisoner 1 walks in, sees a chessboard where each square has a coin on top, flipped either to heads or tails. The warden places the key under one of the squares, which prisoner 1 sees. Before he leaves, he must turn over one and only one coin. Prisoner 2 then walks in and is supposed to be able to figure out which squares the key is in just by looking at the arrangement of coins. This is the website Matt mentioned with a full breakdown of the solution and interactive boards you can play with. http://datagenetics.com/blog/december12014/index.html CORRECTIONS: - At 20:42 when I (Matt) said "You're now assigning a 64-dimension..." he meant to say "You're now assigning a 6-dimension...". But that is a moot point because Grant can visualise cubes in all dimension spaces with equal ease. - Let me know if you spot anything else! Thanks again, as always, for Jane Street being my principal sponsor. https://www.janestreet.com/ Thanks to my Patreon supporters who help make these videos possible. Here is a random subset: Willy Felton Claire Carroll Matt Langford Steve Davidson James Dexter Stephen Hart Philippe von Bergen Alex Frieder Eric Sexton Matthew Schuster Support my channel and I can make more maths videos: https://www.patreon.com/standupmaths Filming and editing by Alex Genn-Bash Music by Howard Carter Design by Simon Wright and Adam Robinson MATT PARKER: Stand-up Mathematician Website: http://standupmaths.com/ Maths book: http://wwwh.umble-pi.com Nerdy maths toys: http://mathsgear.co.uk/

Comments

Lionel Pöffel

Beautiful. But there seems to be a sound problem with Matt's speech. Especially in the first 10min his voice has very low volume.

Timur Sultanov

Wait wouldn't doing simple XOR of all 64 binary numbers be easier? you calculate XOR of all that are tails and you need to flip 1 coin and it will change XOR to desired number. And by XOR I mean bitwise XOR.

Timur Sultanov

ok I suppose you did describe XOR somewhere in there (sum without carry) but damn you made it convoluted for no good reason.

Dachannien

Introducing Grant Sanderson and What Parker! What? Exactly...

hong mao lan tu qi xia zhuan

Does commenting here get read and is it any more privacy-intrusive than getting a google account just to comment on youtube videos? Because I'd actually like to see more visual intuitions for how all NP-class problems, especially ones involving measuring length, somehow translate to true/false statements. Colors I can understand; since they're just one letter usually, but 5.37348 meters over 7.3m over 10.5m? How can distance be boolean?

Vincent Zalzal

Now that I understand the solution, weirdly, I have an easier time explaining it without the visual support. So, for other people out there that see things like me, maybe this will be easier. Each square with heads on it translates to the square index, from 0 to 63. You want prisoner 2 to be able to sum, with the XOR operator (addition without carry), all squares with heads, and having the sum represent the square where the key is. Now, XOR has the nice property that flipping from 0 to 1 or from 1 to 0 are both represented by XORing the square index, i.e. X xor X = 0. So, flipping a coin is the same as XORing its index to the sum. As prisoner 1, you are given a board with a starting sum, let's call it WARDEN, and let's call the key position KEY. You must change the starting sum by one flip so that the new sum is KEY, resulting in the equation WARDEN xor FLIP = KEY. Rearranging the equation, you get FLIP = WARDEN xor KEY. So, as prisoner 1, you list all squares with heads AND the square with the key, XOR them together, and this gives you the square to flip. Also, even if it doesn't prove anything, you can see that, if there were fewer than 64 squares (i.e. if the number of squares is not a power of two), the value FLIP you computed could end up giving you a non-existent index, so the algorithm wouldn't work. Hope this may help!

Anonymous

I really enjoyed the discussion of how each of you thought about the problem, and not just the solution. Thanks very much for that!

3blue1brown

Nice! Yes, I suppose my inner mathematician is leaking out by talking about adding bit-vectors over mod 2 instead of xor-ing messages, even though they are the same thing.

Anonymous

Here's how I solved it: We'd like a transformation A : {0,1}^(2^n) -> {0,1}^n such that for every x and y (chosen by the warden), there is a basis vector e_i such that A(x+e_i) = y. Assuming A is a linear transformation, this means Ae_i = y - Ax. Therefore, it's enough to define A on the basis vectors so that Ae_i covers the entire space {0,1}^n. If we enumerate all vectors in {0,1}^n = {d_0, ..., d_k} then we can define Ae_i = d_i.

Paul Zagieboylo

I really loved this puzzle. I posted it on greylabyrinth.com and someone asked a followup question: if you remove the adversarial warden and assume the initial arrangement is uniformly random, what's the best (probabilistic) strategy for an arbitrary size board? Clearly you can pretend the board is expanded or reduced (whichever is better for the given size) and hope that you don't have to flip a coin on an expanded board that doesn't exist, or indicate a square outside a reduced board. This has at worst a 70.7% chance of working. Can you do better?

Anonymous

Using addition mod N (N is the board size) instead of XOR, but otherwise keeping the solution works on any board size and has a 75% chance of working (they discuss this briefly in the matt parker video). Would be interesting if you could do better than that.

Daniel Raynaud

Great puzzle. I approached it visually as a n-dimensional cube of length 2. It's easy to play with the 2x2 square and define two regions (eg. top row and left column) that encode 2 bits (sum modulo 2). You can see that each of the 4 squares maps to every possible set of regions (both, neither, top only, left only), and can toggle that set with a flip. You can then extend to 2x2x2 cube with top, left, back regions encoding 3 bits. The one dimensional case is trivial and consistent. Then you get an intuition that it'll work for 4, 5, and then 6 dimensional 2-sided cubes in the same way.

Anonymous

I watched your explanation of the impossible chessboard, and paused near the end to try and work out the general method. I didn't work it out, but ironically worked out a method that works only when the number of bits (call this B) is itself a power of two - I worked it out for coloring the 4dim cube, B=4, so in the 2^4 case, but i think this would work for 2^8 etc. Method is: Think of the color as being a bit vector of length log2(B); the way you assign each vertex a color is by somehow coloring it with lower dimension bit vectors. First, you take each of the B positions, and assign it a length log2(B) bit string - this exactly uses up all the log2(B) bit strings. In B=4, each of the four positions is assigned a length 2 bit string. These short bit strings then represent which of the color bits will be flipped by a flip in that bit position. So, if in B=4, a value on the 4dim cube is given by (a,b,c,d), then the color of the vector (a,b,c,d) is the length 2 bit vector (d + b, d + c) where each is mod2. Notice that the places that a appears is (0,0) ie neither, b appears in (1,0) ie the first, c appears in (0,1) ie the second, and d appears in (1,1) ie both. Its obvious that with this coloring method, given any starting position and any desired ending color, you can get there by just one bit flip; if the color is already correct, flip 'a' which wont change it. if the color needs just the first color bit changed, flip b, if it needs the second color bit changed, flip c, and if it needs both changed, flip d. Since there is already a general solution for 2^n, and this only works for 2^(2^k), its not adding anything there, but it seemed particularly elegant and "dyadic" and maybe there is some connection or some other reason this is interesting. Maybe its just exploiting something about hamming codes in the 2^(2^k) case which isnt deep, but I dont know.