Not puzzling reviews

 Princeton University Press page

Jason Rosenhouse is professor in the Department of Mathematics at James Madison University. His research focuses on algebraic graph theory and analytic number theory involving exponential sums. The former includes a neat paper on expansion properties of a family of graphs associated to block designs, with two undergraduates among its authors. But besides his “real” research, he has written a number of books on puzzles such as The Monty Hall Problem: The Remarkable Story of Math’s Most Contentious Brain Teaser. Soon his book Games for Your Mind: The History and Future of Logic Puzzles is to be published.

Today Ken and I thought we would highlight his recent review of a book on math puzzles.

I have mixed feelings about puzzles. I like them, and am happy when I can understand their solution. I am even happier when I can solve them. I sometimes feel that I should spend my limited brain cycles on “real” problems. But puzzles are fun.

Rosenhouse’s review is in the recent Notices of the AMS on the book Bicycles or Unicycles: A Collection of Intriguing Mathematical Puzzles. This book, the “Bicycle Book,” is authored by Daniel Velleman and Stan Wagon.

Their book is a collection of ${3 \times 5 \times 7}$ mathematical puzzles. Rosenhouse likes their book, which means a lot coming from an author of so many puzzle books himself.

## A Cool Problem

Rosenhouse presents this problem from the Bicycle Book.

You are playing solitaire in the first quadrant of the Cartesian plane, the lower corner of which is shown in Figure 1. You begin with a single checker on square a1. On each turn, a legal move consists of removing one checker from the board and then placing two new checkers in the cells immediately above and to the right of the original checker. If either of those two cells is occupied, then the move is illegal, and a different checker must be selected for removal.

Show that you can never make all of the ${3 \times 3}$ lower-left squares empty. This is a complexity question. You describe a computation and assert that certain states cannot be reached. The challenge is two-fold:

1. The computation is nondeterministic. There can be more than one next state.

2. The computation can reach infinitely many states. The task is to prove that no reachable state has the lower nine squares empty.

## A Cool Solution

I must admit I read the solution before I tried to solve the puzzle. I did find an alternative solution. It was not as clever as the one from the book. Let’s look at that solution first.

The idea is to assign magic values to each square on the checkerboard. The value of a state is the sum over all the values of squares with a checker. We need these to hold:

1. The value of the initial square is ${1}$.

2. The value of a move leaves the total sum over all the checkers the same.

3. The value of the squares not in the lower ${3 \times 3}$ is less than ${1}$.

Then there can never be a reachable state that avoids all the lower ${3 \times 3}$. How can we do this? Assign the values as shown below.

$\displaystyle \begin{array}{ccccl} \vdots & \vdots & \vdots & \vdots & \\ 1/8 & 1/16 & 1/32 & 1/64 & \cdots\\ 1/4 & 1/8 & 1/16 & 1/32 & \cdots\\ 1/2 & 1/4 & 1/8 & 1/16 & \cdots\\ 1 & 1/2 & 1/4 & 1/8 & \cdots \end{array}$

Ken remembers, as a teenager, seeing this puzzle in a collection by the master Martin Gardner, with the same proof. Ken thought of it again when considering problems in physics and combinatorics that involve defining an appropriate potential function as the first step.

## An Uncool Solution

Let ${C}$ be the lower-right ${3 \times 3}$ corner board. Label the positions as usual with ${(i,j)}$ where ${i,j}$ both are in ${\{1,2,3\}}$.

Let ${N(t)}$ be the number of checkers in ${C}$ at time ${t}$. Of course ${N(0)=1}$ and the checker is at ${(1,1)}$.

Suppose by way of contradiction that it is possible to make ${C}$ empty.

Our proof uses that the transition from ${N(t)>0}$ to ${N(t+1)=0}$ requires that ${N(t)=1}$. That is ${N(t)=2}$ or even ${3}$ is impossible. The rule cannot remove two or more checkers from ${C}$ in one move.

Let ${N(t)=1}$ and ${N(t+1)=0}$. So where is the checker? A simple case analysis shows it must be at ${(3,3)}$. So now we know the last placement. But how did we get to this position? It is easy to see that it had to be previously at ${(3,2)}$ or ${(2,3)}$. By symmetry we can assume was ${(3,2)}$.

Our goal to show that we cannot place one checker at ${(3,2)}$ and no other in ${C}$. A little analysis shows that it must be the case that the previous state was one checker at ${(3,1)}$. But it is impossible to place a checker there and avoid having more checkers. This yields a contradiction.

## Another Solution

We could use finite state automata theory to supply another solution. The obvious issue is the full game is played on an infinite checkerboard. But we can use a standard trick to reduce the state space to a finite one. Imagine we play the game on just ${C}$. When we have a move that creates checkers outside of ${C}$ just throw them away. It is simple to see that no move can place checkers inside ${C}$. Thus if we cannot empty ${C}$ in this finite version, then there is no way in the full game.

Now the state space is bounded by ${2^{9}}$: each of the nine squares can have a checker or not. We know the initial state and we know the final state. So we can run a finite state search algorithm and decide the answer.

The value of this solution is that it could handle more complex rules and larger squares. Well at least those within reason.

## Other Puzzles

Rosenhouse covers nine other puzzles in his review. In our meta review of his review we will cover just two more.

