The coolest checkerboard magic trick

Question

In the small town of Terni (Italy), there's a couple of young friends named Marco and Leonardo, who like to perform magic tricks to a restricted audience of common friends and relatives. They like to call themselves "The prodigious Duo". Every week-end, The prodigious Duo meets at the house of the leader, which happens to be Marco, to practice new magic tricks, learn new techniques, and, most importantly, to set up the magic show of the week, which will be shown to the audience in the late evening.

Recently, the leader of The prodigious Duo discovered what he claims to be "the coolest magic trick ever done using a chessboard" (which actually is a checkerboard, but that's basically the same thing). 
Marco only tested the trick on a $2 times 2$ squares checkerboard, nonetheless he's certain that the trick would work on any checkerboard with size $n times n$, where $n$ is a perfect power of two (meaning that the binary logarithm $log_{2}n$ of $n$ is an integer). 
So he managed to create a working strategy for a real checkerboard (with $n=8$). Once tested the strategy for the bigger board on a piece of paper, Marco is now ready to explain the trick to Leonardo.

He starts explaining the peculiarities of the checkerboard involved in the trick, since that it isn't a normal checkerboard:

"The checkerboard is composed by $8 times 8$ squares, like a normal one, except that the squares are all red colored, and distinguishable because of the vertical and horizontal lines which define them. This red color choice is only made to avoid confusion when moving the pieces."
"The pieces of the checkerboard are normal coin-shaped pieces, except that they're white on one side and black on the other one."
"The checkerboard is always visible to all the members of the audience during the show, and so will be me and you, remember it, this is important."

Then he explains the magical trick from the spectators' point of view:

"At the beginning of the show, the checkerboard is filled with sixty-four pieces, each one placed inside a different square. The pieces' sides facing up are of mixed color, and their initial color doesn't really matter for the purpose of the trick (e.g. the quantity of black or white pieces doesn't matter)."
"Once the checkerboard is set up, you will ask for a member of the audience (we'll call him $P$) to come up on the stage to participate in the trick."
"Once on the stage, I will cover my eyes and ears with a special mask which will make me unable to see or hear anything around me. Now you'll ask $P$ to rearrange the colors that he sees on the checkerboard flipping any number of pieces he wants, any number of times."
"Now you will take a minute or less to look closely and meticulously at the checkerboard's configuration, and then ask $P$ to: choose a piece among the 64 pieces on the board, flip it only one time, and memorize its position."
"Once $P$ has done its simple task, you'll do the same thing: you'll carefully choose a piece (which doesn't necessarily need to be different from the one chosen by $P$), and flip it one time. At this point, you will lock your head into the same kind of mask I used before, and, once done, ask $P$ to touch me to let me know you cannot see or hear anything."
"Felt the touch and removed my mask, I'll reach the checkerboard, carefully observe it for a bit, and finally remove a single piece from it: the piece that has been chosen by $P$."
"I'll now help you to remove your mask and bow down with you to the surprisingly cheering audience and the astonished $P$, which is trying to work out what sort of sorcery has been going on moments before."

Leonardo takes a minute to elaborate all the information provided to him by Marco, and then, excited, replies: "This is an incredible magic trick, but man, I mean, sixty-four pieces... how could we ever even think about that? Tell me you've got a solving strategy which is as beautiful as this impressive trick!". Marco starts now to explain the real strategy which they are going to apply to recognize the piece chosen by the volunteer on the stage...

You're asked to discover and explain the strategy which The prodigious Duo is going to apply to find the correct piece chosen by the volunteer.

Clarifications and notes

Now, stating some basic facts that might be misunderstood:

During their show, none of the members of The prodigious Duo can communicate with each other, because of the masks they use to cover their heads.

This means that Marco cannot, in any way, see or listen to what's happening on the stage when the volunteer is mixing up the colors flipping the pieces on the checkerboard.
And also that Leonardo cannot, in any way, see or listen to what's going on when Marco removes his mask and looks at the checkerboard, revealing the piece chosen by the volunteer.

No one knows, except for the two magicians, the strategy applied to recognize the piece moved by the volunteer.
The volunteer called on the stage isn't, in any way, collaborating with the magicians nor cheating; same goes for the rest of the audience.
Avoid stupid answers like "Marco checks for the fingerprint leaved by the volunteer on the chosen piece" or similar.

Personal notes

I want to clarify that I didn't think up this puzzle by myself, I only made up some little story-line; I did listen to it years ago talking with some friends of mine, and it randomly came back in my mind recently. For this reason, I do not know the exact solution of this puzzle (and this is the main reason why I am asking for a solution here on SE), nonetheless I'm still able to provide additional details and explanations to anyone who asks for them, editing the question itself or answering the comments. Given that I do not know the real source of this puzzle, it would also be nice if someone could provide it. Oh, and in case you were wondering: yes, that "Marco" is me, ahah.

Marco Bonelli · Accepted Answer

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:

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.

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.

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.

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:

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]$.

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

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.

user2357112 supports Monica · Answer

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.

Gamow · Answer

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.

The coolest checkerboard magic trick

He starts explaining the peculiarities of the checkerboard involved in the trick, since that it isn’t a normal checkerboard:

Then he explains the magical trick from the spectators’ point of view:

You’re asked to discover and explain the strategy which The prodigious Duo is going to apply to find the correct piece chosen by the volunteer.

Clarifications and notes

Personal notes

3 Answers

Good answers, but...

The strategy

Mathematical explaination

Puzzle source

Add your own answers!

Ask a Question