5
$\begingroup$

It is your first day in prison and you are approached by a guard having a hunch for puzzles.

He tells you that he gives every new prisoner the chance to be freed if they can present him with a version of his favorite puzzle that he can not solve. He proudly informs you that no one has gotten out so far; he is just too good.

The puzzle requires the prisoner to arrange $9$ coins in a $3 \times 3$ grid with heads or tails up by his choosing. The guard will then try to find a way to turn all coins to head until the next day. But he is only allowed to turn coins in a slected $2 \times 2$ square or vertical/horizontal line, not only single coins.

After he explained the puzzle to you, he confidently adds "And you know what? Starting today, I will beat everyone without turning any middle lines." You smile and gladly agree to the challenge, with the burning question in mind:

Will I really be the first one to get out?

$\endgroup$
  • 1
    $\begingroup$ "Will I really be the first one to get out?" - no, because this guard is obviously messing with you. He wants to get your hopes up and then laugh in your face at how gullible you are. $\endgroup$ – user2357112 supports Monica Aug 15 at 20:15
  • $\begingroup$ Is the "middle line rule" an actual rule, or is he allowed to break that since it's just his boasting, and not a part of the actual rule set? $\endgroup$ – Vilx- Aug 16 at 0:29
  • $\begingroup$ @Vilx- No he will stick to it and not turn any coins along the middle line. I changed the text to hopefully make this more clear. $\endgroup$ – Nemo Aug 16 at 7:02
7
$\begingroup$

Yes.

Let $v_1, v_2, \dots, v_8$ denote the $8$ possible moves that the guard may use ($4$ squares and the $4$ outer lines). Consider the moves as group actions on the set of grids. Since $v_i^2 = e$ and $v_i v_j = v_j v_i,$ there are at most $2^8 = 256$ grids reachable from one where all coins are heads. There are $2^9 = 512$ grids in total, so there exists at least $256$ for which the guard will fail. To make this solution constructive, you may enumerate the valid grids and choose one that doesn't appear in the list.

Explicit Grid

The grid where the bottom left corner is tails and everything else is heads is not solvable. If it is, then there is a sequence of moves to flip this corner. By symmetry, there is a sequence of moves to flip any corner, and combining with a move flipping an outer line, there is a sequence of moves to flip any of the outer $8$ squares. Combining with a $2 \times 2$ square, there is a sequence of moves to flip any square, hence any position is reachable, contradiction. In fact, there are exactly $256$ reachable positions since the vectors representing each move are linearly independent over $\mathbb{F}_2:$ Wolfram-Alpha

| improve this answer | |
$\endgroup$
  • $\begingroup$ The reasoning and conclusion are correct! However it does not yet answer the formulated question completely. And you will get bonus credit for describing a grid which he can not solve ;) $\endgroup$ – Nemo Aug 15 at 11:59
  • 1
    $\begingroup$ @Nemo I have found a grid that works, but you may not like the way I proved it doesn't work. $\endgroup$ – Display name Aug 15 at 12:30
  • $\begingroup$ @Nemo - I liked FlorianF's answer better. :) $\endgroup$ – Vilx- Aug 16 at 12:38
  • $\begingroup$ @Vilx- His answer is not complete yet ;) $\endgroup$ – Nemo Aug 16 at 12:41
  • $\begingroup$ @Nemo - Oh, come on! :D $\endgroup$ – Vilx- Aug 16 at 12:45
15
$\begingroup$

There is a simple solution.

Turn all the coins to tails. This will set you free.

Because

Consider the coins marked with X.
X . X
. X .
X . X

Every move reverses exactly 2 of these coins. Since you start with an odd number of tails among the X's, the number of tails will remain odd whatever the guard does. So it is impossible for him to reach zero tails.

PS: Note that aschepler also came to the conclusion that corners plus center parity is the problem, in a more systematic analysis of the question. I just showed it is A problem. And that is enough I think.

| improve this answer | |
$\endgroup$
5
$\begingroup$

Adding some findings to the answer by Display name.

As already noted,

the effects of different sequences of moves form a commutative group generated by the original 8 moves, which all have order 2, so this group of grid actions cannot be larger than $2^8$, and cannot reach the desired coin state from all $2^9$ possible coin states.

Call the coin positions

1 2 3
4 5 6
7 8 9

and label the guard's moves with digits for the flipped coins, e.g. {147} and {2356}.

The guard has sequences of moves which can:

Flip the coin in the middle of any edge, leaving the other 8 in their same states.

To flip coin $2$, do {4578} {5689} {147} {369} {123}. The others are possible by rotating this pattern.

and sequences which can:

Flip any corner coin and the center coin, leaving the other 7 in their same states.

To flip coins $1$ and $5$, do {369} {789} {2356} {4578} {1245}. The others are possible by rotating this pattern.

By combining these sequences, the guard can solve any initial position where:

the number of center and corner coins showing heads is odd. This gives $2^8$ solvable positions, and as mentioned above, there cannot be any more solvable positions, so this is a necessary and sufficient condition on solvable puzzles.

Though it seems strange that

nobody has won before, since anyone just placing randomly would have a $\frac{1}{2}$ chance of creating an impossible puzzle. Maybe the part about not using middle rows is new, if the guard got too confident.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ In fact, we can skip all of the group theory now. Each move does not change the parity of $T,$ the total number of center and corner coins showing heads, so only the $256$ positions where $T$ is odd are candidates for reachable positions. And the moves you gave can reach any of these candidates. $\endgroup$ – Display name Aug 15 at 14:08
  • $\begingroup$ This gives the full solution! About the last comment: Yes, he has gotten to confident. $\endgroup$ – Nemo Aug 15 at 15:23
  • $\begingroup$ @Displayname Ah right, that's a simpler way to see the other states aren't solvable. $\endgroup$ – aschepler Aug 15 at 15:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.