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

alt="Your browser understands the <APPLET> tag but isn't running the applet, for some reason." Your browser is completely ignoring the <APPLET> tag!

---

This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at http://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.

---

Discussion

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

Copyright © 1996-2012 Alexander Bogomolny

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₀ ≤ row₁ ≤ row₁ ≤ ... ≤ 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 row₀ = 0 to the largest row_N-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.

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

Copyright © 1996-2012 Alexander Bogomolny