1st CIS 1992 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 m x n rectangle (m, 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?
2 if mn is a multiple of 3, 1 otherwise Solution Obviously 1 x 2 and 2 x 2 can be reduced to 1. Obviously 3 x 2 can be reduced to 2. Note that pieces on the four X squares can be reduced to a single X provided that the square Y is empty (call this the L move): . . Y . . X . . X . . . X X X X X . . . X . . . . . X . . . . . . . . X Now given 4 x 2 we can reduce it to 1 x 2: . . . . X . . . X X . . . . X . then the L move X X X X . X X X . . X X . . X X X X X X . X X X . . X X . . X X Thus given m x 2 with m > 3 we can reduce it to (m-3) x 2 and hence to one of 1 x 2, 2 x 2, 3 x 2. Note also that we are removing 3 pieces at each stage so we end up with 1 piece unless m is a multiple of 3. Given m x 3 with m > 1 we can use the L move to reduce it to (m-1) x 3. Hence by a series of L moves we get to 3 x 1 and hence to 2 pieces. Now given m x n with m ≥ 4 and n ≥ 3, we can treat it as a 3 x n rectangle adjacent to an (m-3) x n rectangle. We can now reduce the 3 x n to 3 x 3 using L moves (with the L upright). We can then eliminate the 3 x 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 . . . 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 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 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: ... ...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 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. 1st CIS 1992 © John Scholes jscholes@kalva.demon.co.uk 5 December 2003 Last corrected/updated 5 Dec 03