visual - Counter Flipping

A counter flip game is played in the following way:

• In each move, you can flip an entire row or column


• Flipping a row or column inverts all the counters on that row or column from $X$ to $O$ or vice versa

For example,

\begin{gather*} XOX\\OXO\\XOX \end{gather*} can be converted to \begin{gather*} OOO\\OOO\\OOO \end{gather*} by three moves:

1. Flip first row: \begin{gather*} OXO\\OXO\\XOX \end{gather*}


2. Flip third row: \begin{gather*} OXO\\OXO\\OXO \end{gather*}



3. Flip middle column: \begin{gather*} OOO\\OOO\\OOO \end{gather*}

If you start with \begin{gather*} OOO\\XOX\\OOO, \end{gather*} prove whether or not it is possible to finish with: \begin{gather*} XOO\\OXX\\OOX \end{gather*}

Answer

Consider only the first two cells of the top row and the first two of the bottom row. Every move that changes them flips exactly two. They start off all O, so after every move 0, 2, or 4 of them will be an O. The goal has three O's so is not possible.

Edit: Now that I have a bit more time, and my answer is already the accepted one, I'll add a short summary of the theory of this type of game which most of the other answers have touched on.

• This is a variant of the Lights Out game.



• There are 9 lights, which can be on (O) or off (X).


• There are 6 moves available - flipping any column or any row.


• Applying any move twice is the same as doing nothing.


• You can switch the order the moves, and they still have the same effect.

These last two facts mean that you will have to apply any move at most once, since if you did it more often you can rearrange the moves so that the repeated moves happen successively, after which pairs of them cancel leaving at most one of each.

In this particular puzzle, there are $2^9$ potential states that the 9 lights can have.

The 6 moves are not independent: Flipping all three rows is the same as flipping all three columns. Therefore, we need never use one of the six moves. For example, instead of flipping the first row, you could instead flip all the columns and the other two rows.

That leaves only 5 types of move to play with. Therefore there can only ever be $2^5$ states that we can reach with these moves (as each is applied at most once in any order).

With these 5 available moves we can set the first row and column to any state we like. Use the three column moves to set the states of the first row, and then moves on the bottom two rows to set the rest of the first column. The state of the other four lights cannot be changed independently of the top row and left column.

Consider any of the following sets of four lights:

  x x .    x . x    x x .    x . x
  x x .    x . x    . . .    . . .
  . . .    . . .    x x .    x . x

Every move toggles exactly two of the lights (or none at all). Therefore, the number of lights that are on (of the four you are looking at) can only change by an even number by any move, or by any sequence of moves. If your starting position has an even number of the four lights on, then so will the end position. If it is odd at the start, then it's odd at the end. From this you can deduce what the state of the bottom-right 2x2 square of lights will have to be after you have set the top row and left column to the states you want.

There is a large amount of mathematical literature on the subject of Lights Out games. It can be solved and analysed using Linear Algebra. You can find an explanation of those techniques on my web page here.