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. how about this one here? well seems to
fit the bill right: the lace forms a 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 shorter. okay
what about this new lacing? can this 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 shorter lacing. what about this third
lacing? well I'm sure you can guess and 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 talk about that now. 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 :) okay ready for the details? ready or not
here we go. 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 :)
