Sign In | Subscribe

Enter your Sign on user name and password.

Forgot password?
  • Follow us on:
Start learning today, and be successful in your academic & professional career. Start Today!
Loading video...
This is a quick preview of the lesson. For full access, please Log In or Sign up.
For more information, please see full course syllabus of Math Analysis
  • Discussion

  • Study Guides

  • Download Lecture Slides

  • Table of Contents

  • Transcription

  • Related Books

Lecture Comments (1)

0 answers

Post by Orsolya Krispán on April 14, 2013

I'm in love with your hand movements :D Great work, thank you very much!


  • An event is something happening that can occur some number of different ways. If we want, we can denote an event with a symbol (such as E) and similarly for the number of ways (such as n). [Some teachers and textbooks will not use the word `event' and might use another word or nothing at all to describe this idea. That's fine. The important part is just to be aware of certain things having multiple possible outcomes or choices. All the coming ideas will work fine in any case; `event' is just a way to describe this formally.]
  • We can visualize an event (or series of events, as we'll soon see) with a branching line diagram. At each event in the diagram, it splits into its various possible outcomes.
  • Addition Principle: Let there be two events E1 and E2, where E1 can occur in m ways and E2 can occur in n. If precisely one of the events will occur (not both), the total possible ways for something to occur is
  • Multiplication Principle [AKA Fundamental Counting Principle]: Let there be two events E1 and E2, where E1 can occur in m ways and E2 can occur in n. If both events will occur (and they have no effect on each other), the total possible ways for something to occur is
  • Pigeonhole Principle: Let there be some event E that can occur in n ways. If the event E happens n+1 times, then at least one of the ways E can occur must happen twice (or more). Equivalently, given n boxes and n+1 objects, if all the objects are put into the boxes, then at least one box must have (at least) two objects.
  • When working on counting problems, it can help immensely to draw pictures and diagrams. Being able to visually follow the events and choices will make it much easier to solve problems.


Lecture Slides are screen-captured images of important points in the lecture. Students can download and print out these lecture slide images to do practice problems as well as take notes while watching the lecture.

  • Intro 0:00
  • Introduction 0:08
    • Combinatorics
  • Definition: Event 1:24
    • Example
  • Visualizing an Event 3:02
    • Branching line diagram
  • Addition Principle 3:40
    • Example
  • Multiplication Principle 5:42
    • Example
  • Pigeonhole Principle 8:06
    • Example
  • Draw Pictures 11:06
  • Example 1 12:02
  • Example 2 14:16
  • Example 3 17:34
  • Example 4 21:26
  • Example 5 25:14

Transcription: Counting

Hi--welcome back to

Today, we are going to talk about counting.0002

With this, we are starting a new section; and at first, it might seem that counting is a simple thing.0004

But it actually turns out that it is extremely important in math.0009

Being able to count the number of ways that an event can turn out, a process can be performed,0012

or objects will be created is extremely useful in business, science, economics, medicine, and a huge variety of fields.0016

And at first, we are probably thinking, "Well, I could just count them: 1, 2, 3, 4, 5, 6...and be able to be done with counting."0023

Why turn it into a thing in math? Well, that is true; but what if you need to count 100 of something, or you need to count 100 of something,0029

or the thing that you are trying to count is a million large?0035

You can't count a million of the thing by hand with any reasonable amount of time.0037

That is going to take you more than a year, to count the million of something out by hand.0042

So, we need some way to be able to count on a large scale;0046

and that is why math does an actual major study of counting--how to count all sorts of different things;0049

and that is what we will be exploring in this lesson and the next two lessons.0055

The formal study of counting is called combinatorics, and this course will barely scratch the surface of combinatorics.0058

Still, we will manage to see some really important results that allow us to show all sorts of really interesting, cool things.0065

The basic ideas are intuitive--they make a lot of sense; but we can exploit them to answer really difficult questions,0070

and it won't be very hard for us to do at all; all right, let's go!0076

First, we are going to define the idea of an event; an event is simply something happening.0080

And it can occur in some number of different ways.0086

If we want, we can denote an event with a symbol, such as E; and similarly, we can talk about the number of ways that the event can occur.0089

We might use a symbol for that, as well; and we could denote it with some n.0097

So, we have some event that can occur in multiple ways.0100

For example, someone might give you a cookie, and you are allowed to choose from three types of cookie: chocolate chip, snickerdoodle, or peanut butter.0103

We have three different types of cookie that can come out of this.0112

The event, E, is getting a cookie; and the way that it can turn out is three different ways: chocolate chip, snickerdoodle, or peanut butter.0117

So, there is this event; but it doesn't necessarily have a single way of turning out,0125

because we could go with the chocolate chip version of the event,0129

the snickerdoodle version of the event, or the peanut butter version of the event.0131

But they are all within the event of getting a cookie.0135

Some teachers won't use the word event; you might see, in some textbooks, or when a teacher is teaching, that they won't use the word event.0139

And they might use a different word to describe it, or they might not use any word at all.0145

That is fine; the important part of all of this is just to be aware that certain things have multiple possible outcomes or choices involved.0149

All the coming ideas are going to work fine, whether we are using the word event or we are using some other word,0157

or we are not really using a word at all; the important thing is just to get this idea of having branching possibilities coming out of something.0161

Event is just one way to describe this formally, and that is the way we will be talking about it in this course.0169

But all of the basic ideas are going to be the same, whatever vocabulary someone else is using.0174

We can visualize an event: one way to help us visualize an event (or a series of events, as we will soon see) is with a branching line diagram.0180

So, we can have something that breaks off into multiple different directions.0188

At each event in the diagram, it will split into all of its various possible outcomes.0192

In our previous cookie example, we could represent the event with this diagram.0196

We could split into chocolate chip, snickerdoodle, and peanut butter; we have this cookie event0200

that splits into the chocolate chip version, the snickerdoodle version, and the peanut butter version.0204

We have this branching line diagram that shows us all the different ways that our event can occur,0209

because we have one event, but it splits into three possibilities.0216

Addition principle: let there be two events, E1 and E2, where E1 can occur in m ways,0221

and E2 can occur in n ways; if precisely one of the events will occur,0230

not both--we know that an event will occur, and it will be either E1 or E2,0236

but we don't know which of the two events it is going to be--we just know for sure that it will be one of them,0241

when something happens--the total possible ways for something to occur is the number of ways that our first event can occur,0246

added to the number of ways that our second event can occur: m + n.0253

For our previous example, if we were given a choice between one of the previously-mentioned cookies,0259

we can now add on this idea of a scoop of ice cream.0264

Previously, we had three different types of cookies; that would be m = 3.0267

Or we could have a scoop of ice cream; we are allowed to have either a cookie or a scoop of ice cream.0272

And the ice cream can be vanilla or chocolate; so that gives us two choices, so we have n = 2.0278

Then, the total possible choices are the m choices plus the n choices: our three choices for cookie,0285

plus the two choices that we have for ice cream, comes out to a total of 5 possible choices that we can have out of this.0294

We can see this branching like this; if we choose the dessert version of cookie0300

(we have this initial thing: we are getting a dessert; now we have the choice between the cookie event or the ice cream event;0305

so if we go down to the cookie event), we can split into chocolate chip, snickerdoodle, or peanut butter.0311

But if we went down the other event, our second event, we can split into vanilla or chocolate.0316

So, that gives us two possibilities here and three possibilities here; we count them all together, and we get 5,0323

when we combine all of the things that could happen, because we have branched off of the different events;0330

so we have to add up all of the possible outcomes.0334

Next, the multiplication principle: this is also called the fundamental counting principle, because it is just so very important to the way counting works.0337

Let there be two events, E1 and E2:0345

once again, E1 can occur in m ways, and E2 can occur in n ways.0348

If both events will occur--that is to say, Event 1 is definitely going to occur, and event 2 is definitely going to occur--0354

and we also have to have that they have no effect on each other (how Event 1 turns out0362

will have no effect on how Event 2 turns out--they are independent events;0367

what happens over here won't affect what happens over here), then the total possible ways0371

for something to occur is the number of ways that our first event can occur, times the number of ways that our second event can occur.0376

Let's see an example to help us understand why this is.0384

Going back to our previous example, once again, expanding on that, the idea of cookies and ice cream:0387

now, we are given a choice of one of the previously-mentioned cookies (that was m = 3 choices),0391

and a choice of the previously-mentioned ice cream scoops.0397

We are not just getting a cookie or a scoop of ice cream; we are getting both.0400

We are getting a cookie, and we are getting a scoop of ice cream.0404

So, we have three possibilities for the cookie choice, and then two possibilities for the scoop of ice cream.0407

That will give us a total of possible choices of 6; and let's see why that ends up working out.0414

We get 3 times 2 equals 6; that is m times n; let's see how this works out.0419

We start with our first event; our first event occurs, because we are going to have to get the cookie, and then we will get the ice cream.0424

We can do it the other way, and it would work out just as well.0430

But let's say cookie, then ice cream: so we choose our cookie choice--we have three possible ways for our cookie choice to turn out.0432

We can either have chocolate chip, snickerdoodle, or peanut butter.0438

But then, on each one of these choices, we have an expanded two more choices.0441

So, if we have chocolate chip, we now have vanilla or chocolate out of that; so that is 2 here.0445

If we took snickerdoodle, we now have vanilla or chocolate; so that is 2 here.0452

If we took peanut butter, we now have vanilla or chocolate; so that is 2 here.0457

So, because we have three possible starting branches, when the next two branches come off, we can just multiply the number for each event.0461

There are three possibilities that come out of our cookie choice, and then a further two possibilities on top of each of those.0468

So, it would be 3 times 2, for a total of 6 in the end.0474

All right, the next idea is the pigeonhole principle.0481

Let there be some event E that can occur in n ways; we have some event E, and it can happen in n ways.0485

Now, if that event happens n + 1 times--it happens one more than the number of ways that the event can turn out;0492

so it has n different possibilities for turning out, and then the event happens one more time0499

than the number of ways that it can turn out--we know that one of the ways that the event can occur must happen twice.0504

It can also happen more, but we know for sure that it will happen at least twice in one of the ways; and it might happen more.0510

But we are guaranteed at least twice in one of the ways.0516

Another way to look at this is with boxes and objects; I think this is a little bit easier to visualize.0520

Equivalently, given n boxes and n + 1 objects, if all of the objects are put into the boxes, then at least one box must have at least two objects.0526

Let's use some numbers here, so that we can see this a little better.0535

Let's say we have 3 boxes: 1, 2, 3 boxes; and we are given 4 objects: 1, 2, 3, 4.0537

If we try to fit these four objects into those three boxes, it has to be the case that, in one of those boxes, there will be at least two balls.0549

For example, if we try to keep these balls separated; so we put this ball in here first, and then we put this ball in here first,0558

and then we put this ball in here first, when we get to this ball here, it has to go into a box that has already been filled.0565

And so, whichever of the three boxes it ends up going into--it doesn't matter which one it ends up going into--0572

it is going to end up going into a box that already has another object in there.0578

And so, we will know that we had at least two objects.0582

We might have ended up putting all 4 balls in one box; that is for sure; but that would still say that at least one box has at least 2 objects.0586

And so, it will end up being true, however we decide to distribute these balls.0595

We can be guaranteed that at least one of the boxes has at least 2 objects.0599

There might be more boxes that have even more; there might be one box that has all of them.0603

But we know for certain that at least one of them has at least 2.0607

In many ways, it is just common sense; it seems a little surprising to see in a mathematical context,0610

because it just makes such perfect sense to us, intuitively.0615

But we can end up saying some pretty surprising things by using this idea, as we will see in Example 5.0618

A really quick example, just to see this applied: if we were given four cookies, and each of our cookies was,0623

once again, those three choices of chocolate chip, snickerdoodle, and peanut butter;0627

then we know, since we were given four cookies, and we only have three possibilities,0632

that we have to have at least two of one type of cookie.0637

We are going to have to have at least two chocolate chips, or at least two snickerdoodles, or at least two peanut butters.0641

We might end up having many in a different kind--we might have 4 chocolate chips or 4 snickerdoodles or 4 peanut butters,0647

or two chocolate chips and two snickerdoodles, and no peanut butters.0653

But we know for certain that there is at least one thing where we have a pairing on the cookie type.0655

All right, first: draw pictures--when working on counting problems, it can help immensely to draw pictures and diagrams.0661

Just being able to visualize this stuff can make it a lot easier to understand.0668

If you can visually follow the events and choices, if you can see what is going on--how things are branching,0671

it is going to make it that much easier to solve problems.0678

So, I really recommend drawing pictures.0680

Now, that is not to say that you need to draw accurate pictures.0682

You don't really want to draw accurate pictures.0685

Instead, what you want to do is draw pictures that are going to be pictures or diagrams0688

that just let you see how many ways an event can occur, and how it is connected to the other events,0692

so that you can see how there are things interrelated, or not interrelated, and how things can occur--0699

the number of ways, branching paths...all of those sorts of things.0705

Drawing every single possibility, drawing really careful pictures--that is not necessarily the thing.0708

You just want something so that you can visualize it and see it on paper.0712

We will see a lot of this in the examples; all of the examples will have some way of being able to visually understand what is going on.0715

All right, now we are ready for some examples.0720

The first example: we have 7 shirts, 3 pairs of pants, and 4 pairs of shoes.0722

What is the total number of outfits that you can wear from this selection?0727

The first thing to notice is: if we are going to wear an outfit, we are going to have to wear shirts, pants, and shoes,0730

because we are going to go outside with it; so we want to have definitely a shirt, definitely pants...0735

we are walking outside, so we definitely want shoes, as well.0739

So, we are going to have definitely a shirt, definitely pants, and definitely shoes.0742

Furthermore, our choice of shirt, our choice of pants, and our choice of shoes have nothing to do with each other.0744

They might not look good together, but it would be a possible output we could create.0750

Shirt is completely independent from pants, which is completely independent from shoes.0754

Each one is a choice completely in and of itself; they don't have an effect on each other.0759

So, we can think of it as three separate events.0763

First, we have the seven shirts; so we have the choices for shirts, to begin with--we have 7 possible things for shirts.0766

And then, next, we have three pairs of pants; so there are a total of...all of our pants choices,0774

our "pants event," is 3 different ways for our pants event to turn out.0782

And then finally, there are 4 pairs of shoes; there are 4 different ways for our shoes event to turn out.0787

We know that we have to end up having a shoes event turn out, and it can turn into four different possibilities.0793

So, we could think of this with branching: we dress ourselves, and so our first thing is that we branch into multiple different choices with the shirts.0800

And then, from here, we branch into multiple different choices with the pants.0808

And that is going to end up happening on each one of our blue things.0811

So then, if we end up following out any one of these, we are going to branch on this.0814

So, on every branch, it branches 7 times; and then, each of those branches 3 times, and then each of those branches 4 times.0818

That was our fundamental counting principle, the multiplication principle.0825

Since they are independent events--they don't have anything to do with each other--we just multiply the number of possibilities for each one of them.0828

So, 7 times 3 times 4: we multiply this all out together; we end up getting 84 possibilities.0834

So, we have a total of 84 different possible outfits.0845

Great; the next question: We are going out to dinner tonight--you are going out to dinner tonight (I am not coming with you).0850

Your options for the restaurant are Mexican, Japanese, or French.0856

At each restaurant, they have the following number of selections.0860

Mexican has 4 appetizers and 10 main courses; Japanese has 3 appetizers and 7 main courses; and French has 8 appetizers and 5 main courses.0863

If you will have one appetizer and one main course, how many ways are there for you to have dinner tonight?0872

The first thing that we have to realize is that, if we are going to go out to dinner, we can't go out to dinner at multiple restaurants at the same time.0878

If you go out to dinner, you have to choose one restaurant.0884

Our very first thing is that we actually have a restaurant choice; so restaurant breaks into 3 different possibilities.0886

We can either go to the Mexican, the Japanese, or the French.0895

If we go to Mexican, we will have that one here; and then, we could also have gone to Japanese;0899

and then finally, we could have gone to French.0911

And then, we were told that, when you are out at dinner, you are going to have one appetizer and one main course.0916

Now, the choice of appetizer has no effect on the choice of main course, necessarily.0925

You could choose any appetizer to go with any main course.0928

They might not fit together, but it doesn't matter; you could choose it, so they are independent events.0931

One of them does not necessarily change the way the other one can turn out.0935

For the Mexican choice, if you went with Mexican, you would have four choices for your appetizer.0939

And then, you would have 10 choices for your main course: 4 appetizers, and then 10 main courses.0946

The same thing for the Japanese, but different numbers: we have 3 choices (let me make this a little bit bigger)0953

for the appetizer, and then we have 7 choices for the main course.0962

Finally, the French restaurant: if you had gone there, you would have 8 choices for the appetizer and 5 choices for the main course.0967

So, if you had gone to Mexican, you would have 4 times 10 total possibilities at the Mexican restaurant.0976

If you had gone to Japanese, you would have 3 times 7, or 21, total possibilities if you had gone to the Japanese restaurant.0982

If you had gone to the French restaurant, you would have 8 times 5, or 40, possibilities if you had gone to the French restaurant.0989

But you don't have to go to any one of these, necessarily.0994

At the beginning, you have this branching choice: you have an exclusive choice,0998

where you can choose one of the restaurants, but you can't choose multiple of the restaurants.1002

So, you could go down Mexican and get to the Mexican set of choices.1006

You could go down Japanese and get to the Japanese set of choices.1009

Or you could go down French and get to the French set of choices.1011

This means that we have to add the number of choices at each restaurant all together to figure out what the total choices for the night are.1014

So, we end up having 40 from the Mexican, plus 21 from the Japanese, plus 40 from the French,1020

which comes out to be a total of 40 + 40 (80) + 21: 101 choices;1029

so you have 101 total choices for dinner tonight, total ways to have dinner,1035

because you could go to any of the three restaurants; and then, once you are at each of the restaurants,1041

you then have an independent choice between appetizer and main course.1045

So, at the end, we have to add them all back up together.1049

The next example: At a computer store, you are going to buy speakers, a monitor, and a computer.1052

There are four options for speakers, seven for monitors, and two for computers.1057

One of the computers gives a choice between one of two operating systems, while the other has one of three operating system options.1061

So, if you buy one of the computers, you can choose between one of two things on top of it.1068

And if you buy the other computer, you are allowed to choose one of three things on top of it.1072

How many total ways are there to make your purchase?1076

Now, of course, if you buy a computer, you have to have an operating system with it.1079

So, we are guaranteed that we are going to get some operating system.1082

With that in mind, how can we figure out how many ways to make a purchase?1085

Well, if we go in the order that this comes, we see that we have speakers; we buy speakers,1088

and we many ways?...there are four options for speakers;1096

and then we have the monitors; we look at it--we have...1103

oh, oops, there are four options, not seven; I was accidentally reading monitors.1107

We have four for speakers, and then we have seven for monitors.1111

And then, the computers: you have two options for the computers.1114

But then, we have this whole thing about the OS, the operating system, of it.1119

Our operating system comes into this, as well: operating system branches, depending on which computer you had bought.1123

If you bought the first computer or the second computer, you are going to have different numbers of options here.1129

So, you could have 2 here or 3 here.1134

With that in mind, it gets a little confusing to figure out how we want to work this out.1137

Let's have our first thing be the computer choice; we will say computer choice determines everything else,1140

because speakers and monitors are completely independent of which computer you choose.1145

The operating system choice, though, does depend on which computer you chose.1149

So, we will start with choosing a computer choice.1153

We have our computer choice, which splits into one of two possibilities.1155

It splits into the two OS possibility, or it splits into the three OS possibility.1160

We have the operating system; over here, there are two possible operating systems.1168

Over here, though, there are three possible operating systems.1174

Next, we have speakers for both of them; there are going to be four choices for speaker and four choices for speaker.1178

And for monitor, we have seven choices for the monitor and seven choices for the monitor,1184

because that has no effect on which of the two computers we had initially bought.1189

Our computer--this number of choices, 2, doesn't really come into effect, because we already counted it by having it branch two different ways.1192

We have created that branching, and now we are reading both of them.1199

What we do is figure out how many options we have if we had bought the 2-operating-system computer.1201

How many options do we have if we had bought the 3-operating-system computer?1207

And then, we add those two together to figure out the total number that we have.1210

So, let's figure this out: if we have 2 times 4 times 7, we end up having 8 times 7, or 56, total options over here.1214

If we had gone with the 3-operating-system, then we have 3 times 4 times 7 possibilities, if we bought the 3-operating-system computer.1226

So, that comes out to 84 choices.1234

If we want to have the possibility of choosing between one of the two computers at first, well, that changes what happens later on.1237

So, that has to count as an either/or event; we can only choose one of the two.1243

We have the 2-operating-system possibility (56) and the 3-operating-system possibility (84).1251

If we want to be able to have an option between choosing which of those two paths we go down, we add them together.1256

So, we have the 56 options for the 2-operating-system, added to the 84 options for the 3-operating-system.1260

We add those together, and we get 140 total possibilities.1270

We have 140 total possible ways to make this purchase, when we include all of the different options that we have at our disposal.1274

The next example: On an exam, there are 25 multiple-choice questions, each one of them having 5 choices that you can answer with.1281

Now, assuming that we count not putting down any choice as an option for answering a question1289

(because it is, in a way, a choice that you have made--not putting anything down is a choice,1293

just as much as marking A or C or E)--if that is the case, we are going to assume that not putting down something1299

counts as an option for answering a question--with that in mind, how many ways total are there to mark the answer sheet?1305

There are 25 different times that we have the chance to answer.1311

For our first one, well, let's look at it as...we have 25 different slots, effectively,1316

each of our slots representing all of the choices that we have for answering.1323

This is going to keep going, going, going; there are a total of 25 slots that we are dealing with,1327

because each of the questions is a slot that gets answered.1336

OK, so with that in mind, we are going to say, "How many ways can we answer the first question?"1340

Well, the first question...we are allowed to count not putting down a choice; we count not putting a choice as an option.1345

So, if that is the case, and there are 5 choices (A, B, C, D, E) for each one of these,1354

and we count not putting down something as an additional option,1358

then that means that there is a total of 6 for one of these questions: A, B, C, D, E, nothing at all.1362

That is a total of 6 possibilities.1368

What about the next question--is the next question affected by the way that we answered the previous question?1370

Not at all; you can mark that answer any way you want.1375

Once again, we have A, B, C, D, E, nothing at all; so there are 6 choices on the next one, 6 choices on the next one, 6 choices, 6 choices.1378

There are 6 choices for each one of the 25 questions that we are answering,1386

6 times 6 times 6 times 6...because each one is an independent event,1390

so we multiply them all together to figure out how many possible things there are.1394

What we have is 6 times 6 times 6...going all the way out to more 6's.1398

We have a total of 25 6's multiplied together.1406

Well, on the bright side, we have a nice way for saying 6 multiplied by 6 25 times; that is the same thing as saying 625.1416

So, there are a total of 625 ways to answer this set of questions.1425

There are 625 ways to mark up this answer sheet.1432

How many does that come out to be?--it is a little hard to see just how large 625 is.1435

625, if we use a calculator to get an approximate value for that--that comes out to be 2.8x1019 possibilities,1439

which is an absolutely staggering number; that is a huge number.1450

If we were to count this out, it would have 19 0's: 1, 2...actually, it would have 18 zeroes,1454

because of that .8: so 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18; and then the 2.8x1019.1459

So, we would end up having this incredibly massive number of choices.1477

I can't even figure many is that?1480

That is ones, thousands, millions, billions, trillions, quadrillions...28 quintillion choices for the ways that we could answer this, with only 25 questions.1482

So, that is a massive, massive number of possibilities here, which gives us an idea of just how fast things can grow.1494

This is why we don't want to have to count this stuff by hand.1500

It is because these numbers can get really big really fast in things that seem really simple; cool.1503

All right, the final example: Show that there are at least two people in London right now with the exact same number of hairs on their heads.1509

This will require a little bit of research.1516

This seems kind of like a weird thing at first; we see this use-the-pigeonhole principle after researching.1519

That is going to be a hint that we are going to want to use the pigeonhole principle.1524

A little bit before we get into this, let's consider the idea of if we were talking about birthdays.1527

That will help us understand what is about to happen in just a moment.1532

If we were talking about birthdays, if we had...let's say that there are only 365 days that you can be born on.1535

We are forgetting about leap years, because we are assuming that we slide that to either the day before or the day after.1543

There are 365 days that you can be born on.1548

That means, if we have 366 people in the same room, we are guaranteed that at least one pair of people there has the same birthday.1551

Now, there might be more birthdays that are concurrent--people that have the same birthday.1560

But we can be guaranteed that there is at least one pair, because if we have 365 effective slots1564

for a day that a birthday can be on, that is 365 boxes that a person can go into and represent "I am on that day."1570

Then, at least two people are going to end up having to be in that same box.1577

They are going to have to end up occupying the same birthday.1581

Otherwise, it just doesn't make sense; that is the pigeonhole principle in action,1584

this idea that if we are stuffing things into pigeonholes (being a little place for a message, a long time ago)--1589

if we stuffed ten messages into nine pigeonholes, there is going to have to be1595

some pigeonhole that has multiple messages in it--at least 2 messages.1601

So, if we have 366 people, we know that there are going to be at least 2 people who have the same birthday--that is the basic idea here.1605

Now, let's start thinking about this one: we are talking about hairs on heads, and we are talking about London.1613

First, let's look into hairs on heads: we look into how many hairs are on a human head.1619

A human head, assuming they have a reasonable full head of hair...a human head with full hair has around 100,000 hairs on it, about 100,000 hairs.1624

Now, of course, this number can be higher; this number can be lower; but it doesn't get much higher than 100,000.1639

200,000--pretty much no one is going to have 200,000 hairs.1645

So, it starts to limit out pretty quickly; around 100,000 hairs is about the normal amount for a human head.1648

And 150,000 would be a lot of hair; more than that just starts to become ridiculous and really hard.1656

We figured that out with just a little bit of Internet research--some cursory research.1661

We figured out pretty quickly that it looks to be about 100,000.1665

At that point...we didn't do really, really careful scientific study, so we want to make sure that we are giving some extra leeway here.1668

So, let's say, from this idea, that the absolute maximum number of hairs that can be on a human head is going to be...let's just say it is a million hairs.1674

There can't be more than a million hairs on a human head.1686

So, there have to be a million hairs or less on a human head.1690

There can be anywhere between 0 (you can't have less than 0 hairs on your head) up to a million.1696

And a million is actually a ridiculously large number; no one is going to actually have a million at all.1700

But let's set it up to a high point that is ridiculous, because if we can show that this is true,1705

even with this ridiculous amount of hair, we will have proved it for a smaller, more accurate thing--what the real world would actually have.1709

We can set a higher set.1715

The next idea: let's look at the population in London.1717

The population in London, as of the writing of this video is a little bit over 8 million.1721

It is around 8.1 million--a little more than that; so it is around 8 million; it is over 8 million.1734

Because of this, we now know, by the pigeonhole principle, that there are1739

at least two people in London who have the exact same number of hairs on their head.1742

Why? Well, let's look at it like this.1746

We can think of that absolute maximum of 1 million hairs as being a bunch of different boxes.1748

The number of hairs on a person's head...this goes all the way out to...we have 0 hairs at first, 1 hair on your head,1754

2 hairs on your head, 3 hairs on your head, 4 hairs on your head...then 999,999 hairs on your head, one million hairs on your head.1765

So, we have all of these different boxes that a person can go into.1774

We are counting all the way up from 0, up until 1 million hairs.1778

We know that, if it is a human, they are going to have to go in one of these boxes,1782

because the absolute maximum number of hairs (and this is ridiculous number) would be that a person has a million hairs on their head.1785

That is too large, but we know that the absolute maximum number of boxes1791

that we have to have here is from 0 up until a million, to mark out the number of hairs on a head.1794

Now, we know that the population of London is over 8 million.1799

That means, when we go through the first one million and one people, then unless they already end up1803

with two people having the same number of hairs on their heads, in the first million and one people,1813

then we are going to go all the way up from 0 to a million with each person having a unique number of hairs on their head.1817

But as soon as we get to the million-and-second person, they are going to end up having to go into the same box as someone else.1823

Someone else will end up having to have that same box with somebody else.1829

They will have to share; so we have the exact same number of hairs guaranteed.1833

We know that, right this moment, in London, there are somewhere in there 2 people who have the exact same number of hairs on their head.1837

It is pretty wild; in fact, because it is over 8 million, we could show that there are, in fact,1845

at least 8 people who have the exact same number of hairs on their head, right this instant--kind of surprising.1850

I won't prove why that has to be the case; but if you think about this for a little while, you will probably be able to figure it out on your own.1857

It is pretty cool; now, of course, there is no practical application to this immediately.1863

We couldn't actually find these two people with any ease.1867

But it is interesting to know that there is this guarantee that, because there are so many people in London,1870

and there are just not that many hairs on the human head--there are more people in London1875

than there can be hairs on the human head--it must end up being that two people have the same number of hairs on their heads.1879

That is one way to apply the pigeonhole principle that allows us to show these really kind of surprising, strange results with not that much difficulty.1887

All right, cool; we will see you at later--goodbye!1893