CTK Insights

Tweet

An interesting problems has been offered at the 1993-1994 Saint Petersburg Regional Mathematical Olympiad, grade 9.

Ten chips are placed on the main diagonal of a 10×10 chessboard, one chip per a square. A move consists in selecting two chips and moving each - if possible for both - to the next square below its present location. Is it possible that after a sequence of moves all the chips be located at the bottom row?

The problem is pretty simple, albeit of the sort that an average student is unlikely to run into during normal schooling. It is interesting, because it allows for several modifications that could be safely and fruitfully added to a very early math curriculum.

First a solution. Do not read further right away if you wish to try your problem solving prowess first.

The squares on the chessboard - a square grid - submits naturally to a (coordinate) two-numbers identification, of which the first number designates the column (left-to-right), the second, the row (bottom-to-top). Under these notations, chip (a, b) can move to (a, b-1), provided b ≥ 1. The problem asks whether it is possible to get all the chips to the horizontal line b = 0.

The chips are originally located at the diagonal {(a, 9 - a)}, a = 0, 1, ..., 9. The left-most chip (0, 9) needs 9 moves to get to the bottom row. The next chip - (1, 8) - needs 8 moves, the other ones will need 7, 6, 5, 4, 3, 2, 1 moves. The one in the lower right corner, (9, 0), could not be moved - his role is entirely static.

For all the chips to reach the bottom row, all these moves would have to be carried out. Let's call the number of available moves (the total for all the individual chips), the height of the chip configuration. At the beginning the height is 9 + 8 + ... + 1 = 45. Importantly, this number is odd. The configuration with all the chips at the bottom has the height of 0 - an even number.

To finally solve the problem, observe that, since on every move two chips slide one square down, the height of the configuration changes exactly by 2 - an even number. This implies that the parity of the height is an invariant of the problem. So, the answer to the problem is negative: it is impossible for the chips in the configuration of an odd height, to be moved into the configuration of an even height.

One observation we can make is that at the outset the chips need not be arranged on the diagonal but only in a manner of Latin Squares: one chip per row and one chip per column. The youngsters can be allowed to place the chips subject to this requirement and then observe that regardless of the starting configuration the problem on a 10×10 board is unsolvable.

Now, taking square boards of a different size, are there some for which it is possible to reach the bottom row? For some at least the height is even. For example, 4×4 or 5×5 boards have even heights (6 and 10, respectively.) The problem on these boards can be solved, but the solution requires a certain strategy: randomly choosing a pair of chips for a move may by chance lead to a solution; it won't always.

What strategy will work? One that always does is to choose two chips with the maximum individual heights. Indeed, let's call a configuration of chips blocked is it does not permit a legal move. Blocked configurations have all the chips at the bottom and a single chip (a, b) with b > 1. This is a nice problem to prove that the strategy of always choosing two chips with the maximum individual heights could not lead to a blocked configuration.

The problem could be converted to a game for two players who move alternately. On a board of even height, could either of the players assure reaching the bottom row or ending up with a blocked configuration?

Some of these questions are discussed elsewhere.