The Shoelace Problem

How should shoes be laced? This seemingly simple question, rooted in everyday life, can provoke passionate argument—and evoke a mathematical response.

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 computer scientist John H. Halton. 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").

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)√(d² + g²)

European: (n − 1)g + 2√(d² + g²) + (n − 2) √(4d² + g²)

Shoe store: (n − 1)g + (n − 1) ✕ √(d² + g²) + √[(n − 1)2d² + g²]

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").

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 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.

Here are some alternative lacings you could try. The first two work only if your shoes have an even number of eyelet pairs. Watch out, though. You might find that by saving shoelace length, you end up with shoes that slip off your feet more easily or laces that break more often.

Mathematician Burkard Polster later revisited the shoelace problem. He argued that the lacing that uses the least amount of lace is a rarely used and unexpected type that he described as a "bowtie" lacing.

Bowtie lacing.

In his model, Polster considered an arrangement of 2n eyelets, situated at the points of intersection of two vertical lines and n equally spaced horizontal lines. He specified that the shoelace visit all eyelets and that every eyelet contribute toward pulling the two sides of the shoe together. Polster then defined a "dense" lacing to be one that zigzags back and forth between the two columns of eyelets, as in the standard American lacing.

This model revealed that there are several other "reasonable" ways of lacing shoes. Of these, the bow-tie method is the most efficient in terms of requiring the shortest lace yet using all the eyelets. However, the two traditional "dense" styles win when you're looking for the strongest lacing—that is, the one that gives the maximum tension on both sides of the shoe.

Which of the two is stronger depends on the distance between the two rows of eyelets: zigzag when the eyelets are close together and straight when they are farther apart.

Hundreds of years of trial and error have led to the strongest—if not the most efficient—way of lacing our shoes, Polster concluded. That's in the face of a staggering 51,840 possible lacings for a shoe with just five eyelets on each side, and millions more for shoes with a larger number of eyelet pairs!

For the definitive guide to lacing, see Polster's book: The Shoelace Book: A Mathematical Guide to the Best (and Worst) Ways to Lace Your Shoes (AMS, 2006).

Originally posted December 23, 2002