Solution to the chessboard puzzle

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.

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.

Daniel Raynaud

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.

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?

Paul Zagieboylo

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.

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.

3blue1brown

I certainly read all the comments here, but not all on YouTube. For keeping track of topic requests, I often refer to the thread at the top of https://www.reddit.com/r/3Blue1Brown/

3blue1brown

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

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!

Vincent Zalzal

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?

hong mao lan tu qi xia zhuan

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

Dachannien

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

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

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

Lionel Pöffel