Skip to main content
Home
plus.maths.org

Secondary menu

  • My list
  • About Plus
  • Sponsors
  • Subscribe
  • Contact Us
  • Log in
  • Main navigation

  • Home
  • Articles
  • Collections
  • Podcasts
  • Maths in a minute
  • Puzzles
  • Videos
  • Topics and tags
  • For

    • cat icon
      Curiosity
    • newspaper icon
      Media
    • graduation icon
      Education
    • briefcase icon
      Policy

      Popular topics and tags

      Shapes

      • Geometry
      • Vectors and matrices
      • Topology
      • Networks and graph theory
      • Fractals

      Numbers

      • Number theory
      • Arithmetic
      • Prime numbers
      • Fermat's last theorem
      • Cryptography

      Computing and information

      • Quantum computing
      • Complexity
      • Information theory
      • Artificial intelligence and machine learning
      • Algorithm

      Data and probability

      • Statistics
      • Probability and uncertainty
      • Randomness

      Abstract structures

      • Symmetry
      • Algebra and group theory
      • Vectors and matrices

      Physics

      • Fluid dynamics
      • Quantum physics
      • General relativity, gravity and black holes
      • Entropy and thermodynamics
      • String theory and quantum gravity

      Arts, humanities and sport

      • History and philosophy of mathematics
      • Art and Music
      • Language
      • Sport

      Logic, proof and strategy

      • Logic
      • Proof
      • Game theory

      Calculus and analysis

      • Differential equations
      • Calculus

      Towards applications

      • Mathematical modelling
      • Dynamical systems and Chaos

      Applications

      • Medicine and health
      • Epidemiology
      • Biology
      • Economics and finance
      • Engineering and architecture
      • Weather forecasting
      • Climate change

      Understanding of mathematics

      • Public understanding of mathematics
      • Education

      Get your maths quickly

      • Maths in a minute

      Main menu

    • Home
    • Articles
    • Collections
    • Podcasts
    • Maths in a minute
    • Puzzles
    • Videos
    • Topics and tags
    • Audiences

      • cat icon
        Curiosity
      • newspaper icon
        Media
      • graduation icon
        Education
      • briefcase icon
        Policy

      Secondary menu

    • My list
    • About Plus
    • Sponsors
    • Subscribe
    • Contact Us
    • Log in
    • All tied up

      11 December, 2002
      11/12/2002


      Velcro users of the world, now you will have to go back to traditional shoe laces if you want to use the latest scientific research to secure your sneakers.

      Burkard Polster, a mathematician from Monash University, Australia, has published research into which type of shoe lacing is the most efficient in the journal Nature - the "most efficient" meaning the one that uses the least amount of lace. You might wonder why anyone apart from penny-pinching scrooges would be worried about wasting shoelace, but in fact the Shoelace problem is a restricted version of a much more famous mathematical conundrum - the Travelling salesman problem. This is the problem of finding the shortest route visiting all of a finite number of cities - which would obviously be of interest to any travelling salesmen trying to minimise their time on the road.

      The Travelling salesman problem turns out to be much harder than it appears at first glance - just working out the distance for every possible route between 10 cities would mean 3,628,800 calculations! This is an active area of mathematical research, and none of the methods (known so far) of chosing a route finds the shortest route every time. You can see the latest research at the TSP site at Georgia Tech , including their result for a route touring 15,112 cities in Germany - the largest instance of the problem solved to date. [Editor's note 14/2/2023: This TSP site –http://www.tsp.gatech.edu/index.html – no longer exists.]

      So what does all this mean for our humble shoe? "Given a single lace and a row of eyelets down each side of a shoe I wanted to find out the best ways of lacing shoes in a `reasonable manner', that is, a manner in which the shoelace visits all eyelets and every eyelet actually contributes towards pulling the two sides of the shoe together," Polster said. So just as in the Travelling salesman problem, where now instead of cities you have eyelets, you can consider which lacing is the shortest. But there are some restrictions on the route your lace takes if you don't want your expensive trainers to fall off. For any eyelet there is a segment of the lace that ends in that hole, and a segment that leaves that hole to go to another eyelet. For one of Polster's "reasonable" lacings, each eyelet has to have at least one of these segments connecting to the opposite column of eyelets, so that the lace at each eyelet is helping to pull the two sides of the shoe together.

      Different types of lacing

      Criss-cross lacing, straight-lacing and the controversial bow tie method

      Polster had to consider all the possible lacings of a shoe - quite a task, considering that there are a staggering 51,840 for a shoe with just 5 eyelets on each side! So instead of brute force he used some powerful mathematical optimisation techniques to prove that the shortest "reasonable" lacing was not the more common criss-cross or straight-lacing, but instead a rarely used bow tie method. However this research probably won't have a revolutionary effect on how we tie our shoes, as Polster also calculated which lacing was the strongest , and this time these two traditional methods tied for the honour.

      The travelling salesman problem has all sorts of applications, from the obvious, such as helping tourists taking a road trip to plan their shortest route and parcel pick-up companies to plan the most efficient route for drivers, to the more unexpected, such as telephone network routing and genome sequencing. It is even believed that monkeys intuitively solve this problem when gathering food. But at this time of the year, the one person who surely has the travelling salesman problem on his mind is Santa! Just what is the shortest route that visits every chimney in the world? Hmmm...

      Read more about...
      Travelling salesman problem
      shoelace problem
      • Log in or register to post comments

      Comments

      Anonymous

      19 September 2012

      Permalink

      The Princeton links no longer work.

      • Log in or register to post comments

      Rachel

      21 September 2012

      In reply to Dead links by Anonymous

      Permalink

      Thanks for letting us know, we've updated the article.

      • Log in or register to post comments

      Read more about...

      Travelling salesman problem
      shoelace problem
      University of Cambridge logo

      Plus Magazine is part of the family of activities in the Millennium Mathematics Project.
      Copyright © 1997 - 2025. University of Cambridge. All rights reserved.

      Terms