# What is the best way to lace your shoes? Dream proof.

Welcome to another Mathologer video today's video is about one of my own
mathematical adventures my quest to pin down the mathematically best ways to
lace shoes yes you heard right the guy who only ever wears Birkenstocks and went
on a mathematical shoelace expedition. this goes back to the time when my own
kids were little. teaching them to tie their shoelaces suggested to me to look
at various mathematical aspects of lacing and tying shoes. because, of course,
that's the crazy way mathematicians think. we're always on the lookout for
the mathematical soul of things no matter how big or small. the whole thing
started out as a bit of innocent fun but then i obsessed a bit happens to me
quite a bit and things got out of control.
first i ended up publishing an article about the best ways to lace shoes, a bit
of mathematical fun in the heavy duty journal nature, a fact which made the
evening news on TV here in australia and resulted in a couple thousands of emails
overnight and requests for interviews from all over the planet believe it or
not. two years later i published a whole book about shoeless maths for the
american mathematical society. that's my daughter Lara on the cover,
well her feet anyway. Lara's tying her laces. and that's me up there in the
corner (with hair :) anyway time to get into it. so what's the best way to lace your
shoes?
let's begin by looking at some familiar lacings. there that's a mathematical shoe
a rectangular array of evenly spaced eyelet pairs. looks comfy right? a lacing
consists of the same number of straight line segments as they are eyelets and
these segments form a closed path that visits every eyelet exactly once just
like in this first example. now that's the crisscross lacing that most shoes
come with. here's the second most popular lacing this is the zigzag lacing. and here
are a couple of other examples. weird, hmm, that's a lacing that a friend of mine
actually found in a French shoe shop a couple of years ago. here is something else
you've probably not seen before. and here's one that it's safe to say has
never appeared in a shoe shop. pretty insane right?
well don't worry I didn't send my kids off to school with shoes laced like that.
closed path visiting every eyelet once. but do we really want to call this a
lacing? something's clearly not right. can you pinpoint it? well the problem is
there are eyelets that don't help us with pulling the two sides of the shoe
together. like this one here. right? doesn't do anything! so in a real lacing
we want at least one of the two segments of the path ending in an eyelet, those
ones there, to connect to the other side of the shoe. right? that lacing over there
works. there are also extra special lacings like the two most popular lacing
the criss cross and a zig zag lacings. in these two lacings every eyelet
contributes twice to pulling the two sides of the shoe together. I call such
lacings tight. in other words in a tight lacing every segment of the closed path
connects the two sides of the shoe and there are no vertical segments at all.
this has the effect that as you travel along the lacing you constantly zigzag
back and forth between the two sides of the shoe like this. ok there's zig zag
zig zag...
Okay down to work. I've shown you five different lacings for a shoe with
seven eyelet pairs. so let's list them all. no let's not :)
it turns out there are more than 38 million such lacings, almost 2 million of
these are tight lacings. the number of lacings increases rapidly with the
number of eyelets. for example for God's shoes with 100 eyelet pairs we get in
the order of 10 to the power of 354 different lacings. now
the formula for the exact number of lacings is this scary-looking monster
here. and my first challenge for the keen among you determine the number of tight
lacings of a shoe with five eyelet pairs. remember tight lacings are the ones that
go back and forth. and the challenge for the super keen: what's the general
formula for the number of tight lacings. as always post your answers and
ponderings in the comments. okay so we have our lacings, sort of. that means we
can now ask which of all the gazillions of lacings of a particular shoe is the
very best. of course there are many types of best. people often say french things
are best. so maybe the french shoe shop lacing is best by default? anyway
ignoring the French, I thought there were two natural interpretations of the word
best to consider. first the shortest lacing and second the strongest lacing.
makes sense? anyway it was these two interpretations of best that I went for.
okay so first what is the shortest lacing of a given shoe? easy right
just have a computer list all possible lacings of this shoe and figure out
which one is the shortest. with 38 million lacings and a modern computer
that's definitely not a problem at all. however even with seven eyelet pairs
there are infinitely many different shoes to consider depending on the
spacing of the eyelets. right? and of course as true mathematicians we are
honorbound to consider all infinitely many different spacing of all the
infinitely many different mathematical shoes. shoes with just two eyelet pairs,
three, pairs four pairs etc
all right, for now best means shortest. so what are the shortest ways to lace
shoes. well with all these infinitely many possibilities you'd expect many
structurally different shortest lacings. not true! this came as a real surprise to
me, but no matter the eyelet spacing, the shortest solution is essentially the
same. first the answer for the tight lacings. remember those are the lacings
that zip back and forth between the two sides of the shoe. it turns out the
shortest tight lacing is always the crisscross lacing. so the most popular
lacing also turns out to be the shortest for each of those infinitely many
possible mathematical shoes. nice to know isn't it? the first to prove this
shoelace theorem was the mathematician John Halton in 1995 in an
article in the mathematical Intelligencer, a couple of years before I
got interested in shoelace maths. see I'm not the only one. now what about general
lacings. here it turns out the absolutely shortest lacing is always what I call a
bowtie lacing. bowtie lacings have horizontal segments at the top and at
the bottom and the rest of the segments come in pairs, either making short
parallel pairs like this. 1 2 3. or short crosses like this. 1 2 3. the basic bowtie
lacing of a shoe starts with a parallel pair at the bottom and then the parallel
pairs and the crosses alternate. okay in the case of an odd number of eyelet
pairs like in the shoe over there, apart from the basic type of bowtie lacing
there are also these variations. there there and there. obviously since they are
just a few segments shuffled around all these variations have the same overall
length and so, if one is of shortest lengths, then all of them are. okay so
this is the situation for mathematical shoes with an odd number of eyelet pairs.
for an even number of eyelet pairs there is only one bowtie lacing just like for
the case of six eyelet pairs, this one here. and this particular instance of
this type of shortest lacing also inspired the name bowtie lacing. look, there is
the bowtie. okay so I've told you the winners of the shortest lacing
competitions. but how would we prove something like this. well most
mathematicians presented with this task will place it within a whole circle of
such puzzles known as the Traveling Salesman problems. let's say you've got a
number of towns, like for example all the major towns in the state of Victoria
where I live. there that's all of them. the Traveling Salesman problem asks for a
shortest round trip that visits every one of these cities once. here is the
solution to this problem. and here's the solution of the same problem for more
than 18,000 towns in Germany. fantastic stuff isn't it and there is one very
striking aspect of these solutions. have a closer look. can you see it? yep I'll
bet a lot of you got it. there's no crossings and that turns out
to always be true. no solution to a Traveling Salesman problem will ever
intersect itself. it's actually really easy to see that crossings can't happen.
just imagine if it did. then we'd have a closed path that intersects itself
somewhere like this. color the crossing segments like this. but now it's clear
that if we replace both the blue and green parts by straight-line segments we
get a shorter closed loop through all the points. that means any closed path
with an intersection like this can always be shortened and so the shortest
closed path, the solution to our travelling salesman problem, cannot have
any self intersections. back to our shoes. what is the solution to the travelling
salesman problem for a shoe. yep it's just the boring non lacing loop that we
stumble across earlier. so how can insights about the general traveling
salesman problem help solve our shortest shoe lacing problem? well have a look at
this lacing. can this possibly be a shortest lacing? doesn't seem likely, does
it? and we can actually prove that it's not the shortest. we can create a shorter
lacing just by doing a little bit of rewiring and straightening just like in
the Traveling Salesman problem. right, there, straighten and we've got something
one be the shortest? nope we can shorten again with some more rewiring.
right, just straighten out the green and blue bits. voila, once again a
here we go again. okay, and shorter, oh damn no lacing, but we could fix that. all
good. so finally after three rewiring we've ended up with one of our bowtie
lacings. this rewiring idea was at the heart of my first proof that the bowtie
lacings are the shortest. very simple idea right? but in the end to completely
nailed down the proof it was a bit tedious because of the ridiculous number
of different cases that had to be considered. there just to give you an
idea that's one of the diagrams listing two different cases in one part of the
proof. of course I was pretty happy of having found my rewiring proof but
somehow my brain subconsciously kept working on the problem and about six
months after I finished the first proof I woke up one morning in the middle of
dreaming about another much shorter proof. now pretty much all mathematicians
have had dream proofs and it's wonderful: you wake up really excited and then two
minutes later you realize your dream proof is completely ridiculous just like
your dream of suddenly being able to levitate or co-starring in a movie with
Scarlett Johansson. but amazingly my dream lacing proof really worked. for the
really keen ones among you I'll illustrate a special case of my dream
proof at the end of this video, proving to you that the crisscross lacing is the
shortest tight lacing. before that let me show you some other really neat shoelace
facts. remember my shoeless book? have a look at the subtitle "a mathematical
guide to the best and worst ways to lace your shoes" yep I also pinned down things
like the longest lacings among the different classes, I know, pretty strange
but totally the thing to do if you are a mathematician. just like worrying about
lacings with a hundred eyelet pairs. and what turns out to be the longest tight
lacing? behold there devil lacings!
pretty devilish, huh? here are the devil's for small shoes up to six eyelet pairs.
and what are the longest lacings overall. well for short shoes shoes with
short horizontal spacing the longest placings are still the devil lacings. for
long shoes, shoes with long horizontal spacing those are the angel lacings. I've
drawn the wings curved to make the pictures less ambiguous and more angelic :)
fun? no? well, I don't care. I think it's fun. but what about real shoes I hear you
ask, like those on the cover of the book? real shoes aren't flat, eyelets aren't
points, laces are made up of line segments, and so on. well, it turns out
that the shortest lacings for ideal mathematical shoes are surprisingly
robust and are also the shortest lacings for most real shoes. this is particularly
true for the shortest tight lacings, the crisscross lacings. at least for any shoe
I've ever owned the crisscross lacing has always been the shortest tight
lacing. but if you're really tired of my pure mathematical weirdness and you want
to find out everything conceivable and inconceivable about real shoelaces I've
got just the site for you. you absolutely must visit Ian's shoelace site which my
friend Ian Fieggen has been obsessing over for ages. insane lacings, ways to tie
laces, shoelace books, shoelace apps. etc yep, I am the pure shoelace nut, Ian is the
applied shoelace nut :) the weirdest thing is that Ian lives just a couple of
kilometres away from me here in Melbourne. that definitely makes
Melbourne the shoelace capital of the world, doesn't it? now your next easy
challenge for the day: head over to Ian's website and find out whether you belong
to the half of the people on Earth who are tying their shoelaces incorrectly.
intrigued?
okay after meeting with Ian we're definitely in good shape with the
shortest and longest lacings. so what about the strongest lacings? also
strongest in what sense? I'll postpone the 'in what sense' and just
start by telling you the surprising answer to the first question. what are
the strongest lacings? it turns out that the two most popular lacings the criss
cross and a zigzag are also the strongest lacings for short shoes, like
the one over there. the strongest lacing is the criss cross lacing as you stretch
the shoe. the strongest lacing stays criss-cross up to a certain changeover
point. at this point the criss cross lacing is as strong as the zigzag
lacing. stretching beyond the changeover point, the zigzag lacing is uniquely
strongest. this basic behaviour is the same no matter the number of eyelet
pairs. just the changeover spacing changes with that number.
the more eyelets there are the quicker we reached the changeover spacing.
okay so you know the strongest lacings, you just don't know what
strongest means. so I'll tell you. have a look at this picture. see the pulley on
the right? ideally a lacing is a pulley like this turned sideways. when a shoelace
is tied we assume ideally that the tension everywhere along the shoelace is
the same. this tension then translates into the tension of the pulley in the
horizontal direction that is the direction in which the two sides of the
shoe are being pulled together. so for a given tension throughout the lace then
the larger the horizontal pulling tension the stronger we say the lacing
is. proving that the crisscross and zigzag laces are strongest is super
nitty-gritty and also only really became feasible after I had my dream. so let's
to finish off I want to show you my dream proof. really quite special, a proof
hatched in a dream that isn't completely crazy and actually works. that had only
happened to me once before. in what follows I'll focus on proving to you
that the crisscross lacing is the shortest tight lacing of the shoe over
there. this proof is completely general and works for any number of eyelets and
any spacing. anyway on to proving that the crisscross lacing is the shortest tight
lacing. what I'll do first is to just give you an outline of the proof. while I
go over this outline, don't get hung up on any details. just run with it and try
to understand the gist of what's going on. I'll flesh out the details afterwards
and things should come together nicely then. okay let's say over there that's a
list of all our tight lacings. let's explode all of them into the different
segments they consist of. there, explored explore explored, and so on. we'll see
that these segments collections resulting from the explosion of tight
lacings share four easy to see properties. first each collection consists of ten
segments. second each collection has at most five horizontals. I'll tell you the
remaining two properties in a minute. now what we can do is to study these
collections in their own right, to have a close look at all collection of segments
that satisfy these four special properties. why do that? wait and see. I've
named these special collections exploded lacings. apart from the exploited
lacings arising from real shoes we see that there are lots of others, like for
example this one here. the length of an exploded lacing is
just the sum of the lengths of all its segments. this means that the length of a
real lacing is the same as the length of its exploded counterpart. pretty obvious
right? now comes the nifty part of the proof and the whole point of this
exploded stuff. although there are a lot more exploded lacings than the real
lacings we started with it will be extremely easy to figure out what the
shortest exploded lacing is. why is that? well it comes from the overall lack of
structure of exploded lacings which makes them very easy to manipulate. the
shortest exploded lacing turns out to be the explosion of the crisscross lacing
consisting of two horizontals and eight short diagonals. it's also easy to see
that the crisscross lacing is the only tight lacing consisting of two
horizontal and eight short diagonals. consequently since the exploded
crisscross lacing is shortest among all explored lacings the crisscross lacing
must be the shortest real tight lacing. really cool. so my dream proof dodges
all the complicated structure of lacings by taking a shortcut through some
strange world of phantom lacings. how neat is that? only in a dream :)
first let's give number labels to the different segment types that can occur.
we'll call horizontal segments zeros. next we call segments that rise exactly one
vertical step 1s that's a 1 there and that's another one. and you can guess
the rest. the segments that rise 2 vertical steps are the 2s and there
are 3s and finally there 4s. 4s are the longest possible segments for
our particular shoe. so our crisscross lacing consists of two
0s, the horizontals at the top and the bottom, and eight 1s. the zigzag
lacing consists of five 0s four 1s and one 4 now. here are four simple
properties shared by all the sets of numbers that correspond to lacings. first
as we've already mentioned all these lacings consist of 10 segments so there
are 10 numbers, 10 non-negative integers. second, the 4s are the longest
possible segments and so 4 is the largest possible number. third and again
we already noted this there will be at most five horizontal segments. that means
we'll have at most 5 zeros. fourth, and finally, the distance between the top and
the bottom of our shoe is four spaces and traveling around the lacing you must
go at least once from top to bottom and back from bottom to top. this means that
the sum of our lacing numbers is at least two times 4, that's 8. okay so let's call
any set of non-negative integers that satisfies these four properties an
exploded lacing. so for example this is an exploded lacing. let's check 10
non-negative integers, tick. nothing bigger than 4. tick. at most five zeros. tick.
and finally the sum of the numbers is 23 which is greater than 8. tick. obviously
in a real lacing there at most two of the long 4-segments. so since our
exploded lacing contains four4s it cannot correspond to real lacing. in
fact, as I already mentioned in the intro, many exploded lacings do not come from
real lacings. okay getting there. now remember the lengths of an exploded
lacing is simply the total sum of the lengths of the segments corresponding to
the numbers. for example, for our exploded lacing here there are three 0s
contributing the length of three horizontals. add to that the length of a
one segment plus two times the length of a three segment and, finally, add four
times the length of a four segment. all under control.
easy enough so far right? okay and now for the easy proof that exploring the
crisscross lacing gives the shortest exploded lacing overall.
three easy peasy steps. first a shortest exploded lacing has sum exactly equal
to 8. why? because any exploded lacing that has
a sum greater than 8 can be made into a shorter exploded lacing by
replacing some of its numbers by smaller numbers. for example in our exploded
lacing here we can make these replacements. two plus three plus one
plus one plus one that's eight. now second easy step. because there are 10
non-negative integers that add to 8 they cannot all be 1 or greater. this
means some of these numbers must be 0s right? Let this sink in.
all okay? good! so that means a shortest exploded lacing contains zeros. third and
final easy-peasy step. okay so maybe not so easy peasy but it's not too bad,
you'll see. think again about our exploded crisscross lacing. it contains
only 0s and 1s. now can a shortest exploded lacing contain a number greater
than 1. let's see. in our example there is a 3. let's grab this 3 and one
of the 0s and picture them together. can you see how to shorten what we're
looking at here? yep just a little traveling salesman rewiring and
straightening. here we go. there the green is a 2 and the pink is a 1. this
means that if we replace the 0 and the 3 in our exploded lacing by a 1 and a 2 we
get a shorter exploded lacing right. also notice that the sum of the numbers
in this new lacing is still 8. one plus two plus two plus one plus one plus
one is eight. can we shorten our new exploded lacing again? absolutely! we
can use the same trick to replace a 0 and a 2 with two 1s like this.
yeah that's a 1 and a 1. replace. ok repeating this step once more we can get
rid of the other 2, the last number greater than 1. go for it ... exactly same
step right. two ones. replace. there so now we're totally down to zeros and
ones. and this always works. we can always shorten until there are
only zeros and ones. and so the shortest exploded lacing overall must contain
only zeros and ones. but since the sum is 8
there must be exactly 8 ones and two zeros. this means that the shortest
exploded lacing is the exploded crisscross lacing. Tada! pretty cool dream
proof. well actually there's one more t to cross. last thing we do. we've proved
that every lacing consisting of two zeros and eight ones is a shortest tight
lacing and the crisscross lacing is definitely one such lacing but maybe there
are others. well let's see. okay time to play with our building
blocks. what can we make with our two zeros and eight ones. let's start at one
corner eyelet. we must have exactly two segments meeting at that eyelet and the
segments must be different. so for that corner eyelet it's clear that one of the
segments is a zero and the other is a one. so one of the zeros has to be at the
bottom. similarly looking at a top corner the other zero must be located at the
top. but now our hands are forced. all we have left are ones and we have no choice
in how to place them. there and there and there and there and that really finishes
the proof, very nice isn't it. and as I said it's very easy to adapt the arguments
that I just presented to also prove that the bowtie lacings are the shortest
lacings overall. and my proofs of the strongest lacing theorems are also based
on exploded lacings. so mathematical dreams can become mathematical reality.
who would have thought? and that's all for today. pleasant dreams :)