The Devil's Chessboard

Since everyone is posting challenges lately, might as well post one that I've heard:

You, your friend, and the Devil play a game. You and the Devil are in the room with a $8 x 8$ chess board with $64$ tokens on it, one on each square. Meanwhile, your friend is outside of the room. The token can either be on an up position or a down position, and the difference in position is distinguishable to the eye. The Devil mixes up the positions (up or down) of the tokens on the board and chooses one of the $64$ squares and calls it the magic square. Next, you may choose one token on a square and flip its position. Then, your friend comes in and must guess what the magic square was by looking on the squares on the board. Show that there is a winning strategy such that your friend can always know what square the magic square is.

Details

You MAY flip a token. As in, you are not forced to flip a token; you may choose to not flip a token.
You can't just tell your friend what square it is. Or point to it. Or text him it. Or... you get the point.
Your friend knows the strategy as well (you tell him beforehand).
If you don't get it right, the Devil takes your soul. High stakes.
There are many ways to approach this problem. Some are more reproducible (i.e. real humans could more reasonable do it) than others. There do exist solutions that humans can reproduce.

Markdown

Appears as

*italics* or _italics_

italics

**bold** or __bold__

bold


- bulleted
- list

bulleted
list


1. numbered
2. list

numbered
list

Note: you must add a full line of space before and after lists for them to show up correctly

paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)

example link

> This is a quote

This is a quote

    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"

# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"

Math

Appears as

Remember to wrap math in $ ... $ or \[ ... \] to ensure proper formatting.

2 \times 3

2 \times 3

2^{34}

2^{34}

a_{i-1}

a_{i-1}

\frac{2}{3}

\frac{2}{3}

\sqrt{2}

\sqrt{2}

\sum_{i=1}^3

\sum_{i=1}^3

\sin \theta

\sin \theta

\boxed{123}

\boxed{123}

Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 2	paragraph 1 paragraph 2
`[example link](https://brilliant.org)`	example link
`> This is a quote`	This is a quote
# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"	# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"

Math	Appears as
Remember to wrap math in `$` ... `$` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Comments

Well this thread has been going for a while and I guess I'll post my favorite solution (credit to Garyados Oak)

Make 6 groups, each corresponding to specific region of the chessboard such that every square has a unique way to report it in terms of being in a group and not in a group. Namely:

Group 1: The top half of the board

Group 2: The left half of the board

Group 3: Rows A, B, E, F

Group 4: Columns 1, 2, 5, 6

Group 5: Rows A, C, E, G

Group 6: Columns 1, 3, 5, 7

Where the rows top to bottom are A, B, C.. and the columns left to right read 1, 2, 3..

Using this, we can communicate any square in a unique manner by saying what groups it is in and what groups it isn't in. For example, take B4:

It is in group 1, 2, and 3, but it is not in group 4, 5, and 6.

Now, the question is how do you communicate what groups it is or isn't in to your friend? This will be done by the number of up-position tokens there are in a group. If that number is odd, then the magic square is in that group. If it is even, then the magic square is not in that group.

Thus, given any configuration of the board, we need to be able to flip one coin and change the groups that are even and need to be odd and the groups that are odd and need to be even while leaving the groups that are correct alone. This can be accomplished by flipping the token on the square that is in the groups which need to be changed, but not in the groups that don't need to be changed. As an explicit example:

Say the magic square is B4. So Groups 1, 2, 3 need to be odd and groups 4, 5, 6 need to be even. The devil gives you a configuration where Groups 1 and 4 are odd and Groups 2, 3, 5, 6 are even. Then you'd find the square that is in group 2, 3, and 4, but not in group 1, 5, and 6, which is F2. Flipping the token in F2 will case group 2 and 3 to now be odd and 4 to be even while leaving the other groups alone.

Thus, your friend comes in, examines the groups for their parity, and can then figure out which square is the magic square.

Michael Tong - 7 years, 10 months ago

Now that I think about it, if you number the squares from 0 to 63 in the right way, then this becomes equivalent to Mitya's solution here.

Jimmy Kariznov - 7 years, 10 months ago

Best strategy I have so far:

Number the squares $0$ through $63$ . If the magic square is $M$ , then try to flip a token such that the sum of the numbers of the up-token squares is $M \pmod{64}$ .

If the current sum is $N \pmod{64}$ , then you either need to flip square $N-M \pmod{64}$ from up to down, or flip square $M-N \pmod{64}$ from down to up. Then, the sum of the numbers of the up-token squares will be $M \pmod{64}$ .

