Welcome to another Mathologer video. See that book
over there? It's called Récréation mathématique and it's a 17th-century version of mathologer. Yep
once upon a time long ago people would read books for their recreational mathematics. Published
in 1626 Récréation mathématique is a collection of fun maths problems devised by some jesuit
priests while organising their annual open days. Who would have thought they had open days way back
then. Anyway just like some famous and infamous maths videos recreational mathematics went viral.
More than 70 editions and translations appeared over the next century. It's a cool book but I have
a special reason for introducing it to you today. Towards the end of Récréation mathématique we
find the first-ever recorded instance of the mega-famous pigeonhole principle. A very simple
and yet incredibly powerful proof technique. What I want to do today is to explain to you
the pigeonhole principle and to present my top seven favourite applications of pigeon-based
mathematics. I'll start with a very famous and very hairy example from that dusty book over
there. Then we'll have a problem with pigeons on a sphere, a pigeon-powered explanation of
recurring decimals, some party maths, a very twisty property of the Rubik's cube, a puzzler
from the 1972 international mathematical olympiad, and finally what some people consider to be
the best mathematical card trick of all time. Lots of fun aha moments ahead, promise. Okay so to start the hairy ball rolling let me ask you a question: are there any
hair doppelgängers in Australia? Strange. In other words are there two Australians who
have exactly the same number of body hairs? Okay, that's an easy one since two people with no hair
at all will have the exact same zero hairs. And it turns out that there are quite a few such people.
Since alopecia universalis a medical condition that results in the loss of all body hair
affects about one in four thousand people. Okay so let's change the question and just
consider people who have some body hair. So are there two hairy Australians with
the exact same number of body hairs? What do you think? How could you possibly
find the answer to this question? Well, ask everybody in Australia to stand still
while one by one we count all their hairs? Australians tend to be a sporty lot and
standing still is not their forte. So maybe not. Well, it's actually very easy to decide
this question in a very sneaky way. First of all, let's figure out roughly
how many hairs we're talking about. The average number of hair follicles on
a human body is about 5 million. So it's probably safe to say that the absolute hairiest
Australian has no more than 6 million hairs. Next evacuate six million Australian houses
and label them one two three up to six million. There, that's house number six million at the
bottom. Now imagine moving all the Australians, all 24 million of them, into these six
million houses. Each Australian counts the number of hair on their body and moves into
the house with the corresponding number. Got it? 24 million Australians crammed into six million
houses. Obviously that means at least one house, probably tons of them will end up with more
than one occupant, right? But what does it mean for two people to be in such a house? Yep,
it means those people have the same number of hairs as the number of that house and so
the same number of hairs as each other. We just proved that at any moment in time there
are hair doppelgängers in Australia. Amazing argument isn't it? Really no work at all. And
as well as amazing the argument is really weird. Think about it, although we can be absolutely
certain that Australia has hair doppelgängers the argument gives us absolutely no clue about
how to find such hairy twins. Very strange. There's also another thing the argument fails to
tell us. Take any hairy individual, say Einstein there, then the argument doesn't promise us that
Einstein ever had a hair doppelgänger anywhere in the world. As I said the argument itself is
usually referred to as the pigeonhole principle and you can probably guess the origin of the name
right? If there are more pigeons than pigeonholes, then once all the pigeons are housed at least
one of the pigeonholes has to have more than one pigeon. Pretty obvious. Oh and here's the part
of the 17th-century book that deals with the hair example. If you know a little French it's very
much worth having a closer look not least to find out how exactly a 17th-century Mathologer went
about explaining things to a general audience. I'll link to a digital copy in the description,
as well to as to a nice mathematical intelligencer article about the history of the
puzzle and the pigeonhole principle. Now suppose you have lots of pigeons then you'll
be guaranteed that there's a pigeonhole with plenty of pigeons. To be precise if you have m
pigeons and n pigeonholes then you can be sure that at least one of the pigeonholes
contains at least m over n pigeons. Okay also pretty obvious when you think about
it for a second. So for example with 15 pigeons and six holes, there is at least one hole with 15
divided by 6 pigeons. 15 divided by 6 that's 2.5 okay. And no no pigeons were hurt in the
production of this video we don't deal with half pigeons. So we round up 2.5 to 3 and we
can be sure that once all the pigeons are housed at least one pigeonhole will
contain at least three pigeons. Applied to our hairy Australians we have 24
over 6 that's 4. So we can be sure there is at least one club of four Australians
with the exact same number of hairs. So things are even more hairy in
Australia than they appear at first sight. Okay, let's suppose you have five pigeon
friends scattered around the globe. Can you find a hemisphere containing three of the
pigeons? Yep that's easy right two hemispheres north and south and five pigeons so one of the
hemispheres contains at least three pigeons. True some of those pigeons may be on
the equator but you can also easily avoid that just find a tilted equator that is
a great circle which misses all five pigeons. Then one of the tilted hemispheres created
by that equator will contain three pigeons. But now a tricky one. If you don't mind
including a great circle in a hemisphere you can always arrange to have four
of the five pigeons in one hemisphere. Really? That doesn't sound right, does it?
Here's how you do it. Take any two of your pigeon friends. Then you can definitely find
a tilted equator that contains both pigeons. That leaves three pigeons and so one of the two
hemispheres will contain two of these pigeons plus the two on the equator and you have four pigeons
in a hemisphere. Cool hmm. An easy challenge for you. Say you upgraded to seven pigeon friends
roaming the globe. How many can you guarantee to be contained in some hemisphere plus its tilted
equator? Leave your answers in the comments. Of course, we all know what fractions are: three
over four, five over three and things like that but it gets a little trickier if you
want to express fractions as decimals. Sure three over four is zero point seven five and
five over three equals one point six six,… those two are easy right? Well, we had to sneak in those
infinity dots when no one was looking. But what about 7 over 13? How can we recite that? And is
0.676767… a fraction? Not so obvious. Well as most of you know the fractions are exactly the numbers
whose decimal representations have infinite repeating tails. Wait what? All have infinite
repeating tails? What about three over four? There, no repeating tail? Well the way I look at
it even 0.75 has an infinite repeating tail. An infinite repeating tail of zeros. Anyway if you
include the infinite tails of zeros then the fractions are really exactly those numbers whose
decimal expansions have infinite repeating tails. But do you know why the fractions are exactly
those decimals? I'm guessing quite a few of you don't so let me demonstrate this fraction decimal
correspondence by fitting a flock of infinitely many pigeons into finitely many pigeonholes. Ok,
let's pick a fun fraction like the one over there. Does it look like fun? Maybe not but we'll find
out why this fraction is special when we calculate its decimal expansion. To do that we divide 355
by 113. We all remember our long division right? Okay here we go 113 goes into 355 three
times. Three times 113 is 339 and so we get a remainder of 16. Next, add 0 to make
the 16 into 160. 113 goes into 160 once. 1 times 113 is 113. Okay remainder 47. And
so on. Now we can continue … well forever. Okay so the process is never-ending and
as part of the process we will generate infinitely many of the yellow remainders. These
yellow remainders are our infinitely many pigeons. And what are the pigeonholes? Well, notice
that there are only finitely many values those yellow remainders can be namely the 113
possible remainders after division by 113. So what does the pigeonhole principle
now give us? It promises that at some point of this division process we must come
across one of these remainders a second time. But as soon as this happens the whole division
process will repeat, we'll have entered into a loop which produces the same sequence of digits
over and over and that promises 355 over 113 can be expressed as a repeating decimal. And why is
our fun fraction so much fun. Well, the decimal looks a little familiar, right? At least at the
beginning. In fact 355 over 113 is a very famous very good fraction approximation of pi using
relatively small numbers. Its decimal expansion coincides with that of pi up to this point. And
what about the repeating tail of this fraction? It turns out the repeating part is as big as can
be namely 112 digits long corresponding to the 112 non-zero remainders of 113. All pretty easy
right? Of course, there was nothing special about our fraction for this argument. The same argument
shows that every fraction can be written as an infinite decimal with a repeating tail. The
argument also tells us how long this tail can be. Ok but what about the other half of this fraction
decimal correspondence. We used pigeons to prove that every fraction is a repeating decimal
but why is every repeating decimal a fraction? Be honest, do you know why? Well if you
don't know and you'd like to know you can get a mountain size hint from my video on why
9.99 and so on is equal to 10. And of course, look to the comments for a discussion. Oh
and just in case you have not spotted it yet here is a little extra very memorable fun
feature of the fraction in our example. Okay here's the famous one. You go to a party
and as usual at a party people shake hands with all their friends. Okay with COVID we're
having a lot fewer parties and handshakes but let's imagine the good old times. So people
at our imaginary party are shaking hands. Some will have lots of friends and do a lot of
shaking and others may have only a friend or two. But no matter how many guests attend the party and
whatever shaking of hands transpires there will always be at least two guests who shake hands with
the exact same number of people. Nice huh? And no pigeons in sight, unless it's a pigeon party :)
okay lame joke but couldn't resist. Let's see how this works. Suppose there's seven guests at
a party. The exact number doesn't matter. Well, it should be more than one guest. Okay, now when
two guests shake hands we record this with a line connecting the two guests. So once all hands have
been shaken we'll end up with a picture like this. One very unpopular guy down there. Anyway,
see there are also those two guys there. They each shake hands with five
other people and the question is how can we be sure that this will always
happen, that there will always be such handshake twins? Well, let's
focus on just one of the guests. What's possible in terms of handshakes? Well if
everybody hates this guy, maybe a gate crasher, then nobody will want to shake hands with him.
But if this guy is not a complete outcast then he might shake hands with one other person,
or two three four five or six other people. The six here is the maximum corresponding
to a popular guy who shakes with everybody else at the party. So zero to six that's seven
different possible numbers of handshakes and there are seven guests and so the pigeonhole
principle tells us …. Absolutely nothing, not yet anyway. With seven guests and seven
possible numbers of shakes, we're going to have to work a little harder. But here's a nifty
insight. If there's an unpopular guy, a zero, then there also cannot be super popular
guys. Right? A Mr Popular could shake hands with everybody else but not with a
zero guy. And the converse is also true. If there's a Mr Popular who shakes hands
with everyone there cannot be a zero guy. This means that the possible handshake numbers at
our party are either zero to five or one to six. So at any specific seven guest party there
are only six possible handshake numbers. And yep now the pigeonhole principle works.
Two guests must shake the same number of times. Tada, very pretty, isn't it? You got it? Good! Then here's a challenge for you. Try
to prove this advanced pigeon party theorem: at any party with six people at least one of the
following handshaking scenarios will manifest: first scenario there are three people who shake
hands with each other, like this. Second scenario: there are three people none of
whom shake hands with each other. And as in the case of the party over there
both scenarios can occur at the same time. This pigeon party theorem is the starting
point for something called Ramsey theory. Very interesting and very
powerful stuff. Check it out! Okay of course all of you are familiar with the
Rubik's cube and most of you will know at least in principle how to solve it. The trick is to
have up your sleeve three or four algorithms, set combinations of moves. Then using these few
algorithms over and over in the correct order you can solve the cube. However, if you started
with a solved cube something cool happens. Take a solved cube and consider just one
algorithm. Use that algorithm over and over on the solved cube. Then no matter what
algorithm you choose you will eventually end up with a solved Rubik's cube. Pretty
surprising right? For example, suppose your algorithm is the following two-move combo: first
twist the top side clockwise and then twist the left side counterclockwise. When we do
this over and over this is what happens. Works and even if you know it's going to work
it's a little hard to believe until you see it, isn't it. For our algorithm it turns out we had to
repeat it 63 times to get back to the solved cube. And again what I'm saying is that this will work
with any algorithm any algorithm whatsoever. Start with a solved cube and repeat your algorithm over
and over and after enough repeats you'll have a solved cube again. Why does this work? Well,
it's pretty similar to the fractions example earlier. It amounts to fitting infinitely many
pigeons into finitely many pigeonholes. Let me explain. First ,our pigeonholes. The Rubik's
cube has this many different configurations that's a lot of configurations and these
finitely many configurations are our pigeonholes. Let those dots over there stand for the different
holes the possible configurations of the cube. In particular, there is one special blue dot.
The blue dot stands for the solved cube. We're starting with a solved cube
which means we start out at the blue dot. Now perform the algorithm. That
moves us to some new configuration. Repeat and you get to yet another configuration.
And so on. Now the important observation to make is that this process goes on forever. And this
forever stands for the infinitely many pigeons. But there are only finitely many states and those
finitely many states are the pigeonholes. This means that eventually, you have to come across a
state that you've already visited on your journey. Now there are two possibilities.
Either you get back to solved or you re-enter the path at a different state.
Of course, if that were to happen you'd never get back to solved because you would now
forever and ever travel on this loop. So what I'm claiming is that this later joining
cannot happen. And why not? Because that would mean that there are two different configurations
that our algorithm would move to the orange spot. And that is definitely impossible
since our algorithm is reversible. What I mean by this is that if your cube is in a
certain configuration and you execute an algorithm then by reversing the moves of the algorithm
you must end up where you started. That means it's impossible to use the algorithm once to
reach a new configuration from two different starting configurations. That is that orange
dot in the diagram is impossible. Very neat. Okay so our algorithm whatever it is just loops us
back to the solved cube and then goes on looping. Actually the same is true no matter where
you begin, the algorithm will loop you back to that beginning configuration. Let's
say you start here. Okay go for it. There, another cycle. In fact, it's easy to see
that this second cycle has to be of exactly the same length as our first cycle. This means that
all the zillions of Rubik's cube configurations will be split into disjoint cyclical journeys of
equal lengths. That also means that the common length of our cycles must divide the total number
of configurations that monster number up there. And you can check that 63 the number of times we
had to repeat that first algorithm I showed you, that 63 divides our monster number. That's nice
isn't it? And there's another surprise lurking just around the corner. I might as well just tell
you about it. How long can an algorithm cycle be? Well there are lots and lots and lots of really
huge numbers that divide the monster up there. So you might expect really huge cycles as well. But
nope no matter how complicated your algorithm, it turns out that its cycle length can be
no greater than a relatively tiny 1260. Challenge for you suppose your algorithm is
right side clockwise top side clockwise left side clockwise and also bottom side clockwise. How long
is the cycle of this algorithm? Do you like this stuff so far? Well, two more chapters to go. Our
penultimate puzzle is a very nice problem from the 1972 international mathematical olympiad. Serious
stuff. Start with all the two digit numbers. Pick any 10 of them. Then the maths olympians were
supposed to show that no matter the 10 numbers picked there would always be two collections of
these numbers with no overlap and with exactly the same sum. So in the example there we've chosen
a blue collection and a green collection and each collection sums to 125. 10 plus 22 plus
93 that's 125 and 17 plus 29 plus 37 plus 42 is 125 again. And that's always true no
matter the 10 numbers originally chosen. That's pretty amazing isn't it?
So how are we going to show this? Where are the pigeons and pigeonholes that
will help us? Actually that's pretty easy. The pigeonholes are the possible sums. So what's the
smallest possible sum you can get in the scenario. Easy right? The smallest possible sum is 10
corresponding to the collection of just the one number 10. What about the largest possible
sum? Well that would be the sum of the largest nine two digit numbers right? And so the largest
sum is definitely no larger than 91 plus 92 all the way to 99 which is 855. And then from 10 to
855 that's 846 possible sums, 846 pigeonholes. What about the pigeons? Given 10
chosen numbers we have to figure out the number of possible collections. Those
10 circles represent our 10 numbers. Now for any collection of these numbers, each number
either is in the collection or it misses out, so two possibilities for each number. That means
that there's a total of two times two times two ten times so 2 to the power of 10 is equal to 1024
possible collections from these 10 numbers. Right? Almost. Those 1024 collections also
include the collection with none of the 10 numbers and the collection of all ten.
But these all-or-nothing collections don't work for us since we actually want two non-empty
collections. So we'll leave those ones out, giving us 1022 possible collections. And so
there you have your pigeonholes and pigeons. Great. So there are definitely always two
different collections that have the same sum. But we're not quite done. Can you see what the problem is? These two equal sum collections
may have overlaps and those annoying olympiad examiners asked for non-overlapping collections.
So we'll either have to be happy with the partial credit, definitely not a bad result for olympiad
problem, or we have to think a little more. But just a tiny bit more. If there's a
few numbers common to both collections, we can simply remove those numbers from both
collections. Then, since we're removing the same numbers from both collections these
new collections will still have equal sums. Success full credit and as soon as we've completed
the other nine olympiad problems we can go and claim our gold medal. What a great problem
and what an amazing solution, don't you think? And having successfully navigated the olympiad
here's your challenge. Find seven integers from one to one hundred such that no two different
collections from those numbers have the same sum. Now for the grand finale I want to show
you a famous pigeon-powered card trick. Here's how it goes: a volunteer chooses five
cards from a standard deck and gives them to me. I look at them. Then I choose four of the
five cards. Choose choose choose choose. Okay now I pass the four cards to an assistant. Okay
that's Marty of course. He looks at the cards and after a moment's consideration announces
what the fifth card is. Pretty amazing right? And there's no stacked deck no sleight of hand
just pigeons. Do you want to know how this works? Of course you do :) okay so here's an example.
Suppose the volunteer hands me these five cards. Then I'll keep the ten of spades
arrange the remaining cards like this and show them to my assistant. Before you watch
the rest of the video it's really worth you trying to figure out for yourselves how exactly
the order of those four cards tells my friend what the remaining fifths card is. So maybe
pause the video and see what you can figure out. Okay you're back. Figured it out? No? Well for
those still puzzled here's how the trick works. There are five cards but only four suits. So
our pigeons tell us that there must be at least two cards of one suit. Focus on two such cards. In
this example there's no choice and I have to think about the two spades. Okay our pigeons have done
their job they can go and relax now. Now imagine all 13 spade cards in a circle and highlight our
two cards to 6 and a 10. There. How far are our cards apart on the circle? Well, starting from 6
and moving the clockwise direction we count one two three four. Okay four steps. Starting from ten
we have one two three four five six seven eight nine. We take the smaller of the two walks to be
the distance between the two cards. So in our case the distance is four. And, notice, since there
are 13 cards in a suit the distance between any two cards will be at most six. Okay back to our
example. The distance is four with a start card six and the end card ten. The end card is the
card we keep, the card that our assistant will have to guess. And the start card is the first
of the four cards that we show to our assistant. Okay our assistant sees the six of spades
and he knows that we begin by looking at two cards of the same suit. So he knows the fifth
mystery card must also be a spade. But which one? What remains for me to do is to communicate that
the mystery card is four steps away from the starting six on the table. But since we have three
more cards to play with that turns out to be easy. There are six possible distances we might need
to signal and there are six possible orderings of the three cards. Kind of a just enough
pigeonhole principle. Here are the details: we can think of the 52 cards of a standard
deck being arranged in a natural dictionary order with suits counting first. So c for clubs
comes before d for diamonds then hearts and then spades. And within the suits cards are ordered as
usual: ace two three four five up to jack queen king. This means that the dictionary order of
the three remaining cards in our example is this. Got it? The jack of diamonds comes before the five
of hearts because d comes before h so we have a bottom card, a middle card and a top card. And
now we label the different orderings of the three cards from one to six, again as in the dictionary,
like this. BMT in this order stands for one and this is two three four and since
a distance of four is what we want to communicate this is the arrangement this is
the arrangement that we show our partner. Okay ingenious isn't it. I really hope you
like this one. It's called the Fitch Cheney five card trick named after the
mathematician William Fitch Cheney, jr who invented it. In fact some people think this
is the best mathematical card trick ever invented. And to finish off a practice hand for
you. Let's say you are my assistant and I show you these cards. What's the
card that I'm holding in my hand. And that's all from me today. I hope you enjoyed
these proofs, all based on the super simple pigeonhole principle. Which of the proofs did you
like best? Which the least? Please record your rankings in the comments. It will be interesting.
Well and then until next time. Stay safe.
