The shoelace problem

DOI10.1007/BF03024786MaRDI QIDQ1903418zbMATH OpenOpenAlexFDO

Authors John H. Halton

Publication date 10 March 1996

Published in The Mathematical Intelligencer (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf03024786

zbMATH Keywords

shortest pathtraveling salesmanzig-zag lacing

Mathematics Subject Classification ID

Recreational mathematics (00A08) Programming involving graphs or networks (90C35)

Review text

In a number of discussions of how shoes should be laced, it became apparent that no one seemed to have the definitive answer. Shoes were laced and relaced, passions flared, and shoes were even thrown\dots. The author decided that an appeal to mathematics was indicated. This problem is a restriction of the Traveling Salesman Problem. We are given a set of \(2(n+ 1)\) points (the lace-holes or eyelets) arranged in a bi-partite lattice. The problem is to find the shortest path passing through every eyelet just once, in such a way that the points of the `right' and `left' holes alternates. The author compares three `popular' lacing strategies and proved the minimality of the ordinary zig-zag lacing.

Recommendations

• Lacing irregular shoes
• The Shoelace Book
• Mathematical entertainments: Problems and patterns
• PLANAR LACES
• What is the minimum length of a non-extendable lace?

Cited in

(6)

• What is the minimum length of a non-extendable lace?
• Polynomially solvable cases of the bipartite traveling salesman problem
• Lacing irregular shoes
• The Sock Problem Revisited
• The Shoelace Book
• The bipartite travelling salesman problem: a pyramidally solvable case

This page was built for publication: The shoelace problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1903418)