\documentclass[11pt]{article}
\include{18313-preamble}
\usepackage{graphicx}

\begin{document}
\lecture{2004/05/03}{Dan Ports}{2004/05/04}{drkp@mit.edu}
\lecturetitle{The Shoelace Problem}{J. H. Halton. The Mathematical
  Intelligencer, 1995}{Anna Bergren and Anna Kuperstein}{Dan Ports}
\bibliographystyle{IEEEtran}

In Monday's lecture, we saw that the standard American shoelacing
method (Figure~\ref{fig:american}) is the most efficient, in terms of
required shoelace length. It was not only the most efficient of the
three lacings we considered, but the most efficient of all possible
lacings. While looking for a copy of this article, I stumbled across a
reference to an article in Nature \cite{polster} that claims that the
most efficient lacing, again in terms of the required lace length, is
the bowtie lacing (Figure~\ref{fig:bowtie}). Obviously this is a
contradiction. How, then, do we resolve it?

\begin{figure}[htbp]
  \centering
  \includegraphics[width=2in]{18313-l4-american}
  \caption{American lacing}
  \label{fig:american}
\end{figure}
\begin{figure}[htbp]
  \centering
  \includegraphics[width=2in]{18313-l4-bowtie}
  \caption{Bowtie lacing}
  \label{fig:bowtie}
\end{figure}
\begin{figure}[htbp]
  \centering
  \includegraphics[width=2in]{18313-l4-trivial}
  \caption{Trivial lacing}
  \label{fig:trivial}
\end{figure}

The obvious difference between the bowtie lacing and the others we
discussed (the American, European, and Shoe-Shop clacing methods) is
that the bowtie lacing has adjacent eyelets on the same column
connected directly. The other three lacings we considered do not;
indeed, this is specifically prohibited in the problem we
discussed. The Polster article relaxes the constraint that the lace
must alternate between eyelets in each column. It does not entirely
eliminate that constraint, however, because if it did we could use the
more efficient (and entirely useless) trivial straight lacing in
Figure~\ref{fig:trivial}.

Thus there is no contradiction between the results; the complexities
of this problem arise from the different definitions of what is
allowable.

The Polster article defines an \emph{$n$-lacing} of a shoe to be a
closed path in the plane that consists of $2n$ line segments whose
endpoints are the $2n$ eyelets of the shoe, such that for each eyelet
in the shoe, at least one of the two other eyelets connected to that
eyelet is not in the same column. He defines a \emph{dense $n$-lacing}
to be a $n$-lacing where both segments ending in any eyelet are in the
other column. The latter definition is the one that the Halton article
uses.

Polster claims that ``using the symmetries of the configuration of
eyelets, it is possible to design a powerful list of local shortening
rules and to use them to identify the bow-tie $n$-lacings as the
shortest $n$-lacings'', and ``furthermore, by generalizing earlier
results, we can show that the criss-cross [American] $n$-lacing is the
shortest dense $n$-lacing, even if the eyelets are not fully
aligned.'' \cite{polster}. This is not an entirely satisfying
explanation, but the result is not too surprising: we showed earlier
that the American lacing is the shortest dense $n$-lacing (since that
was the condition we studied in the lecture), and it seems reasonable
that the bow-tie lacing, which is essentially the American lacing with
``gaps'' --- connections between two adjacent eyelets in the same
column --- placed half the time, whenever they are allowable, should
be the shortest $n$-lacing. Of course, formalizing this requires
plenty of details, including the fact that the bowtie lacing is
slightly different based on whether $n$ is even or odd --- a detail
that doesn't seem particularly interesting.

He also provides the result that the number of $n$-lacings is
\[ \frac{(n!)^2}{2}\sum_{k=0}^{\left\lfloor n \right \rfloor}
\frac{1}{n-k} \binom{n-k}{k}^2 \]
and that the number of dense $n$-lacings is
\[\frac{n!(n-1)!}{2}\]

The latter result is not too surprising, but the former will require
some more thought on my part. Unfortunately, he does not provide a
justification.

\bibliography{18313}
\end{document}