# Moving Chips in Pairs Down a Checkerboard

N chips are placed on an N×N checkerboard, one per row and one per square. A move consists in sliding one square down any two of the chips. Is it always possible to have all the chips in the bottom row? When it is possible, devise a strategy which insures that all chips arrive at the bottom row.

(Select a pair of chips and then press the *Make Move* button. To select/deselect a chip just click on it.)

What if applet does not run? |

|Activities| |Contact| |Front page| |Contents| |Arithmetic|

Copyright © 1996-2018 Alexander Bogomolny

### Discussion

N chips are placed on an N×N checkerboard, one per row and one per square. A move consists in sliding one square down any two of the chips. Is it always possible to have all the chips in the bottom row? When it is possible, devise a strategy which insures that all chips arrive at the bottom row.

What if applet does not run? |

Let's identify a chip with a pair of numbers - the column and row in which the chip is located. The counting starts form the low left corner *height of a chip* is its row number. The *height of a configuration* of chips is the sum total of the heights of the chips in the configuration. A configuration is *solvable* if it is possible to move all the chips in the configuration to the bottom row by a sequence of legal moves. A configuration is *blocked* is all the chips in it but one are located in the bottom row.

### Proposition 1

If the height of a configuration is odd, the configuration is not solvable.

The claim is rather obvious but was discussed at some length elsewhere.

### Proposition 2

If the height of configuration is even, the configuration is solvable. The strategy of selecting on every move two chips with the largest heights always succeed in moving all the chips to the bottom row.

### Proof

Let's arrange the heights of the chips in an ascending order

row_{0} ≤ row_{1} ≤ row_{1} ≤ ... ≤ row_{N-1}

Call such a sequence the *signature* of the configuration. Observe that, for the original configuration where the chips have been placed one per row, the signature has no gaps: it contains all the integers from the least _{0} = 0_{N-1} = N-1.

If a configuration of even height is blocked, then the only chip

|Activities| |Contact| |Front page| |Contents| |Arithmetic|

Copyright © 1996-2018 Alexander Bogomolny

64266857 |