Then, your friend just needs to sum up the numbers of all the squares with up-tokens, take the result $\pmod{64}$ , and guess that square.

This will fail if square $N-M \pmod{64}$ already has a down-token AND square $M-N \pmod{64}$ already has an up-token. So, you still have like a 75ish% chance.

Now can we tweak this so we guess the correct square 100% of the time?

OK, so here is my attempt to tweak your observations into a strategy. I am going to use the fact that 64 is a power of 2, which is perhaps not so good (this wouldn't apply to a 9-by-9 chessboard). If this solution is correct, I would say it is borderline reproducible: a human being with good memory could use it in practice.

Write $V$ for the set of all possible states of the board, i.e., the set of sequences $a_1, a_2, \ldots, a_{64}$ where each $a_i$ is either $0$ or $1$ . Let $W$ be a set with 64 elements; we will choose $W$ later. The strategy you need to win this game can be described as follows. You want to find a map $f : V \to W$ such that for any state of the board $v\in V$ and for any $w\in W$ , there exists one flip of a token that transforms $v$ into a state $v'\in V$ with $f(v')=w$ .

We can encode token flips in the following way. $V$ has a natural addition operation, namely, componentwise addition modulo $2$ . If you want to be more formal, you can say that $V$ with this operation is an abelian group (a product of 64 copies of $\mathbb{Z}/2\mathbb{Z}$ ), or alternatively a 64-dimensional vector space over a field with $2$ elements. Regardless of the viewpoint, let $e_i\in V$ denote the sequence that has $1$ in the $i$ -th place and $0$ everywhere else. Each element of $V$ can be written as a sum of a bunch of these $e_i$ (again, from the linear algebra perspective, the $e_i$ form a basis of $V$ ).

Flipping token number $i$ corresponds to adding $e_i$ to your state $v\in V$ . Hence $f$ needs to have this property: for each $v\in V$ and each $w\in W$ , there exists $1\leq i\leq 64$ with $f(v+e_i)=w$ . Note that because $W$ has $64$ elements, this is the same as requiring $f(v+e_i)$ to be pairwise distinct for all $i$ (if $v$ is fixed). This, in turn, is equivalent to the following property for any $v\in V$ and any $i\neq j$ , we need $f(v+e_i+e_j)\neq f(v)$ .

