WEBVTT mathematics/pre-calculus/selhorst-jones
00:00:00.000 --> 00:00:02.200
Hi--welcome back to Educator.com.
00:00:02.200 --> 00:00:04.300
Today, we are going to talk about counting.
00:00:04.300 --> 00:00:09.300
With this, we are starting a new section; and at first, it might seem that counting is a simple thing.
00:00:09.300 --> 00:00:12.300
But it actually turns out that it is extremely important in math.
00:00:12.300 --> 00:00:16.500
Being able to count the number of ways that an event can turn out, a process can be performed,
00:00:16.500 --> 00:00:23.200
or objects will be created is extremely useful in business, science, economics, medicine, and a huge variety of fields.
00:00:23.200 --> 00:00:28.800
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."
00:00:28.800 --> 00:00:34.800
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,
00:00:34.800 --> 00:00:37.500
or the thing that you are trying to count is a million large?
00:00:37.500 --> 00:00:41.800
You can't count a million of the thing by hand with any reasonable amount of time.
00:00:41.800 --> 00:00:45.900
That is going to take you more than a year, to count the million of something out by hand.
00:00:45.900 --> 00:00:48.800
So, we need some way to be able to count on a large scale;
00:00:48.800 --> 00:00:55.100
and that is why math does an actual major study of counting--how to count all sorts of different things;
00:00:55.100 --> 00:00:58.300
and that is what we will be exploring in this lesson and the next two lessons.
00:00:58.300 --> 00:01:04.700
The formal study of counting is called **combinatorics**, and this course will barely scratch the surface of combinatorics.
00:01:04.700 --> 00:01:10.200
Still, we will manage to see some really important results that allow us to show all sorts of really interesting, cool things.
00:01:10.200 --> 00:01:15.900
The basic ideas are intuitive--they make a lot of sense; but we can exploit them to answer really difficult questions,
00:01:15.900 --> 00:01:19.800
and it won't be very hard for us to do at all; all right, let's go!
00:01:19.800 --> 00:01:26.400
First, we are going to define the idea of an event; an **event** is simply something happening.
00:01:26.400 --> 00:01:29.400
And it can occur in some number of different ways.
00:01:29.400 --> 00:01:36.700
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.
00:01:36.700 --> 00:01:40.400
We might use a symbol for that, as well; and we could denote it with some n.
00:01:40.400 --> 00:01:43.100
So, we have some event that can occur in multiple ways.
00:01:43.100 --> 00:01:52.600
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.
00:01:52.600 --> 00:01:57.100
We have three different types of cookie that can come out of this.
00:01:57.100 --> 00:02:05.400
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.
00:02:05.400 --> 00:02:09.100
So, there is this event; but it doesn't necessarily have a single way of turning out,
00:02:09.100 --> 00:02:11.500
because we could go with the chocolate chip version of the event,
00:02:11.500 --> 00:02:15.100
the snickerdoodle version of the event, or the peanut butter version of the event.
00:02:15.100 --> 00:02:19.000
But they are all within the event of getting a cookie.
00:02:19.000 --> 00:02:25.500
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*.
00:02:25.500 --> 00:02:28.900
And they might use a different word to describe it, or they might not use any word at all.
00:02:28.900 --> 00:02:36.900
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.
00:02:36.900 --> 00:02:41.200
All the coming ideas are going to work fine, whether we are using the word *event* or we are using some other word,
00:02:41.200 --> 00:02:49.300
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.
00:02:49.300 --> 00:02:54.100
*Event* is just one way to describe this formally, and that is the way we will be talking about it in this course.
00:02:54.100 --> 00:03:00.100
But all of the basic ideas are going to be the same, whatever vocabulary someone else is using.
00:03:00.100 --> 00:03:08.000
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.
00:03:08.000 --> 00:03:11.900
So, we can have something that breaks off into multiple different directions.
00:03:11.900 --> 00:03:16.400
At each event in the diagram, it will split into all of its various possible outcomes.
00:03:16.400 --> 00:03:19.900
In our previous cookie example, we could represent the event with this diagram.
00:03:19.900 --> 00:03:24.000
We could split into chocolate chip, snickerdoodle, and peanut butter; we have this cookie event
00:03:24.000 --> 00:03:28.700
that splits into the chocolate chip version, the snickerdoodle version, and the peanut butter version.
00:03:28.700 --> 00:03:35.700
We have this branching line diagram that shows us all the different ways that our event can occur,
00:03:35.700 --> 00:03:41.100
because we have one event, but it splits into three possibilities.
00:03:41.100 --> 00:03:49.900
Addition principle: let there be two events, E₁ and E₂, where E₁ can occur in m ways,
00:03:49.900 --> 00:03:56.000
and E₂ can occur in n ways; if precisely one of the events will occur,
00:03:56.000 --> 00:04:01.500
not both--we know that an event will occur, and it will be either E₁ or E₂,
00:04:01.500 --> 00:04:06.000
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,
00:04:06.000 --> 00:04:13.400
when something happens--the total possible ways for something to occur is the number of ways that our first event can occur,
00:04:13.400 --> 00:04:19.300
added to the number of ways that our second event can occur: m + n.
00:04:19.300 --> 00:04:23.800
For our previous example, if we were given a choice between one of the previously-mentioned cookies,
00:04:23.800 --> 00:04:26.700
we can now add on this idea of a scoop of ice cream.
00:04:26.700 --> 00:04:32.600
Previously, we had three different types of cookies; that would be m = 3.
00:04:32.600 --> 00:04:38.600
Or we could have a scoop of ice cream; we are allowed to have either a cookie or a scoop of ice cream.
00:04:38.600 --> 00:04:44.700
And the ice cream can be vanilla or chocolate; so that gives us two choices, so we have n = 2.
00:04:44.700 --> 00:04:53.800
Then, the total possible choices are the m choices plus the n choices: our three choices for cookie,
00:04:53.800 --> 00:05:00.400
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.
00:05:00.400 --> 00:05:05.400
We can see this branching like this; if we choose the dessert version of cookie
00:05:05.400 --> 00:05:11.500
(we have this initial thing: we are getting a dessert; now we have the choice between the cookie event or the ice cream event;
00:05:11.500 --> 00:05:15.800
so if we go down to the cookie event), we can split into chocolate chip, snickerdoodle, or peanut butter.
00:05:15.800 --> 00:05:23.000
But if we went down the other event, our second event, we can split into vanilla or chocolate.
00:05:23.000 --> 00:05:29.700
So, that gives us two possibilities here and three possibilities here; we count them all together, and we get 5,
00:05:29.700 --> 00:05:33.900
when we combine all of the things that could happen, because we have branched off of the different events;
00:05:33.900 --> 00:05:37.000
so we have to add up all of the possible outcomes.
00:05:37.000 --> 00:05:44.800
Next, the multiplication principle: this is also called the fundamental counting principle, because it is just so very important to the way counting works.
00:05:44.800 --> 00:05:48.100
Let there be two events, E₁ and E₂:
00:05:48.100 --> 00:05:54.200
once again, E₁ can occur in m ways, and E₂ can occur in n ways.
00:05:54.200 --> 00:06:01.800
If both events will occur--that is to say, Event 1 is definitely going to occur, and event 2 is definitely going to occur--
00:06:01.800 --> 00:06:07.500
and we also have to have that they have no effect on each other (how Event 1 turns out
00:06:07.500 --> 00:06:11.200
will have no effect on how Event 2 turns out--they are independent events;
00:06:11.200 --> 00:06:16.200
what happens over here won't affect what happens over here), then the total possible ways
00:06:16.200 --> 00:06:23.700
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.
00:06:23.700 --> 00:06:27.200
Let's see an example to help us understand why this is.
00:06:27.200 --> 00:06:31.200
Going back to our previous example, once again, expanding on that, the idea of cookies and ice cream:
00:06:31.200 --> 00:06:37.000
now, we are given a choice of one of the previously-mentioned cookies (that was m = 3 choices),
00:06:37.000 --> 00:06:40.300
and a choice of the previously-mentioned ice cream scoops.
00:06:40.300 --> 00:06:43.700
We are not just getting a cookie or a scoop of ice cream; we are getting both.
00:06:43.700 --> 00:06:47.200
We are getting a cookie, and we are getting a scoop of ice cream.
00:06:47.200 --> 00:06:54.600
So, we have three possibilities for the cookie choice, and then two possibilities for the scoop of ice cream.
00:06:54.600 --> 00:06:59.000
That will give us a total of possible choices of 6; and let's see why that ends up working out.
00:06:59.000 --> 00:07:04.500
We get 3 times 2 equals 6; that is m times n; let's see how this works out.
00:07:04.500 --> 00:07:09.700
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.
00:07:09.700 --> 00:07:11.900
We can do it the other way, and it would work out just as well.
00:07:11.900 --> 00:07:18.400
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.
00:07:18.400 --> 00:07:20.800
We can either have chocolate chip, snickerdoodle, or peanut butter.
00:07:20.800 --> 00:07:25.400
But then, on each one of these choices, we have an expanded two more choices.
00:07:25.400 --> 00:07:32.200
So, if we have chocolate chip, we now have vanilla or chocolate out of that; so that is 2 here.
00:07:32.200 --> 00:07:36.700
If we took snickerdoodle, we now have vanilla or chocolate; so that is 2 here.
00:07:36.700 --> 00:07:40.700
If we took peanut butter, we now have vanilla or chocolate; so that is 2 here.
00:07:40.700 --> 00:07:48.200
So, because we have three possible starting branches, when the next two branches come off, we can just multiply the number for each event.
00:07:48.200 --> 00:07:53.800
There are three possibilities that come out of our cookie choice, and then a further two possibilities on top of each of those.
00:07:53.800 --> 00:08:00.900
So, it would be 3 times 2, for a total of 6 in the end.
00:08:00.900 --> 00:08:05.000
All right, the next idea is the **pigeonhole principle**.
00:08:05.000 --> 00:08:11.700
Let there be some event E that can occur in n ways; we have some event E, and it can happen in n ways.
00:08:11.700 --> 00:08:19.400
Now, if that event happens n + 1 times--it happens one more than the number of ways that the event can turn out;
00:08:19.400 --> 00:08:24.100
so it has n different possibilities for turning out, and then the event happens one more time
00:08:24.100 --> 00:08:30.600
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.
00:08:30.600 --> 00:08:36.600
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.
00:08:36.600 --> 00:08:40.100
But we are guaranteed at least twice in one of the ways.
00:08:40.100 --> 00:08:45.700
Another way to look at this is with boxes and objects; I think this is a little bit easier to visualize.
00:08:45.700 --> 00:08:55.000
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.
00:08:55.000 --> 00:08:57.200
Let's use some numbers here, so that we can see this a little better.
00:08:57.200 --> 00:09:09.500
Let's say we have 3 boxes: 1, 2, 3 boxes; and we are given 4 objects: 1, 2, 3, 4.
00:09:09.500 --> 00:09:18.600
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.
00:09:18.600 --> 00:09:25.300
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,
00:09:25.300 --> 00:09:32.500
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.
00:09:32.500 --> 00:09:38.300
And so, whichever of the three boxes it ends up going into--it doesn't matter which one it ends up going into--
00:09:38.300 --> 00:09:42.300
it is going to end up going into a box that already has another object in there.
00:09:42.300 --> 00:09:46.500
And so, we will know that we had at least two objects.
00:09:46.500 --> 00:09:55.300
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.
00:09:55.300 --> 00:09:59.000
And so, it will end up being true, however we decide to distribute these balls.
00:09:59.000 --> 00:10:02.900
We can be guaranteed that at least one of the boxes has at least 2 objects.
00:10:02.900 --> 00:10:07.200
There might be more boxes that have even more; there might be one box that has all of them.
00:10:07.200 --> 00:10:10.100
But we know for certain that at least one of them has at least 2.
00:10:10.100 --> 00:10:14.800
In many ways, it is just common sense; it seems a little surprising to see in a mathematical context,
00:10:14.800 --> 00:10:17.800
because it just makes such perfect sense to us, intuitively.
00:10:17.800 --> 00:10:22.800
But we can end up saying some pretty surprising things by using this idea, as we will see in Example 5.
00:10:22.800 --> 00:10:27.200
A really quick example, just to see this applied: if we were given four cookies, and each of our cookies was,
00:10:27.200 --> 00:10:32.600
once again, those three choices of chocolate chip, snickerdoodle, and peanut butter;
00:10:32.600 --> 00:10:37.400
then we know, since we were given four cookies, and we only have three possibilities,
00:10:37.400 --> 00:10:41.500
that we have to have at least two of one type of cookie.
00:10:41.500 --> 00:10:47.000
We are going to have to have at least two chocolate chips, or at least two snickerdoodles, or at least two peanut butters.
00:10:47.000 --> 00:10:52.900
We might end up having many in a different kind--we might have 4 chocolate chips or 4 snickerdoodles or 4 peanut butters,
00:10:52.900 --> 00:10:55.600
or two chocolate chips and two snickerdoodles, and no peanut butters.
00:10:55.600 --> 00:11:01.500
But we know for certain that there is at least one thing where we have a pairing on the cookie type.
00:11:01.500 --> 00:11:08.300
All right, first: draw pictures--when working on counting problems, it can help immensely to draw pictures and diagrams.
00:11:08.300 --> 00:11:11.600
Just being able to visualize this stuff can make it a lot easier to understand.
00:11:11.600 --> 00:11:18.600
If you can visually follow the events and choices, if you can see what is going on--how things are branching,
00:11:18.600 --> 00:11:20.600
it is going to make it that much easier to solve problems.
00:11:20.600 --> 00:11:22.100
So, I really recommend drawing pictures.
00:11:22.100 --> 00:11:25.400
Now, that is not to say that you need to draw accurate pictures.
00:11:25.400 --> 00:11:27.700
You don't really want to draw accurate pictures.
00:11:27.700 --> 00:11:32.400
Instead, what you want to do is draw pictures that are going to be pictures or diagrams
00:11:32.400 --> 00:11:39.200
that just let you see how many ways an event can occur, and how it is connected to the other events,
00:11:39.200 --> 00:11:44.700
so that you can see how there are things interrelated, or not interrelated, and how things can occur--
00:11:44.700 --> 00:11:47.700
the number of ways, branching paths...all of those sorts of things.
00:11:47.700 --> 00:11:52.000
Drawing every single possibility, drawing really careful pictures--that is not necessarily the thing.
00:11:52.000 --> 00:11:54.900
You just want something so that you can visualize it and see it on paper.
00:11:54.900 --> 00:12:00.000
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.
00:12:00.000 --> 00:12:01.700
All right, now we are ready for some examples.
00:12:01.700 --> 00:12:06.700
The first example: we have 7 shirts, 3 pairs of pants, and 4 pairs of shoes.
00:12:06.700 --> 00:12:09.700
What is the total number of outfits that you can wear from this selection?
00:12:09.700 --> 00:12:14.900
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,
00:12:14.900 --> 00:12:19.400
because we are going to go outside with it; so we want to have definitely a shirt, definitely pants...
00:12:19.400 --> 00:12:21.700
we are walking outside, so we definitely want shoes, as well.
00:12:21.700 --> 00:12:24.600
So, we are going to have definitely a shirt, definitely pants, and definitely shoes.
00:12:24.600 --> 00:12:29.700
Furthermore, our choice of shirt, our choice of pants, and our choice of shoes have nothing to do with each other.
00:12:29.700 --> 00:12:34.300
They might not look good together, but it would be a possible output we could create.
00:12:34.300 --> 00:12:38.800
Shirt is completely independent from pants, which is completely independent from shoes.
00:12:38.800 --> 00:12:43.100
Each one is a choice completely in and of itself; they don't have an effect on each other.
00:12:43.100 --> 00:12:45.700
So, we can think of it as three separate events.
00:12:45.700 --> 00:12:54.600
First, we have the seven shirts; so we have the choices for shirts, to begin with--we have 7 possible things for shirts.
00:12:54.600 --> 00:13:01.900
And then, next, we have three pairs of pants; so there are a total of...all of our pants choices,
00:13:01.900 --> 00:13:07.000
our "pants event," is 3 different ways for our pants event to turn out.
00:13:07.000 --> 00:13:13.400
And then finally, there are 4 pairs of shoes; there are 4 different ways for our shoes event to turn out.
00:13:13.400 --> 00:13:20.400
We know that we have to end up having a shoes event turn out, and it can turn into four different possibilities.
00:13:20.400 --> 00:13:27.700
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.
00:13:27.700 --> 00:13:31.200
And then, from here, we branch into multiple different choices with the pants.
00:13:31.200 --> 00:13:34.400
And that is going to end up happening on each one of our blue things.
00:13:34.400 --> 00:13:38.500
So then, if we end up following out any one of these, we are going to branch on this.
00:13:38.500 --> 00:13:44.700
So, on every branch, it branches 7 times; and then, each of those branches 3 times, and then each of those branches 4 times.
00:13:44.700 --> 00:13:47.900
That was our fundamental counting principle, the multiplication principle.
00:13:47.900 --> 00:13:54.300
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.
00:13:54.300 --> 00:14:05.300
So, 7 times 3 times 4: we multiply this all out together; we end up getting 84 possibilities.
00:14:05.300 --> 00:14:10.300
So, we have a total of 84 different possible outfits.
00:14:10.300 --> 00:14:16.500
Great; the next question: We are going out to dinner tonight--you are going out to dinner tonight (I am not coming with you).
00:14:16.500 --> 00:14:20.200
Your options for the restaurant are Mexican, Japanese, or French.
00:14:20.200 --> 00:14:22.900
At each restaurant, they have the following number of selections.
00:14:22.900 --> 00:14:31.700
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.
00:14:31.700 --> 00:14:38.200
If you will have one appetizer and one main course, how many ways are there for you to have dinner tonight?
00:14:38.200 --> 00:14:43.700
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.
00:14:43.700 --> 00:14:46.500
If you go out to dinner, you have to choose one restaurant.
00:14:46.500 --> 00:14:55.000
Our very first thing is that we actually have a restaurant choice; so restaurant breaks into 3 different possibilities.
00:14:55.000 --> 00:14:59.600
We can either go to the Mexican, the Japanese, or the French.
00:14:59.600 --> 00:15:11.100
If we go to Mexican, we will have that one here; and then, we could also have gone to Japanese;
00:15:11.100 --> 00:15:16.500
and then finally, we could have gone to French.
00:15:16.500 --> 00:15:24.800
And then, we were told that, when you are out at dinner, you are going to have one appetizer and one main course.
00:15:24.800 --> 00:15:28.400
Now, the choice of appetizer has no effect on the choice of main course, necessarily.
00:15:28.400 --> 00:15:30.700
You could choose any appetizer to go with any main course.
00:15:30.700 --> 00:15:35.100
They might not fit together, but it doesn't matter; you could choose it, so they are independent events.
00:15:35.100 --> 00:15:39.300
One of them does not necessarily change the way the other one can turn out.
00:15:39.300 --> 00:15:45.900
For the Mexican choice, if you went with Mexican, you would have four choices for your appetizer.
00:15:45.900 --> 00:15:53.100
And then, you would have 10 choices for your main course: 4 appetizers, and then 10 main courses.
00:15:53.100 --> 00:16:02.000
The same thing for the Japanese, but different numbers: we have 3 choices (let me make this a little bit bigger)
00:16:02.000 --> 00:16:07.500
for the appetizer, and then we have 7 choices for the main course.
00:16:07.500 --> 00:16:15.800
Finally, the French restaurant: if you had gone there, you would have 8 choices for the appetizer and 5 choices for the main course.
00:16:15.800 --> 00:16:22.200
So, if you had gone to Mexican, you would have 4 times 10 total possibilities at the Mexican restaurant.
00:16:22.200 --> 00:16:28.700
If you had gone to Japanese, you would have 3 times 7, or 21, total possibilities if you had gone to the Japanese restaurant.
00:16:28.700 --> 00:16:34.200
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.
00:16:34.200 --> 00:16:37.900
But you don't have to go to any one of these, necessarily.
00:16:37.900 --> 00:16:41.800
At the beginning, you have this branching choice: you have an exclusive choice,
00:16:41.800 --> 00:16:45.800
where you can choose one of the restaurants, but you can't choose multiple of the restaurants.
00:16:45.800 --> 00:16:48.900
So, you could go down Mexican and get to the Mexican set of choices.
00:16:48.900 --> 00:16:51.600
You could go down Japanese and get to the Japanese set of choices.
00:16:51.600 --> 00:16:53.900
Or you could go down French and get to the French set of choices.
00:16:53.900 --> 00:17:00.500
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.
00:17:00.500 --> 00:17:09.100
So, we end up having 40 from the Mexican, plus 21 from the Japanese, plus 40 from the French,
00:17:09.100 --> 00:17:15.200
which comes out to be a total of 40 + 40 (80) + 21: 101 choices;
00:17:15.200 --> 00:17:21.100
so you have 101 total choices for dinner tonight, total ways to have dinner,
00:17:21.100 --> 00:17:25.400
because you could go to any of the three restaurants; and then, once you are at each of the restaurants,
00:17:25.400 --> 00:17:28.700
you then have an independent choice between appetizer and main course.
00:17:28.700 --> 00:17:32.300
So, at the end, we have to add them all back up together.
00:17:32.300 --> 00:17:36.800
The next example: At a computer store, you are going to buy speakers, a monitor, and a computer.
00:17:36.800 --> 00:17:41.200
There are four options for speakers, seven for monitors, and two for computers.
00:17:41.200 --> 00:17:48.400
One of the computers gives a choice between one of two operating systems, while the other has one of three operating system options.
00:17:48.400 --> 00:17:52.300
So, if you buy one of the computers, you can choose between one of two things on top of it.
00:17:52.300 --> 00:17:56.500
And if you buy the other computer, you are allowed to choose one of three things on top of it.
00:17:56.500 --> 00:17:58.900
How many total ways are there to make your purchase?
00:17:58.900 --> 00:18:02.300
Now, of course, if you buy a computer, you have to have an operating system with it.
00:18:02.300 --> 00:18:05.500
So, we are guaranteed that we are going to get some operating system.
00:18:05.500 --> 00:18:08.600
With that in mind, how can we figure out how many ways to make a purchase?
00:18:08.600 --> 00:18:16.000
Well, if we go in the order that this comes, we see that we have speakers; we buy speakers,
00:18:16.000 --> 00:18:23.300
and we have...how many ways?...there are four options for speakers;
00:18:23.300 --> 00:18:27.300
and then we have the monitors; we look at it--we have...
00:18:27.300 --> 00:18:30.700
oh, oops, there are four options, not seven; I was accidentally reading monitors.
00:18:30.700 --> 00:18:34.100
We have four for speakers, and then we have seven for monitors.
00:18:34.100 --> 00:18:39.500
And then, the computers: you have two options for the computers.
00:18:39.500 --> 00:18:43.100
But then, we have this whole thing about the OS, the operating system, of it.
00:18:43.100 --> 00:18:49.500
Our operating system comes into this, as well: operating system branches, depending on which computer you had bought.
00:18:49.500 --> 00:18:54.000
If you bought the first computer or the second computer, you are going to have different numbers of options here.
00:18:54.000 --> 00:18:56.900
So, you could have 2 here or 3 here.
00:18:56.900 --> 00:19:00.100
With that in mind, it gets a little confusing to figure out how we want to work this out.
00:19:00.100 --> 00:19:05.100
Let's have our first thing be the computer choice; we will say computer choice determines everything else,
00:19:05.100 --> 00:19:09.000
because speakers and monitors are completely independent of which computer you choose.
00:19:09.000 --> 00:19:12.900
The operating system choice, though, does depend on which computer you chose.
00:19:12.900 --> 00:19:15.500
So, we will start with choosing a computer choice.
00:19:15.500 --> 00:19:20.600
We have our computer choice, which splits into one of two possibilities.
00:19:20.600 --> 00:19:28.600
It splits into the two OS possibility, or it splits into the three OS possibility.
00:19:28.600 --> 00:19:34.300
We have the operating system; over here, there are two possible operating systems.
00:19:34.300 --> 00:19:38.100
Over here, though, there are three possible operating systems.
00:19:38.100 --> 00:19:44.400
Next, we have speakers for both of them; there are going to be four choices for speaker and four choices for speaker.
00:19:44.400 --> 00:19:48.800
And for monitor, we have seven choices for the monitor and seven choices for the monitor,
00:19:48.800 --> 00:19:52.200
because that has no effect on which of the two computers we had initially bought.
00:19:52.200 --> 00:19:59.000
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.
00:19:59.000 --> 00:20:01.600
We have created that branching, and now we are reading both of them.
00:20:01.600 --> 00:20:06.800
What we do is figure out how many options we have if we had bought the 2-operating-system computer.
00:20:06.800 --> 00:20:10.500
How many options do we have if we had bought the 3-operating-system computer?
00:20:10.500 --> 00:20:14.100
And then, we add those two together to figure out the total number that we have.
00:20:14.100 --> 00:20:26.200
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.
00:20:26.200 --> 00:20:34.500
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.
00:20:34.500 --> 00:20:37.500
So, that comes out to 84 choices.
00:20:37.500 --> 00:20:42.800
If we want to have the possibility of choosing between one of the two computers at first, well, that changes what happens later on.
00:20:42.800 --> 00:20:51.100
So, that has to count as an either/or event; we can only choose one of the two.
00:20:51.100 --> 00:20:55.700
We have the 2-operating-system possibility (56) and the 3-operating-system possibility (84).
00:20:55.700 --> 00:21:00.200
If we want to be able to have an option between choosing which of those two paths we go down, we add them together.
00:21:00.200 --> 00:21:09.700
So, we have the 56 options for the 2-operating-system, added to the 84 options for the 3-operating-system.
00:21:09.700 --> 00:21:14.400
We add those together, and we get 140 total possibilities.
00:21:14.400 --> 00:21:21.600
We have 140 total possible ways to make this purchase, when we include all of the different options that we have at our disposal.
00:21:21.600 --> 00:21:28.800
The next example: On an exam, there are 25 multiple-choice questions, each one of them having 5 choices that you can answer with.
00:21:28.800 --> 00:21:33.400
Now, assuming that we count not putting down any choice as an option for answering a question
00:21:33.400 --> 00:21:38.700
(because it is, in a way, a choice that you have made--not putting anything down is a choice,
00:21:38.700 --> 00:21:45.000
just as much as marking A or C or E)--if that is the case, we are going to assume that not putting down something
00:21:45.000 --> 00:21:51.200
counts as an option for answering a question--with that in mind, how many ways total are there to mark the answer sheet?
00:21:51.200 --> 00:21:56.600
There are 25 different times that we have the chance to answer.
00:21:56.600 --> 00:22:03.000
For our first one, well, let's look at it as...we have 25 different slots, effectively,
00:22:03.000 --> 00:22:07.200
each of our slots representing all of the choices that we have for answering.
00:22:07.200 --> 00:22:16.600
This is going to keep going, going, going; there are a total of 25 slots that we are dealing with,
00:22:16.600 --> 00:22:19.700
because each of the questions is a slot that gets answered.
00:22:19.700 --> 00:22:25.100
OK, so with that in mind, we are going to say, "How many ways can we answer the first question?"
00:22:25.100 --> 00:22:33.700
Well, the first question...we are allowed to count not putting down a choice; we count not putting a choice as an option.
00:22:33.700 --> 00:22:38.500
So, if that is the case, and there are 5 choices (A, B, C, D, E) for each one of these,
00:22:38.500 --> 00:22:42.500
and we count not putting down something as an additional option,
00:22:42.500 --> 00:22:48.600
then that means that there is a total of 6 for one of these questions: A, B, C, D, E, nothing at all.
00:22:48.600 --> 00:22:50.600
That is a total of 6 possibilities.
00:22:50.600 --> 00:22:55.400
What about the next question--is the next question affected by the way that we answered the previous question?
00:22:55.400 --> 00:22:58.200
Not at all; you can mark that answer any way you want.
00:22:58.200 --> 00:23:06.100
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.
00:23:06.100 --> 00:23:10.000
There are 6 choices for each one of the 25 questions that we are answering,
00:23:10.000 --> 00:23:13.800
6 times 6 times 6 times 6...because each one is an independent event,
00:23:13.800 --> 00:23:17.700
so we multiply them all together to figure out how many possible things there are.
00:23:17.700 --> 00:23:26.600
What we have is 6 times 6 times 6...going all the way out to more 6's.
00:23:26.600 --> 00:23:36.600
We have a total of 25 6's multiplied together.
00:23:36.600 --> 00:23:45.200
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 6^25.
00:23:45.200 --> 00:23:52.100
So, there are a total of 6^25 ways to answer this set of questions.
00:23:52.100 --> 00:23:55.600
There are 6^25 ways to mark up this answer sheet.
00:23:55.600 --> 00:23:59.400
How many does that come out to be?--it is a little hard to see just how large 6^25 is.
00:23:59.400 --> 00:24:10.300
6^25, if we use a calculator to get an approximate value for that--that comes out to be 2.8x10^19 possibilities,
00:24:10.300 --> 00:24:13.900
which is an absolutely staggering number; that is a huge number.
00:24:13.900 --> 00:24:19.600
If we were to count this out, it would have 19 0's: 1, 2...actually, it would have 18 zeroes,
00:24:19.600 --> 00:24:37.000
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.8x10^19.
00:24:37.000 --> 00:24:40.600
So, we would end up having this incredibly massive number of choices.
00:24:40.600 --> 00:24:42.100
I can't even figure out...how many is that?
00:24:42.100 --> 00:24:54.000
That is ones, thousands, millions, billions, trillions, quadrillions...28 quintillion choices for the ways that we could answer this, with only 25 questions.
00:24:54.000 --> 00:25:00.500
So, that is a massive, massive number of possibilities here, which gives us an idea of just how fast things can grow.
00:25:00.500 --> 00:25:03.100
This is why we don't want to have to count this stuff by hand.
00:25:03.100 --> 00:25:08.900
It is because these numbers can get really big really fast in things that seem really simple; cool.
00:25:08.900 --> 00:25:16.000
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.
00:25:16.000 --> 00:25:18.700
This will require a little bit of research.
00:25:18.700 --> 00:25:24.200
This seems kind of like a weird thing at first; we see this use-the-pigeonhole principle after researching.
00:25:24.200 --> 00:25:27.100
That is going to be a hint that we are going to want to use the pigeonhole principle.
00:25:27.100 --> 00:25:32.500
A little bit before we get into this, let's consider the idea of if we were talking about birthdays.
00:25:32.500 --> 00:25:35.300
That will help us understand what is about to happen in just a moment.
00:25:35.300 --> 00:25:42.700
If we were talking about birthdays, if we had...let's say that there are only 365 days that you can be born on.
00:25:42.700 --> 00:25:48.100
We are forgetting about leap years, because we are assuming that we slide that to either the day before or the day after.
00:25:48.100 --> 00:25:51.100
There are 365 days that you can be born on.
00:25:51.100 --> 00:26:00.100
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.
00:26:00.100 --> 00:26:03.900
Now, there might be more birthdays that are concurrent--people that have the same birthday.
00:26:03.900 --> 00:26:09.900
But we can be guaranteed that there is at least one pair, because if we have 365 effective slots
00:26:09.900 --> 00:26:17.500
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."
00:26:17.500 --> 00:26:21.300
Then, at least two people are going to end up having to be in that same box.
00:26:21.300 --> 00:26:24.100
They are going to have to end up occupying the same birthday.
00:26:24.100 --> 00:26:28.800
Otherwise, it just doesn't make sense; that is the pigeonhole principle in action,
00:26:28.800 --> 00:26:34.900
this idea that if we are stuffing things into pigeonholes (being a little place for a message, a long time ago)--
00:26:34.900 --> 00:26:41.000
if we stuffed ten messages into nine pigeonholes, there is going to have to be
00:26:41.000 --> 00:26:45.500
some pigeonhole that has multiple messages in it--at least 2 messages.
00:26:45.500 --> 00:26:53.200
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.
00:26:53.200 --> 00:26:58.700
Now, let's start thinking about this one: we are talking about hairs on heads, and we are talking about London.
00:26:58.700 --> 00:27:03.800
First, let's look into hairs on heads: we look into how many hairs are on a human head.
00:27:03.800 --> 00:27:19.400
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.
00:27:19.400 --> 00:27:24.800
Now, of course, this number can be higher; this number can be lower; but it doesn't get much higher than 100,000.
00:27:24.800 --> 00:27:28.500
200,000--pretty much no one is going to have 200,000 hairs.
00:27:28.500 --> 00:27:36.100
So, it starts to limit out pretty quickly; around 100,000 hairs is about the normal amount for a human head.
00:27:36.100 --> 00:27:41.000
And 150,000 would be a lot of hair; more than that just starts to become ridiculous and really hard.
00:27:41.000 --> 00:27:44.900
We figured that out with just a little bit of Internet research--some cursory research.
00:27:44.900 --> 00:27:47.800
We figured out pretty quickly that it looks to be about 100,000.
00:27:47.800 --> 00:27:54.000
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.
00:27:54.000 --> 00:28:06.400
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.
00:28:06.400 --> 00:28:10.600
There can't be more than a million hairs on a human head.
00:28:10.600 --> 00:28:15.800
So, there have to be a million hairs or less on a human head.
00:28:15.800 --> 00:28:20.400
There can be anywhere between 0 (you can't have less than 0 hairs on your head) up to a million.
00:28:20.400 --> 00:28:24.900
And a million is actually a ridiculously large number; no one is going to actually have a million at all.
00:28:24.900 --> 00:28:29.000
But let's set it up to a high point that is ridiculous, because if we can show that this is true,
00:28:29.000 --> 00:28:34.900
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.
00:28:34.900 --> 00:28:37.200
We can set a higher set.
00:28:37.200 --> 00:28:40.700
The next idea: let's look at the population in London.
00:28:40.700 --> 00:28:54.100
The population in London, as of the writing of this video is a little bit over 8 million.
00:28:54.100 --> 00:28:58.700
It is around 8.1 million--a little more than that; so it is around 8 million; it is over 8 million.
00:28:58.700 --> 00:29:02.200
Because of this, we now know, by the pigeonhole principle, that there are
00:29:02.200 --> 00:29:06.400
at least two people in London who have the exact same number of hairs on their head.
00:29:06.400 --> 00:29:08.300
Why? Well, let's look at it like this.
00:29:08.300 --> 00:29:14.500
We can think of that absolute maximum of 1 million hairs as being a bunch of different boxes.
00:29:14.500 --> 00:29:24.800
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,
00:29:24.800 --> 00:29:34.600
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.
00:29:34.600 --> 00:29:38.000
So, we have all of these different boxes that a person can go into.
00:29:38.000 --> 00:29:41.800
We are counting all the way up from 0, up until 1 million hairs.
00:29:41.800 --> 00:29:45.300
We know that, if it is a human, they are going to have to go in one of these boxes,
00:29:45.300 --> 00:29:51.100
because the absolute maximum number of hairs (and this is ridiculous number) would be that a person has a million hairs on their head.
00:29:51.100 --> 00:29:54.200
That is too large, but we know that the absolute maximum number of boxes
00:29:54.200 --> 00:29:59.200
that we have to have here is from 0 up until a million, to mark out the number of hairs on a head.
00:29:59.200 --> 00:30:03.000
Now, we know that the population of London is over 8 million.
00:30:03.000 --> 00:30:13.200
That means, when we go through the first one million and one people, then unless they already end up
00:30:13.200 --> 00:30:17.500
with two people having the same number of hairs on their heads, in the first million and one people,
00:30:17.500 --> 00:30:22.700
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.
00:30:22.700 --> 00:30:29.000
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.
00:30:29.000 --> 00:30:33.000
Someone else will end up having to have that same box with somebody else.
00:30:33.000 --> 00:30:37.400
They will have to share; so we have the exact same number of hairs guaranteed.
00:30:37.400 --> 00:30:45.300
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.
00:30:45.300 --> 00:30:50.600
It is pretty wild; in fact, because it is over 8 million, we could show that there are, in fact,
00:30:50.600 --> 00:30:57.200
at least 8 people who have the exact same number of hairs on their head, right this instant--kind of surprising.
00:30:57.200 --> 00:31:03.300
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.
00:31:03.300 --> 00:31:07.000
It is pretty cool; now, of course, there is no practical application to this immediately.
00:31:07.000 --> 00:31:09.700
We couldn't actually find these two people with any ease.
00:31:09.700 --> 00:31:15.200
But it is interesting to know that there is this guarantee that, because there are so many people in London,
00:31:15.200 --> 00:31:19.000
and there are just not that many hairs on the human head--there are more people in London
00:31:19.000 --> 00:31:27.100
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.
00:31:27.100 --> 00:31:33.200
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.
00:31:33.200 --> 00:31:36.000
All right, cool; we will see you at Educator.com later--goodbye!