Stanford Math Circle

Summer 2012 Puzzles

Ted Alper tmalper@stanford.edu

The Math circle is on break for the summer, but there were so many nice ideas bounced around that we didn't completely finish, and I thought it might be nice to keep them in front of everyone. So here are two puzzles connected to a recent session that I thought I'd leave you with to think about over the summer. You're welcome to send ideas about them to me.

Two puzzles involving invariants and infinite checkerboards

The first puzzle was on Dmitri Zvonkine’s handout last week, but we didn’t have time to look at it during his presentation. It’s really pretty, and it involves a slightly different type of invariant than the other examples we did that day.

We begin with three checkers (or amoebas) on a “chessboard” covering the first quadrant of the plane:

starting position first puzzle

Now we make a series of moves: Each move consists of first selecting any checker on the board for which both the square immediately above it and the square immediately to its right are empty. We then remove the checker from the board while placing new checkers on those two empty squares. For example, here’s a possible sequence of the first four moves:

sample first four moves in first puzzle

(I’ve included the outline of a checker to mark the one removed from the board)

The puzzle is to show that no sequence of moves from the starting position, regardless of its length, will ever succeed in making all three starting squares empty.

You should ask yourself: “How can I find an invariant here? What sort of quantity would stay the same when a checker in one location is replaced with two checkers in related locations?” This is a pretty big hint, you need to find some sort of weight for each checker that depends on the location of the checker such that the sum of the weights of the checkers stays the same as the moves are made. Once you can do that, you can then try to tackle why this invariant shows you can’t reach a situation where those three starting squares are all empty.

This reminded me of a second invariant problem involving checkers on an infinite board. In this one you also have checkers on an infinite board, but with a few differences:

You use the entire plane for your chessboard,not just one quarter of it
You start with an infinite number of checkerson the board, one in every square in the lower half-plane
You move the pieces in a different way, in this puzzle the checkers move as in “Peg Solitaire”, that is, a checker may jump over one adjacent checker (whether above, below, left, or right) if the following square in the same direction is empty. The checker that is jumped over is then removed.
the object of this puzzles is to get at leastone checker as far into the upper half plane as possible (that is, to bring it to a square with the largest possible value of its y-coordinate).

So, the starting arrangment looks like:

starting position for second puzzle

and an initial sequence of moves might look like this (where I’ll draw outline circles for both the previous location of the checker that just jumped and the checker that was jumped over and is now removed):

sequence of starting moves for second puzzle

These moves brought a checker up to the second row above the x-axis, and it might not be too hard to continue this sequence of moves with three more that would bring a checker to the third above the x-axis. But can you reach the fourth row? or the fifth? or any row above the x-axis? And what does this have to do with invariants?

Showing that you can reach a specific row might be simply a matter of constructing a series of moves that reach that row. Showing that you can reach any row, might involve induction. But if you want to show that it’s not possible to reach some row, an invariant could be very helpful! Such an invariant might have to be similar to the weights used in the previous puzzle, but there are two noticable differences:

in this problem, each move replaces two checkers by one, in the previous problem one checker is replaced bytwo.
the three squares affected by a move are three-in-a-row here, in the previous problem they werethree-in-an-L-shape.

How do these differences influence the choice of weights?