The coolest checkerboard magic trick

I love this puzzle! And here is a quick albeit very mathy solution:

Let $mathcal{B}$ be the canonical basis of $mathbb{Z}_2^{8 times 8}$ then there is a surjective linear map $varphi : ~mathbb{Z}_2^{8 times 8} rightarrow mathbb{Z}_2^6$ with $varphi(mathcal{B}) = mathbb{Z}_2^6$.

This is due to a standart result in linear algebra. A linear map $ mathbb{Z}_2^{8 times 8} rightarrow mathbb{Z}_2^6$ can be defined by specifying the images of a basis of $mathbb{Z}_2^{8 times 8}$. To solve the puzzle we bijectively send the $8 times 8 = 64$ vectors in the basis $mathcal{B}$ to the $2^6 = 64$ vectors in $mathbb{Z}_2^6$; hence defining our $varphi$.

Why is this a solution to the puzzle? Well we have the following correspondences:

And by using $varphi$, any board $A$ corresponds / points to a particular square $varphi(A)$ on the board.

Now say we are given a scrambled board $A in mathbb{Z}_2^{8 times 8}$ and want to find a flip $E in mathcal{B}$ so that it points to the square $p in mathbb{Z}_2^6$ that the audience member chose. Since $varphi(mathcal{B}) = mathbb{Z}_2^6$ there is a canonical vector $E in mathcal{B}$ with $varphi(E) = p - varphi(A)$ and using the linearity of $varphi$ we see $$ varphi(A + E) = varphi(A) + varphi(E) = varphi(A) + p - varphi(A) = p $$ So by doing the flip $E$ on the board $A$ it is now pointing to $p$.

---

Here is one convenient way to put $mathcal{B}$ and $mathbb{Z}_2^6$ into bijection. You can first number the squares as $$ begin{pmatrix} 0 & 1 & 2 & cdots & & \ \ \ & & cdots & 62 & 63 end{pmatrix} ~~~~~~~~~ begin{pmatrix} 00000 & 00001 & 00010 & cdots & & \ \ \ & & cdots & 11110 & 11111 end{pmatrix} $$ where on the right, you see the numbering written in binary with six digits, making it visible that every number corresponds to a vector in $mathbb{Z}_2^6$ in a natural way. Now let $E_j in mathcal{B}$ be the matrix that has a $1$ at $j$ as numbered above. Then we define $varphi$ by $$ varphi (E_j) := text{vector being the binary of } j $$

UPDATE: 3Blue1Brown made a YouTube video about this puzzle, which also gives a very cool visual and geometrical explanation of the problem.

Good answers, but...

I've seen two valuable solutions for this puzzle:

• The answer given by Gamow, which is, in my opinion, the best solution if you want to implement the algorithm in some programming language, but it's not very good/intuitive for the two members of The prodigious Duo (converting so many numbers to binary and XORing all that data isn't an easy task without even a piece of paper).

• The answer given by user2357112, which is probably better if you were to play the trick like The prodigious Duo does, without any help or program; by the way this answer is a bit hard to understand without an example because of the wording etc.

Looking at the second mentioned answer, I figured out that is very easier to understand if you do not use any mathematical notation and just rely on the checkerboard's cells.

The strategy

The strategy applied by the two young magicians to do the trick can be easily explained like this:

1. Divide the $8 times 8$ checkerboard in $6$ different areas, which we'll label with an alphabet letter from $A$ to $F$, represented in this image with the semitransparent white-to-yellow stripes.

   

Doing this, you'll be able to alter the number of black pieces in any of the six areas only flipping one single piece, because of the interjections of these areas. We'll say that a certain area is "black colored" if it contains an odd number of black pieces, and "white colored" if it contains an even number of black pieces.

![Areas 2][6]

From this second image, you'll clearly see that the only square outside of all the areas is the one in the top-left corner, and the only one inside all the areas is the one in the bottom-right corner. This means that you can change the color of all the areas at the same time by flipping the bottom-right piece, or just maintain all the colors unchanged by flipping the top-left piece. Every other piece changes the color of an unique combination of areas. This means that flipping one single piece you can change the color of any combination of areas you want.

