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.)


If you are reading this, your browser is not set to run Java applets. Try IE11 or Safari and declare the site https://www.cut-the-knot.org as trusted in the Java setup.

Moving Chips in Pairs Down a Checkerboard


What if applet does not run?

Discussion

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

Copyright © 1996-2017 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.


If you are reading this, your browser is not set to run Java applets. Try IE11 or Safari and declare the site https://www.cut-the-knot.org as trusted in the Java setup.

Moving Chips in Pairs Down a Checkerboard


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 (0, 0). The 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

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 row0 = 0 to the largest rowN-1 = N-1. A move that slides two chips with the largest heights down one square changes the signature but creates no gaps.

If a configuration of even height is blocked, then the only chip (a, b) that is not in the bottom row has b > 0 and even, meaning that the configuration's signature has a gap. Since the signatures of the original configuration and all subsequent ones obtained by selecting two chips with the largest heights has no gaps, such a strategy could not possibly lead to a blocked configuration. Since the process of moving pairs of chips may only consist of a finite number of moves, the strategy always terminates with all the chips at the bottom row.

Related material
Read more...

  • A Three Pegs Question
  • Solitaire on a Circle
  • Peg Solitaire
  • The Game of Fif
  • Nim
  • Sums and Products
  • Splitting Piles
  • Chameleons of Three Colors
  • White and Black Balls in Urn. 1 in, 2 out. What Color Remains?
  • Extension of Euclid's Game
  • |Activities| |Contact| |Front page| |Contents| |Arithmetic|

    Copyright © 1996-2017 Alexander Bogomolny

     62643881

    Search by google: