\section*{Problem 4}

Given an infinite sheet of square ruled paper. Some of the squares contain a piece. A move consists of a piece jumping over a piece on a neighbouring square (which shares a side) onto an empty square and removing the piece jumped over. Initially, there are no pieces except in an \(\mathrm{mxn}\) rectangle ( \(\mathrm{m}, \mathrm{n}>1)\) which has a piece on each square. What is the smallest number of pieces that can be left after a series of moves?

\section*{Answer}

2 if \(\mathrm{mn}\) is a multiple of 3,1 otherwise


\section*{Solution}

Obviously \(1 \times 2\) and \(2 \times 2\) can be reduced to 1 . Obviously \(3 \times 2\) can be reduced to 2 . Note that pieces on the four \(\mathrm{X}\) squares can be reduced to a single \(\mathrm{X}\) provided that the square \(\mathrm{Y}\) is empty (call this the L move):

```

. . Y . . X . . X
$\mathrm{X} \mathrm{X} \mathrm{X} \mathrm{X} \mathrm{X} \cdot \mathrm{P} \cdot \mathrm{X} \cdot$. .
. . $\mathrm{X}$. . . . . . . . $\mathrm{x}$

```

Now given 4 x 2 we can reduce it to \(1 \times 2\) :

. . . . x . . . \(x\) x . . . . x . then the L move

\(\mathrm{x} x \mathrm{x} \mathrm{x} \cdot \mathrm{x} \mathrm{x} \mathrm{x} \cdot \mathrm{x} \mathrm{x} \cdot \mathrm{x}^{\mathrm{x}} \mathrm{x}\)

\(\mathrm{x} x \mathrm{x} \mathrm{x} \cdot \mathrm{x} \mathrm{x} \mathrm{x} \cdot \mathrm{x}^{\mathrm{x}} \cdot \mathrm{x} \cdot \mathrm{x}\)

Thus given \(\mathrm{m} \times 2\) with \(\mathrm{m}>3\) we can reduce it to (m-3) \(\times 2\) and hence to one of \(1 \times 2,2 \times 2,3\) \(x 2\). Note also that we are removing 3 pieces at each stage so we end up with 1 piece unless \(\mathrm{m}\) is a multiple of 3 .

Given \(\mathrm{m} \times 3\) with \(\mathrm{m}>1\) we can use the \(\mathrm{L}\) move to reduce it to \((\mathrm{m}-1) \times 3\). Hence by a series of L moves we get to \(3 \times 1\) and hence to 2 pieces.

Now given \(m \times n\) with \(m \geq 4\) and \(n \geq 3\), we can treat it as a \(3 \times n\) rectangle adjacent to an ( \(m\) 3) \(\mathrm{x}\) n rectangle. We can now reduce the \(3 \times n\) to \(3 \times 3\) using \(\mathrm{L}\) moves (with the \(\mathrm{L}\) upright). We can then eliminate the \(3 \times 3\) using L moves (with the L horizontal). Note that we have not changed mn mod 3 .

This deals with all cases, except that we do not reduce 4 x 4 to 1 x 4. Instead we use L moves as follows:

```

X x x x X x x x x x x x x x x . x x . . x . . .
XXXXX . X x x . X x x . X x . . x . . . . . .
X X X X . X X X . X X X . X X . . X . . . . . .

```
![](https://cdn.mathpix.com/cropped/2024_05_09_2c0a57c089c74a6cc642g-137.jpg?height=45&width=1179&top_left_y=2376&top_left_x=243)

So we have shown that if \(\mathrm{mn}\) is not a multiple of 3 we can always reduce to a single piece. Clearly we cannot do better than that. We have also shown how to reduce to two pieces if \(\mathrm{mn}\) is a multiple of 3. It remains to show that we cannot do better. Color the board with 3 colors in the usual way:
\(\cdots \begin{array}{llllllllllll}. & 2 & 3 & 1 & 2 & 3 & 1 & \ldots\end{array}\)

\(\cdots\)\begin{tabular}{llllllll}
\hline & 1 & 2 & 3 & 1 & 2 & \(\cdots\)
\end{tabular}

...

Then any move changes the parity of the number of pieces on each color. If \(\mathrm{mn}\) is a multiple of three, then these three numbers start off equal and hence with equal parity. But a single piece has one number odd and the other two even. So we cannot get to a single piece.

