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 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 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:
- 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 is less than .
Then there can never be a reachable state that avoids all the lower . How can we do this? Assign the values as shown below.
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 be the lower-right corner board. Label the positions as usual with where both are in .
Let be the number of checkers in at time . Of course and the checker is at .
Suppose by way of contradiction that it is possible to make empty.
Our proof uses that the transition from to requires that . That is or even is impossible. The rule cannot remove two or more checkers from in one move.
Let and . So where is the checker? A simple case analysis shows it must be at . 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 or . By symmetry we can assume was .
Our goal to show that we cannot place one checker at and no other in . A little analysis shows that it must be the case that the previous state was one checker at . 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 . When we have a move that creates checkers outside of just throw them away. It is simple to see that no move can place checkers inside . Thus if we cannot empty in this finite version, then there is no way in the full game.
Now the state space is bounded by : 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 has determinant . The particular matrices look like they could have some strange determinant, one that even varies with . The trick is to show that there are other families and of matrices, in which each matrix has determinant and that
Of course this immediately proves that also have determinant . The challenge is kind of a factorization problem.
Another puzzle is to prove that a number is prime if and only if there is exactly one pair of positive integers such that
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.
, then .
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