Will you be the first to get free?

Question

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?

Answer 1

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

Answer 2

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.

Answer 3

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.