You are here

American Mathematical Monthly - November 1999



A Modern Treatment of the 15 Puzzle
by Aaron F. Archer

In the 1870's the impish puzzlemaker Sam Loyd caused quite a stir in the United States, Britain, and Europe with his now famous 15-puzzle, by offering a $1000 prize to perform a feat that turns out to be mathematically impossible. The puzzle consists of sliding blocks in a tray, and the object is to achieve certain arrangements of the blocks, starting from the initial position shown in the figure. An editorial comment in an 1879 issue of the American Journal of Mathematics claimed that over the preceding weeks, the puzzle "may safely be said to have engaged the attention of nine out of ten persons of both sexes and of all ages and conditions of the community" and "may almost be said to have risen to the importance of a national institution."

The puzzle has inspired numerous mathematical treatments over the years, most of which prove the relatively simple fact that odd permutations of the blocks are impossible to achieve, and many of which mention the surprising fact that all even permutations are possible. However, proofs of this result are hard to find in the literature. In their book Matters Mathematical, I. N. Herstein and I. Kaplansky write that "No really easy proof seems to be known." This article intends to rectify that deficiency with a short, simple, elementary proof, based on defining equivalence classes via a hamiltonian path.

The 15-puzzle can be generalized to a puzzle of swapping vertex labels on a graph. The method presented here can be applied to any graph containing a hamiltonian path. We conclude by discussing an elegant (but non-elementary) result of R. M. Wilson that characterizes all obtainable labelings in any arbitrary graph.


Effects of Calculus Reform: Local and National
by James F. Hurley, Uwe Koehn, and Susan L. Ganter
With support from the National Science Foundation and Connecticut's Elias Howe High-Technology program, during the period of 1988-93 the University of Connecticut Department of Mathematics developed and implemented a computer-integrated first-year calculus sequence. One tool to measure its impact was a common final examination for all students in both experimental and traditional sections, all of which used the same text. Those examinations included significant conceptual emphasis but no project-specific material. In every case, the mean score in the experimental sections was higher.

A five-year longitudinal study tracked the subsequent academic careers of students who took calculus in the project's first year. It measured persistence in mathematical, scientific, and engineering majors by analyzing completion rates of key post-calculus courses in those majors. Students from the project's sections completed an average of nearly 50% more of those courses. Enrollment in project calculus sections was (with SAT mathematics score) one of only two factors to correlate significantly with persistence in technical majors. For female students, background in project calculus was the only statistically significant factor to correlate with such persistence.

Circulation of a preliminary version of the paper, by the first two authors, raised the question of how representative Connecticut's experience was. Studies by other projects, which yield some similar results, are discussed. The third author's collection and analysis of data from across the nation provides a basis for discussion of the more general impact of calculus reform, and the kind of additional studies appropriate to assessing the final effect of the calculus-reform movement.


The Dirichlet Problem for Ellipsoids
by John A. Baker
The problem of the title is solved, in arbitrary dimensions, in the case of polynomial boundary data by invoking a simple and elegant, eighty year old result of Ernst Fischer (of Riesz-Fisher fame). Using that special case, the general problem (involving arbitrary continuous boundary data) is solved by appealing to the Weierstrass Approximation Theorem and the Mean-Value Theorem of harmonic function theory.


Some Fundamental Control Theory II: Feedback Linearization of Single Input Nonlinear Systems
by William J. Terrell
This is Part II of a two-part article that introduces some basic mathematical ideas in control theory, approached via a natural question in elementary differential equations. We consider the question of equivalence, via local coordinate change and state feedback, between an n-dimensional scalar input nonlinear system and the simple n-th order linear equation y (n) = v having input v. The solution of the equivalence problem provides a significant entry point into the literature of nonlinear control. The exposition shows connections among topics in differential geometry required for the case of Frobenius' Theorem needed for the equivalence problem.


Curves Whose Curvature Depends on Distance From the Origin
by David A. Singer
The existence and uniqueness theorem for curves in Euclidean space says that a curve is determined up to rigid motion by its curvature and torsion, given as functions of arc length. The actual equations for such a curve are linear but may be difficult to integrate in practice; in the case of planar curves this is not a problem. In this paper, we consider curves whose curvature is given in terms of the distance from a fixed point rather than in terms of the arc length. The resulting equations are non-linear, so even the planar case may be a challenge to integrate. We show how to solve this problem by formulating it in terms of motion under a central force. We present the particular case of curves whose curvature is equal to the distance from the origin; one of these curves is familiar.


The Fifty-Ninth William Lowell Putnam Mathematical Competition
by Leonard F. Klosinski, Gerald Alexanderson, and Loren C. Larson


On the Nelson Unit Distance Coloring Problem
by Carsten Thomassen

Descartes' Rule of Signs: Another Construction
by David J. Grabiner

Integrating Polynomials in Secant and Tangent
by Jonathan P. McCammond


Field Theory: From Equations to Axiomatization. Part II
by Israel Kleiner



African Fractals: Modern Computing and Indigenous Design.
By Ron Eglash

Reviewed by James V. Rauff