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 8x88 x 8 chess board with 6464 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 6464 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
6 years, 2 months ago

No vote yet
18 votes

  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.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. 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"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

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 - 6 years, 2 months ago

Log in to reply

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 - 6 years, 2 months ago

Log in to reply

Best strategy I have so far:

Number the squares 00 through 6363. If the magic square is MM, then try to flip a token such that the sum of the numbers of the up-token squares is M(mod64)M \pmod{64}.

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

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

This will fail if square NM(mod64)N-M \pmod{64} already has a down-token AND square MN(mod64)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 - 6 years, 2 months ago

Log in to reply

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 VV for the set of all possible states of the board, i.e., the set of sequences a1,a2,,a64a_1, a_2, \ldots, a_{64} where each aia_i is either 00 or 11. Let WW be a set with 64 elements; we will choose WW later. The strategy you need to win this game can be described as follows. You want to find a map f:VWf : V \to W such that for any state of the board vVv\in V and for any wWw\in W, there exists one flip of a token that transforms vv into a state vVv'\in V with f(v)=wf(v')=w.

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

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

Now we finally use the fact that 64=2664=2^6. We can choose WW to also be an abelian group, namely, the product of 6 copies of Z/2Z\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:VWf:V\to W, i.e., a map satisfying f(v+v)=f(v)+f(v)f(v+v')=f(v)+f(v'). Such a map is uniquely determined by the values f(ei)f(e_i), which can be chosen arbitrarily -- because every wWw\in W satisfies w+w=0w+w=0 (otherwise this whole construction would break down). There are 6464 values of ii and 6464 elements of WW, so we can choose the f(ei)f(e_i) to be all the distinct elements of WW. Then, by construction, f(ei+ej)0f(e_i+e_j)\neq 0 for all iji\neq j, which means that f(v+ei+ej)f(v)f(v+e_i+e_j)\neq f(v) for iji\neq j and the proof is complete (if I didn't make any mistakes).

Mitya Boyarchenko - 6 years, 2 months ago

Log in to reply

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

Michael Tong - 6 years, 2 months ago

Log in to reply

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

Michael Tong - 6 years, 2 months ago

Log in to reply

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

Take a 6464-dimensional hypercube with vertices (±1,,±1)(\pm 1, \ldots , \pm1). Each vertex corresponds to one of the 2642^{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 00 through 6363 such that for any vertex, the 6464 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 6464-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 - 6 years, 2 months 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 - 6 years, 2 months 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 - 6 years, 2 months ago

Log in to reply

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

Jimmy Kariznov - 6 years, 2 months 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 - 6 years, 2 months 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=2664 = 2^6 is not coincidental.

Michael Tong - 6 years, 2 months 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 - 6 years, 2 months ago

Log in to reply

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

Daniel Leong - 6 years, 2 months ago

Log in to reply

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

Daniel Leong - 6 years, 2 months ago

Log in to reply

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 - 6 years, 2 months ago

Log in to reply

Trick question. I have no soul.

Cole Wyeth - 6 years, 2 months 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ć - 6 years, 2 months ago

Log in to reply

Yes of course :)

Michael Tong - 6 years, 2 months ago

Log in to reply

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

Ivan Sekovanić - 6 years, 2 months ago

Log in to reply

@Ivan Sekovanić Good luck!

Michael Tong - 6 years, 2 months ago

Log in to reply

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

Daniel Leong - 6 years, 2 months ago

Log in to reply

You copied my name O_O

Daniel Liu - 6 years, 2 months ago

Log in to reply

My surname is leong

Daniel Leong - 6 years, 2 months ago

Log in to reply

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

A Former Brilliant Member - 6 years, 2 months ago

Log in to reply

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

Tim Vermeulen - 6 years, 2 months 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 - 5 years, 5 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...