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
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
row0 ≤ row1 ≤ row1 ≤ ... ≤ rowN-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
If a configuration of even height is blocked, then the only chip


|Activities| |Contact| |Front page| |Contents| |Arithmetic|
Copyright © 1996-2018 Alexander Bogomolny
72264331