The third puzzle in his review comes from the challenge to prove that each matrix in a certain family ${\{C_n\}}$ has determinant ${1}$. The particular matrices ${C_{n}}$ look like they could have some strange determinant, one that even varies with ${n}$. The trick is to show that there are other families ${\{A_n\}}$ and ${\{B_n\}}$ of matrices, in which each matrix has determinant ${1}$ and that

$\displaystyle C_n = A_n B_n.$

Of course this immediately proves that ${C_{n}}$ also have determinant ${1}$. The challenge is kind of a factorization problem.

Another puzzle is to prove that a number ${p}$ is prime if and only if there is exactly one pair of positive integers ${m,n}$ such that

$\displaystyle \frac{1}{m} - \frac{1}{n} = \frac{1}{p}.$

This seems to be surprising in two ways: First who could think of this? Second who could think of this? Okay it should be why is it true? Indeed Rosenhouse says that the proof is complex.

Rosenhouse adds that most puzzles in this book are less “bite-sized” than the ones typically posed by the master Gardner. This certainly goes for the title puzzle about whether a bicycle can possibly move along a curve—other than a straight line—that was made by a unicycle. It requires a foray into differential equations.

## Open Problems

My “uncool solution” was left somewhat incomplete. Do you see how to complete the analysis?

[some word fixes]

September 22, 2020 5:24 pm

The cool solution for the first problem has the extra benefit that it doesn’t even use the restriction that checkers cannot be stacked.

September 23, 2020 8:23 pm

I think you’re wrong.

September 23, 2020 3:29 am

The “cool solution” for the first puzzle can yield the slightly stronger result that it is not possible to remove all checkers from the 6 cells in the first 3 diagonals (i, j) with i+j <= 4.
To make it work, it should also be observed that at any time there is exactly one checker on the bottom line and one on the left column.

Also, in the "uncool solution", the configuration with one checker at (3,2) can also be obtained from a previous state with two checkers on (3,3) and (3,2), which adds a few more branches to the study.

3. September 23, 2020 12:57 pm

I’m confused about the last two solutions. If state n has a single checker at (3,2), then it seems that state n-1 could have checkers at (3,3) and (3,2).

More directly, if I play this game with the rules changed to “any checker outside of C is thrown away”, it’s possible to remove all checkers from C (and indeed the next-to-next-to-last state has checkers at (3,3) and (3,2)). That suggests that the brute-force finite automaton approach won’t work.

It looks like the impossibility fundamentally relies on the infinite board. Did I misunderstand the puzzle?

September 24, 2020 11:02 am

Dear Scott:

I did get it wrong…opps

Thanks for the comment

Best

Dick

September 24, 2020 4:59 am

I’m not sure I believe your suggested automaton approach. The problem is that if checkers outside the domain are “thrown away”, then you can’t ensure that in later steps checkers near the border can actually be placed legally. In fact, I programmed up your approach with automata and it finds “solutions” with 19 moves that are not actually solutions.

September 24, 2020 11:01 am

Dear Jeff and Scott and others:

Oh my….Looks like I made a error. Thanks for the comments. Will get back later on.

Best

Dick

September 25, 2020 9:26 am

Regarding the prime representation puzzle. If we have two factorizations p=ab=xy, then p=(a*(b-x)) * (b*(y-a)) / ( (b*(y-a)) – (a*(b-x)) ), or equivalently, 1/p = 1/(a*(b-x)) – 1/(b*(y-a)). And it is relatively straightforward to see these are the only representations. Therefore, the number of such representations of p is equal to the square of its representations as product of two integers. If we restrict to 0<a<b and 0<x<y then it is unique exactly when p is prime.

I think that calling it a 'complex proof' is a bit too much.

September 25, 2020 12:26 pm

Dear Cristóbal Camarero:

Thanks for this comment.

$p=ab=xy$, then $1/p = 1/a(b-x) - 1/b(y-a)$.

Best

Dick

October 11, 2020 7:39 am

Here is yet another solution to the Solitaire Problem which I figured out together with Ronja Tiling, a student of mine at EFG Euskirchen (before looking at the cool or any other solution from this website).

We define $L(i,j)$ in such a way that it is a lower bound on the number of pebbles that have to be moved away from square $(i,j)$ before the $3\times 3$ left lower corner can become empty.

Inside the $3\times 3$ square the values $L(i,j)$ are $1,1,1$ on the bottom line, $1,2,3$ and $1,3,6$. Outside this square,
$$L(i,j)=\left\{\begin{array}{ll} 0 & \mbox{if i=0 or j=0}\\ \max\{L(i-1,j)+L(i,j-1)-1,0\} & \mbox{otherwise} \end{array}\right.$$
Now by taking into account only the squares on the diagonal and the squares next to the diagonal, one obtains the following lower bound $D(i,i)$ for the number of pebbles that have to be moved from square $(i,i)$ before the $3\times 3$ corner can become empty:
$D(3,3) = 6$, and
$$D(i,i) =2\cdot (D(i-1,i-1)-1)-1 = 2\cdot D(i-1,i-1)-3$$
for $i>3$.
It is now easy to check that $D(i,i)$ goes to infinity as $i\to\infty$, whence an infinite amount of time is required before the left lower $3\times 3$ square can become empty.

Best regards

Mathias