### An Olympiad Problem for a Kindergarten Investigation

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

The chips are originally located at the diagonal {(a, 9 - a)}, a = 0, 1, ..., 9. The left-most chip

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

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

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.

[...] Bogomolny from CTK Insights presents An Olympiad Problem for a Kindergarten Investigation. He gives a problem that is simple to describe and that has a simple but sophisticated [...]

July 5th, 2011 at 8:16 pmI am going to use this question up here in Brazil and later I can tell you the results!

November 28th, 2011 at 5:12 pmThis problem made me hard, I'm studying at Scholl high now, but I can not solve.

regards

December 7th, 2011 at 10:10 pmque es el amor