The shoelace problem (Q1903418)

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.