Now we finally use the fact that $64=2^6$ . We can choose $W$ to also be an abelian group, namely, the product of 6 copies of $\mathbb{Z}/2\mathbb{Z}$ (or a 6-dimensional vector space over a field with two elements). We will look for an additive (or linear) map $f:V\to W$ , i.e., a map satisfying $f(v+v')=f(v)+f(v')$ . Such a map is uniquely determined by the values $f(e_i)$ , which can be chosen arbitrarily -- because every $w\in W$ satisfies $w+w=0$ (otherwise this whole construction would break down). There are $64$ values of $i$ and $64$ elements of $W$ , so we can choose the $f(e_i)$ to be all the distinct elements of $W$ . Then, by construction, $f(e_i+e_j)\neq 0$ for all $i\neq j$ , which means that $f(v+e_i+e_j)\neq f(v)$ for $i\neq j$ and the proof is complete (if I didn't make any mistakes).

Mitya Boyarchenko - 7 years, 10 months ago

Feel free to solve it for an $8 x 8$ case. There are solutions for $n x n$ chessboards but it involves memorizing $2^n$ states of the board and is impossible to reproduce it.

Possibly. I haven't heard of a solution using this but the great part about this problem is there are many solutions.

This observation might help anyone who is good at graph theory solve this problem:

Take a $64$ -dimensional hypercube with vertices $(\pm 1, \ldots , \pm1)$ . Each vertex corresponds to one of the $2^{64}$ possible initial states of the board. Each edge corresponds to a move that you can make by flipping exactly one token.

Color the vertices with colors $0$ through $63$ such that for any vertex, the $64$ adjacent vertices are all different colors. Make sure you and your friend color the graph the same way.

When you are in the room, start at the vertex corresponding to the initial state of the board. Then, find the adjacent vertex whose color number is equal to the magic square's number. Finally, flip the appropriate token such that the final state of the board corresponds to this adjacent vertex. .

When your friend is in the room, he finds the vertex corresponding to the final state of the board and guesses the magic square whose number is equal to the color of that vertex.

This works iff the $64$ -dimensional hypercube can be colored in that manner. Perhaps there is a proof by induction to show that it can be colored accordingly.

@Jimmy Kariznov – It's possible, I don't know for sure, but just to put it out there, there are elegant solutions to the problem that you and a friend could reasonably do with a minute's worth of time.

@Michael Tong – I wonder if the solution you have in mind goes something like this? (This is equivalent to the other approach I proposed, just written in a simpler way.)

You can number the squares on the chessboard as 0, 1, 2, ..., 63. Encode all these numbers in base 2 using exactly 6 digits, so for example, 0 corresponds to 000000, 1 corresponds to 000001, ..., 63 corresponds to 111111. You then agree on the following strategy. When your friend returns to the room and sees the state of the chessboard, he will add up all the numbers corresponding to the squares on which the token is flipped up, but the main point is that he will perform the addition in binary without carrying. So for example, if the tokens are up only on squares 5 and 63, your friend will compute 000101 + 111111 = 111010 (and then convert this back into a decimal between 0 and 63). This sum will represent the position of the square that the Devil chose as the magic square.

The only thing that's needed is to make sure that from any starting position, you can flip one token to reach a position that has the correct sum. But this is actually pretty clear if you think about how addition without carrying works.

@Mitya Boyarchenko – Ahh, bitwise XOR instead of addition. Very clever.

@Jimmy Kariznov – Yes, in hindsight, I should have mentioned this in my solution. I started with a generalization of your idea, then I passed to a special case, and I didn't realize until you mentioned it that the special case is almost identical to your initial approach.

@Mitya Boyarchenko – I can't see any holes in your theory yet since it doesn't matter what state the square you need to add/subtract is because in this form of addition, adding and subtracting a number does the same thing. Good job!

For people who want to find other solutions, the fact that $64 = 2^6$ is not coincidental.

@Michael Tong – It's certainly better than my original idea, which was to flip the token on the square that the Devil chose as the magic square, and then place it back slightly off center. If your friend has 20/20 vision, this might work. :)

@Mitya Boyarchenko – You know, that looks like it would actually work.

Daniel Leong - 7 years, 10 months ago

@Jimmy Kariznov – Seems legit. If both of you can remember hat the hypercube looks like.

Don't do the addition in mod 64, use XOR. That should solve the problem, as addition and subtraction become the same operation so the way the devil flips each square is irrelevant.

Vitalik Buterin - 7 years, 10 months ago

Trick question. I have no soul.

Cole Wyeth - 7 years, 10 months ago

Oh! I've already written a whole paper about this problem (For IB Extended Essay), and I did exactly what you are saying. But I didn't even knew this problem had a name and a Wiki on Brilliant!! Anyways, for someone interested you might want to read the paper here: https://drive.google.com/file/d/1XxeDGOKNlYQ934l8NBtcYr6dwhFeSs7R/view?usp=sharing (if a shared it correctly) Notice that the formulation that I use and the solution is exactly the same as @Mitya Boyarchenko here, but I also point out that "savage" non-linear solutions or strategies (so not reproducible for persons to use) do exist as it is mentioned at the beginning of this article.

Pau Cantos Coll - 1 year, 7 months ago

Can I develop a strategy with my friend before the devil mixes up the tokens and chooses his "magic" one?

Ivan Sekovanić - 7 years, 10 months ago

Yes of course :)

Hmm, thanks. I had something in mind but I appeared to be wrong, sadly :( No sleep for me I guess.

@Ivan Sekovanić – Good luck!

I was thinking in encoding a number 0-63 in binary somehow.

You copied my name O_O

Daniel Liu - 7 years, 10 months ago

My surname is leong

Does this mean your friend does not know weather a token is up or down?

A Former Brilliant Member - 7 years, 10 months ago

He can see the whole board, so he can see it.

Tim Vermeulen - 7 years, 10 months ago

Here is what I thought of: In 64 squares we can get a possible 2^64 combinations of binary digits. We can divide it by 64 and get 2^58 combinations for each column. Now we can convert any given combination to any other combination just by adding one. For example, In a 2*2 matrix, possible outcomes are 2^4. we can divide it by 4 and get 2^2 outcomes for each column. Each column will be like this, 1 2 3 4 0000 0010 0100 1000 0001 0011 0101 1001 1111 1101 1011 0111 1110 1100 1010 0110 Now any possible setup can be converted to another by just changing one bit.
Similarly we can do it for 64 squares.!!

Visal Kumar - 7 years, 1 month ago

Math	Appears as
Remember to wrap math in `\(` ... `\)` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$