Waste less time on Facebook — follow Brilliant.
×

The Devil's Chessboard

This note has been used to help create the Combinatorial Games - Winning Positions wiki

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.

Note by Michael Tong
4 years ago

No vote yet
18 votes

Comments

Sort by:

Top Newest

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 · 4 years ago

Log in to reply

@Michael Tong 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 · 4 years ago

Log in to reply

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? Jimmy Kariznov · 4 years ago

Log in to reply

@Jimmy Kariznov 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 · 4 years ago

Log in to reply

@Mitya Boyarchenko 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. Michael Tong · 4 years ago

Log in to reply

@Jimmy Kariznov Possibly. I haven't heard of a solution using this but the great part about this problem is there are many solutions. Michael Tong · 4 years ago

Log in to reply

@Michael Tong 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 · 4 years ago

Log in to reply

@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 · 4 years ago

Log in to reply

@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 · 4 years ago

Log in to reply

@Mitya Boyarchenko Ahh, bitwise XOR instead of addition. Very clever. Jimmy Kariznov · 4 years ago

Log in to reply

@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 · 4 years ago

Log in to reply

@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 · 4 years ago

Log in to reply

@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 · 4 years ago

Log in to reply

@Mitya Boyarchenko You know, that looks like it would actually work. Daniel Leong · 4 years ago

Log in to reply

@Jimmy Kariznov Seems legit. If both of you can remember hat the hypercube looks like. Daniel Leong · 4 years ago

Log in to reply

@Jimmy Kariznov 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 · 4 years ago

Log in to reply

Trick question. I have no soul. Cole Wyeth · 4 years ago

Log in to reply

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 · 3 years, 4 months ago

Log in to reply

Does this mean your friend does not know weather a token is up or down? Yash Talekar · 4 years ago

Log in to reply

@Yash Talekar He can see the whole board, so he can see it. Tim Vermeulen · 4 years ago

Log in to reply

I was thinking in encoding a number 0-63 in binary somehow. Daniel Leong · 4 years ago

Log in to reply

@Daniel Leong You copied my name O_O Daniel Liu · 4 years ago

Log in to reply

@Daniel Liu My surname is leong Daniel Leong · 4 years ago

Log in to reply

Can I develop a strategy with my friend before the devil mixes up the tokens and chooses his "magic" one? Ivan Sekovanić · 4 years ago

Log in to reply

@Ivan Sekovanić Yes of course :) Michael Tong · 4 years ago

Log in to reply

@Michael Tong Hmm, thanks. I had something in mind but I appeared to be wrong, sadly :( No sleep for me I guess. Ivan Sekovanić · 4 years ago

Log in to reply

@Ivan Sekovanić Good luck! Michael Tong · 4 years ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...