| | Ivars Peterson's MathTrek |
February 8, 1999
There are at least three common ways to lace shoes, as illustrated below: American (or standard) zigzag, European straight, and quick-action shoe store. Which lacing style a person uses depends on a variety of factors, ranging from aesthetic appeal to tying efficiency.
Indeed, lacing patterns can be quite complex, and different patterns require different lengths of lace. For the sake of conserving fiber, one might wonder which lacing pattern requires the shortest laces.
That was the question tackled by John H. Halton, a computer scientist at the University of North Carolina at Chapel Hill. The shoelace question represents a special, restricted instance of the classic traveling salesman problem, in which a salesman must visit customers in a number of cities scattered across the country and then return home following the shortest possible route visiting each city only once (see The Traveling Monkey, July 7, 1997).
In the shoelace problem, you have to find the shortest path from the top eyelet (or lacehole) on one side to the top eyelet on the other side, passing through every eyelet just once. Having ventured into the realm of mathematical modeling, you can idealize the lace to be a mathematical line of zero thickness and the eyelets to be equally spaced points arranged in two columns.
It's then possible to calculate the length of lace in terms of the number n of pairs of eyelets, the distance d between successive eyelets, and the gap g between corresponding left and right eyelets.
Applying the Pythagorean theorem and a little algebra, you end up with the following lace lengths:
American: g + 2(n - 1)
(d2 + g2)
European: (n - 1)g + 2(d2 + g2) + (n - 2) (4d2 + g2)
Shoe store: (n - 1)g + (n - 1) x (d2 + g
2) + [(n - 1)2d2 + g2]
It turns out that if n is at least 4, the shortest laces are always American, followed by European, then shoe store. For n = 3, American remains shortest, but European and shoe-store lacings are of equal length.
Instead of taking an algebraic approach, however, Halton used a shortcut inspired by the geometry of paths traced by rays of light. The trick is to think of the lacing pattern as the path of a light ray reflected back and forth between a pair of mirrors. You can imagine that every time the ray hits an eyelet position, it continues in its original direction through a virtual lattice of points created by reflecting the original lattice of pairs of points in the mirror (see Mirror Bounces, May 26, 1997).
In effect, instead of zigzagging, the lacing path is reflected at each eyelet so that it is straightened out as much as possible. By plotting such paths on a rectangular lattice, it's easy to see that the American lacing is the straightest and, hence, the shortest.
Halton went to demonstrate that the American zigzag lacing is the shortest among all possible lacings. Michal Misiurewicz of IUPUI in Indianapolis later proved that the eyelets don't necessarily have to be arranged in two parallel rows with equal distances between consecutive eyelets for that to be true. Even when the eyelets are irregularly arranged, the standard lacing is shorter than any other lacing.
It turns out, however, that shorter lacings are possible if the lace doesn't have to pass alternately through the eyelets on the left and right side of the shoe.
Copyright 1999 by Ivars Peterson
References:
Gale, D. 1998. Tracking the Automatic Ant and Other Mathematical Explorations . New York: Springer-Verlag.
Halton, J.H. 1995. The shoelace problem. Mathematical Intelligencer 17(No. 4):36.
______. 1992. The shoelace problem. Department of Computer Science Technical Report No. 92-032, University of North Carolina at Chapel Hill.
Misiurewicz, M. 1996. Lacing irregular shoes. Mathematical Intelligencer 18(No. 4):32.
Stewart, I. 1996. Arithmetic and old lace. Scientific American (July):94. Feedback in Scientific American (December):118.
Comments are welcome. Please send messages to Ivars Peterson at ipeterson@maa.org