2. Now, before the volunteer (let's call him $P$ again) makes his choice, you'll check every area and determine if it's either black or white colored, and apply this simple logic:

• If the area is black, then the piece that you've got to flip is inside such area.

• If the area is white, then the piece that you've got to flip is outside such area.

3. Your goal is to flip the piece which, once flipped, will turn all the areas into white. Analyze all the six areas, and reduce the range of squares that may contain the piece to flip until you end up with only one possible square containing the piece to be flipped: this is guaranteed to happen always, for any combination of black/white pieces.

Now you may be wondering: "why should I find the piece to flip before $P$ makes his choice?". This is because the order of the choices (the magician's one and the $P$'s one) isn't important at all: if you flip two pieces, then the colors of the six areas will change to a new combination which is the same no matter the order of the flipped pieces.

4. Once that $P$ and the first magician have both flipped their pieces, applying the same algorithm described in the first three points will make you find the piece that has been flipped by $P$.

This solution may look difficult, but is the easiest one to use when the only thing you can do is to watch the checkerboard (like Marco and Leonardo do) without touching it, and without any other support rather than your memory.

Mathematical explaination

First of all, number all the squares of the checkerboard with an integer from $0$ to $63$, from the top-left to the bottom-right corner. The result will be this:

^{(Yeah I was too lazy to write all the numbers)}

Now, considered the six areas (from $A$ to $F$), we'll represent the color of each area with a bit:

• $0$ if the area is white (contains an even number of black pieces);

• $1$ if the area is black (contains an odd number of black pieces).

We can order the bits from $A$ to $F$ to obtain a sequence (let's call it $S$) of six bits, something like this: $011010$, which is, in a general case, represented by the notation $b_A b_B b_C b_D b_E b_F$, where $b$ means "bit". $S$ represents the binary notation of the number of the square where the piece to flip (let's call it $X$) is located.

Pretty cool, but why? To make this reasoning more clear, let's break it down:

1. The first bit, $b_A$, tells us if the position of $X$ is either in the upper or lower half of the checkerboard. This is why $b_A$ is placed at the first position in our 6-bit string:

• If $X$ is located in the upper half, then $b_A$ will be $0$, meaning that $S in [000000, 011111]$, and the number of the cell containing $X$ cannot be higher than $31$.

• Otherwise, if $X$ is located in the lower half, the number of its cell must be higher than $31$, as you can see in the picture above, meaning that $S in [100000, 111111]$.

2. The second bit, $b_B$, together with $b_A$, will tell us if $X$ is located in the upper or lower half of the already discovered half:

• If $X$ is located in the upper half of the already discovered half, then $S in [b_A00000, b_A01111]$, which is either from $0$ to $15$ or from $32$ to $47$ (as you can see in the image).

• Otherwise, if $X$ is located in the lower half of the already discovered half, then $S in [b_A10000, b_A11111]$, which is either from $16$ to $31$ or from $48$ to $63$.

3. This reasoning goes on until $b_F$...

Now it should be clear to you why $S$ represents the binary notation of the number of the cell containing $X$.

Puzzle source

I do not know the exact origin of this puzzle, but I actually discovered where I did already see it, thanks to my friend Leonardo who told me that a similar task was asked in the Mathematical Olympiad of Cesenatico, year 2013 (Cesenatico is an Italian town). The task was actually easier, because it only asked to prove that the two magicians' strategy existed, and also to prove that existed only if the number of squares was a power of two.

For the curious, here's the PDF (unfortunately written in Italian) containing the tasks and the solutions of the contest: the one I'm talking about is the 7th.

This indeed is an old puzzle. One possible source (but certainly not the first one) is:

Andy Liu: Two Applications of a Hamming Code
The College Mathematics Journal 40, (Jan 2009), pp. 2-5

The trick on the $2^ktimes2^k$ board is to associate each of the $2^{2k}$ squares with a unique binary number with $2k$ bits. (Note that the number of squares equals the number of such binary labels, so that there indeed exists a bijection).

• Let $y$ denote the binary label of the square picked by $P$ from the audience.
• Consider the checkerboard at the moment just after $P$ has flipped his coin, and consider the binary labels of all the squares with a white piece. Let $z$ denote the XOR of all such white binary labels; hence $z$ is another binary number with $2k$ bits.
• Your goal is to flip a piece, so that afterwards the XOR of all white binary labels becomes equal to $y$.
• Mathematically, you would like to find a square whose binary label $x$ satisfies $x oplus z=y$.
• Since the operation $oplus$ is associative, and since $zoplus z=0$ and $zoplus 0=z$ for all $z$, this desired equation $x oplus z=y$ is equivalent to $xoplus z oplus z=yoplus z$ and furthermore to $x=yoplus z$.
• Hence if we simply flip the square with binary label $yoplus z$, our partner will compute the XOR of all white binary labels and then announce the corresponding square to the audience. Done.

Note also that for the trick we do not need to know the geometric structure of the checkerboard: plain numbering of the squares suffices.

Let the number of cells in the board be $2^k$ for some $k$, and number each cell from $0$ to $2^k-1$.

In step 4, during the "look closely and meticulously at the checkerboard's configuration" part, Leonardo decides which piece he will flip. This is before the audience member makes his choice. For each integer $i$ from $1$ to $k$, Leonardo will count how many black pieces there are in positions whose $i$th bit is $1$. If there is an odd number of black pieces, Leonardo will flip a cell whose $i$th bit is $1$; otherwise, he will flip one of the other cells. This is enough to completely determine which cell Leonardo flips.

When Marco looks at the board, after Leonardo and the audience member have made their flips, he performs the same computations as Leonardo. If there is an odd number of black pieces in positions whose $i$th bit is $1$, the audience member flipped one of those pieces. This is enough to completely determine the audience member's choice.

---

For example, suppose the board to be $4$-by-$4$ pieces wide. The positions are labeled as follows:

00 01 02 03
04 05 06 07
08 09 10 11
12 13 14 15

and it looks like this after the audience member scrambles it:

b b w b
w b w w
w b b b
w w b w

The positions whose first bit is $1$ are the odd-numbered positions:

- b - b
- b - w
- b - b
- w - w

There's an odd number of black pieces in these spots, so Leonardo will flip an odd-numbered position.

The positions with a $1$ in the second bit are the ones in the right half of the board:

- - w b
- - w w
- - b b
- - b w

There's an even number of black pieces here, so Leonardo will flip a piece on the left side of the board.

The positions with a $1$ in the third bit are the second and fourth rows:

- - - -
w b w w
- - - -
w w b w

There's an even number of black pieces here, so Leonardo flips a piece in the first or third row.

The positions with a $1$ in the fourth bit are the ones in the bottom half of the board:

- - - -
- - - -
w b b b
w w b w

There's an even number of black pieces here, so Leonardo flips a piece in the top half of the board.

Putting all this together, we find that Leonardo flips position 1:

- b - -
- - - -
- - - -
- - - -

After Leonardo and the audience member's flips, if any of the halves of the board we've considered have an odd number of black pieces, it's because the audience member flipped one of those pieces. Marco can repeat Leonardo's procedure to find the audience member's piece.