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 :)