Maths Olympiad Prep

Library / /19 of 19

Combinatorics Difficulty 7.5 National Olympiad, round 2 Prove it Soviet Union

Problem:

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 m×nm \times n rectangle (m,n>1m, 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?

Solution

Solution:

2 if mnmn is a multiple of 3, 1 otherwise

Obviously 1×21 \times 2 and 2×22 \times 2 can be reduced to 1. Obviously 3×23 \times 2 can be reduced to 2. Note that pieces on the four XX squares can be reduced to a single XX provided that the square YY is empty (call this the L move):

. . . . . . . . . . . . . . . . . . . . . . X X X X X . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . X X . . . . . . . . . . . . . . . . . . .

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

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

Now given m×nm \times n with m4m \geq 4 and n3n \geq 3, we can treat it as a 3×n3 \times n rectangle adjacent to an (m3)×n(m-3) \times n rectangle. We can now reduce the 3×n3 \times n to 3×33 \times 3 using L moves (with the L upright). We can then eliminate the 3×33 \times 3 using L moves (with the L horizontal). Note that we have not changed mnmod3mn \bmod 3.

This deals with all cases, except that we do not reduce 4×44 \times 4 to 1×41 \times 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 X . X X X . X X X . X X . . . . . . . . . . . . . . . . . . . . X X X . X X X . X X X . X X . . . . . . . . . . . . . . . . . . . . X X X . X X X . . . . . . . . . . . . . . . . .

So we have shown that if mnmn 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 mnmn is a multiple of 3. It remains to show that we cannot do better. Color the board with 3 colors in the usual way:

. . . . . . . . . . . . . . . . . . . . . 1 2 3 1 2 3 . . .
. . . 2 3 1 2 3 1 . . . . . . . . . . . . . . . . . . . . 3 1 2 3 1 2 . . . . . . . . . . . . . . . . . . . .

Then any move changes the parity of the number of pieces on each color. If mnmn 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.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.