Puzzle Reviews by a Puzzle Writer
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 
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 
- The computation is nondeterministic. There can be more than one next state.
- 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:
-
The value of the initial square is
.
- The value of a move leaves the total sum over all the checkers the same.
-
The value of the squares not in the lower
Then there can never be a reachable state that avoids all the lower
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 
Let 
Suppose by way of contradiction that it is possible to make
Our proof uses that the transition from 
Let 
Our goal to show that we cannot place one checker at 
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
Now the state space is bounded by 
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 
Of course this immediately proves that
Another puzzle is to prove that a number 
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]
The cool solution for the first problem has the extra benefit that it doesn’t even use the restriction that checkers cannot be stacked.
I think you’re wrong.
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.
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?
Dear Scott:
I did get it wrong…opps
Thanks for the comment
Best
Dick
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.
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
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.
Dear Cristóbal Camarero:
Thanks for this comment.
I added the latex for your key step.
Best
Dick
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