For more information, please see full course syllabus of Pre Calculus
For more information, please see full course syllabus of Pre Calculus
Counting
- 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 E_{1} and E_{2}, where E_{1} can occur in m ways and E_{2} can occur in n. If precisely one of the events will occur (not both), the total possible ways for something to occur is
m+n. - Multiplication Principle [AKA Fundamental Counting Principle]: Let there be two events E_{1} and E_{2}, where E_{1} can occur in m ways and E_{2} 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
m·n. - 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.
Counting
- The most difficult part of this problem is probably just the English. If a word is unfamiliar to you but it seems important to what's going on, look it up! The first step to doing any problem is making sense of it, and that includes understanding the vocabulary. The word `trailhead' is somewhat uncommon, but if we look it up, we discover that it just means "the starting place for a trail". Since the problem is asking about hikes, and a hike takes place on a trail, each trailhead represents a possible hike.
- From there, the problem is quite simple. We start off with three initial choices-east, north, or west. Depending on which direction we choose, it determines how many choices we have for a hiking trail. Since choosing one direction precludes going on hikes from the other directions, we use the addition principle: just add up the number of choices for each direction.
- Each direction has the following number of trail choices:
Since you can only choose one category (east or north or west), we add them together to find the total number of choices:East: 5, North: 7, West: 4
Thus there are 16 possible trails to choose, so 16 different hikes.5 + 7 + 4 = 16
- For purchasing the bike, you have two choices to make: the model of the bicycle and the color of the bicycle. Notice that choosing a different choice for either of these qualities will result in a different bike.
- Still, the first choice of model has no effect on the second choice for color. Any color can be picked for any of the bike models. Thus, because both choices must occur and neither has any effect on the other, we can use the multiplication principle.
- The number of ways the model can be chosen is 4. Count up the colors to find that there are a total of 6 ways to choose a color. Thus, since the two choices do not affect each other, we multiply them:
4 ·6 = 24
- For choosing your dinner, you have three choices to make: which appetizer, which main course, and which dessert. Notice that choosing something different in any of these categories will result in a different dinner.
- Still, each choice has no effect on the other choices. You can pick any appetizer and still go on to pick any main course and any dessert, and similarly for the other two. Thus, because each choice must occur and none of them have any effect on the others, we can use the multiplication principle.
- The number of choices for the appetizer is 8, the number of choices for the main course is 12, and the number of choices for the dessert is 5. Since each choice does not affect the others, we multiply them:
8 ·12 ·5 = 480
- The family has to begin by making a choice between staying at a campground or a hotel. Choosing a campground means they won't choose a hotel, and choosing a hotel means they won't choose a campground. This means we can separate the two into two different categories and count them separately.
- If they stay at a hotel, they also have to choose what type of room they stay in. Since each room type is available at all the hotels, the hotel choice does not affect the room choice, and vice-versa. Thus, we use the multiplication principle to find the total number of ways to stay in a hotel:
Ways to stay in a hotel: 8 ·2 = 16 - Since choosing campground or hotel means the other event will not occur, we use the addition principle: count the number of ways to camp then add it to the number of ways to stay in a hotel:
[# campground ways] + [# hotel ways] = 3 + 16 = 19
- Jack needs to take a class from some teacher during some timeslot. To begin with, he has a choice of which school he attends: "Three Storms" or "Buckaroo". Thus we can count how many ways he can take a class at each school, then add the two together to get the total number of ways:
Total # of ways = [# ways at "Storms"] + [# ways at "Buckaroo"] - Let's figure out how many ways he can take a class at "Three Storms" first. At that school, there are three teachers he can choose from, and each has four timeslots. Since the choice of teacher does not affect how many timeslots he has access to, we multiply them together to find the total number of ways:
We do the same thing for the other school. At "Buckaroo" there are six teachers he can choose from, and each has three timeslots. Since the choice of teacher does not affect the number of timeslots, we multiply:# ways at "Storms" = 3 ·4 = 12 # ways at "Buckaroo" = 6 ·3 = 18 - Now that we know how many choices he has at each school, we can add them together to find the total number of choices.
Total # of ways = 12 + 18 = 30
- Since you respond to every question and it is a true/false test, there are precisely two possible choices for each question on the test.
- The choice of answer on each question has no effect on the other questions. For example, if you answer `true' on one question, you can still choose to answer either `true' or `false' on all the other questions. Therefore, since you will answer each question on the test and each of the questions has no effect on the others, we can calculate the total number of ways with the multiplication principle.
- For each question, take the number of ways it can be answered, then multiply that by all the others. Since each question can be answered in two ways, we have
2 ·2 ·2 ·2 ·2 ·2 ·2 ·2 ·2 ·2 = 2^{10} = 1024
- Each number choice in the combination has no effect on the other number choices. For example, if the first number is `47', the next number can be anything at all, including `47' again. Thus there are 60 possible choices for each of the four numbers in the combination.
- Since the choice of each number has no effect on the others and all four choices must occur, we can calculate the total number of ways with the multiplication principle. For each choice, take the number of ways it can be picked, then multiply it by all the others. Since each choice can be picked in one of 60 ways, we have
60 ·60 ·60 ·60 = 60^{4} = 12 960 000 - We follow the exact same logic for figuring out the total possible ways when the combination is five numbers long:
60 ·60 ·60 ·60 ·60 = 60^{5} = 777 600 000
- Begin by noticing that the choice for each character has no effect on the choice of any of the others. For example, if a `7' is chosen for the first number slot, we can still choose any letter (other than the excluded ones) for the subsequent letters and any number for the subsequent numbers. Since every choice must be made and none of them affect the other choices, we use the multiplication principle.
- For each number in the license, there are 10 possible choices (since it comes from the numbers 0-9). For each letter in the license, there are 23 possible choices (since the alphabet has 26 letters, but we were told I, O, and Q are excluded).
- Since the choice of each character has no effect on the others, take the number of ways each can be picked, then multiply it by all the others:
10 ·23 ·23 ·23 ·10 ·10 ·10 = 10^{4} ·23^{3} = 121 670 000
- Unlike the previous problems we've worked on, the choice for who wins each place in the race does affect the other choices. Winning first place means that person cannot also win second or third. We can not just say there are eight possibilities for each of three choices and get 8·8 ·8: each choice affects the others, so we can't naively apply the multiplication prinicple without taking that into account. However, if we think about it carefully, we can still use the multiplication principle. Start off by thinking about the different places in order. Think about first, then second, then third.
- If we look at first place before the others, it's easy to see how many options there are: there are eight competitors, so eight people could potentially take first place. Thus we have 8 options for the first choice. With that in mind, let's now consider second place. Since we already assigned a winner to first place, notice that there are only seven competitors remaining. This will be true no matter who won first place, because winning will take that person out of the running. Thus we don't have to care about the specific winner of first, we just need to acknowledge that there are now only seven possibilities for second. Thus we have 7 options for the second choice.
- Following the same logic, we will only have six competitors remaining for third place. Thus we have 6 options for the third choice. To find the total number of possibilities, we multiply the number of options for each choice with the others:
8 ·7 ·6 = 336
- Notice that if Sally pulls two socks from the drawer, she won't necessarily have a pair of socks that match in color. For example, she could pull out one orange and one blue. Similarly, if she pulls out three socks, they still won't necessarily match: orange, blue, and tan. We are looking for how many socks she must pull out to be absolutely sure she will have a matching pair in what she has pulled out.
- If you think it's simple to find the answer to this, you're right! We know that the socks can come in a total of six different colors (black, white, tan, red, orange, and blue): therefore the most socks she can have without pulling a matching pair is six-one of each color. As soon as she pulls the seventh sock, it absolutely must match with one of the previous socks. Thus Sally must pull out 7 socks to guarantee a match. [Notice that she might achieve a match before pulling out seven socks, it's just that she can only guarantee a match by pulling out seven.] [If you're curious to see a slightly more formal explanation/proof, check out the next step. The above does a great job of relying on intuition, but sometimes you need to prove it more carefully.]
- To formally prove this, we can use the pigeonhole principle. Consider each of the colors as a category "box". We have a total of 6 boxes, one for each color. Each sock that is pulled is put into the matching color box. As soon as we pull 6+1 = 7 socks, we know there must be at least one box with (at least) two objects in it: our matching pair. This fact comes from the pigeonhole principle, which guarantees if something can occur in n ways and the event happens n+1 times, it must repeat at least one of the ways.
*These practice questions are only helpful when you work on them offline on a piece of paper and then use the solution steps function to check your answer.
Answer
Counting
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
Precalculus with Limits Online Course
Transcription: Counting
Hi--welcome back to Educator.com.0000
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, E_{1} and E_{2}, where E_{1} can occur in m ways,0221
and E_{2} 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 E_{1} or E_{2},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, E_{1} and E_{2}:0345
once again, E_{1} can occur in m ways, and E_{2} 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 have...how 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 6^{25}.1416
So, there are a total of 6^{25} ways to answer this set of questions.1425
There are 6^{25} 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 6^{25} is.1435
6^{25}, if we use a calculator to get an approximate value for that--that comes out to be 2.8x10^{19} 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.8x10^{19}.1459
So, we would end up having this incredibly massive number of choices.1477
I can't even figure out...how 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 Educator.com later--goodbye!1893
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!