|
Counting and Probability I
By Keone Hon
1. How do you count?
Suppose you had a handful of marbles. How would you count them? Would you go 1, 2, 3, 4,…? Or would you count by twos, like 2, 4, 6,…? Or would you count by fives, like 5, 10, 15,…? It should be clear that there are many ways of counting objects. The goal of this lecture is to discuss some of them and apply them to problems you may encounter during your careers as math competitors.
Consider, then, the problem of counting hundreds of thousands of marbles. Would you still count 1, 2, 3, …? If you try, I wish you the best of luck. You'll be at it for a while. Instead, if you were to count by thousands or tens of thousands, you'd be more successful.
2. Simple ones
Here's a problem:
How many integers are there between 12 and 48, inclusive?
First off, there are some confusing words in there. What does inclusive mean? Well, inclusive means you include the numbers on the end, that is, 12 and 48. On the other hand, if the problem had said exclusive, it would mean that you don’t include 12 and 48. But that is not the case.
So what the problem is really asking is “how many integers are there in 12, 13, 14, …, 47, 48?”.
Now I can do this problem. Suppose I label the numbers in the sequence, like so:
1 2 3 4 5
12, 13, 14, 15, 16, … , 47, 48
Looking at these numbers, we notice a pattern: 12 corresponds to 1, 13 to 2, 14 to 3, and so on, therefore the number on the top is 11 less than the number on the bottom. Using this, we figure that the number on top of 48, the last number, is 48 – 11 = 37.
So we fill in
1 2 3 4 5 36 37
12, 13, 14, 15, 16, … , 47, 48
From this, we can see that there are exactly 37 numbers in the sequence of 12 to 48, inclusive.
Here’s a similar problem:
How many integers are there from 467 to 837, inclusive?
Don’t be intimidated by the big numbers! It’s really just the same problem as before, only with a few numbers switched around.
I label the numbers the same way as I did last time:
1 2 3 4
467, 468, 469, 470, … 837
What did I do to get from each bottom number to the number above it? Well, I subtracted 466, since 467 – 466 = 1, 468 – 466 = 2, 469 – 466 = 3, etc. So the number above 837 should be _____. Since this is all the numbers from 1 to _____, there are ____ numbers in between 467 and 837.
Example: How many integers are there between 25 and 98, inclusive?
Now that you’ve seen that method in action a few times, I’ll shorten it a little. Say I had started labeling the numbers in the previous problem starting with 0, like this:
0 1 2 3
467, 468, 469, 470, … 837
What did I do this time? Well, I subtracted 467, since 467 – 467 = 0, 468 – 467 = 1, etc. So what number belongs on top of 837? Well, it’s whatever 837 – 467 is.
How many terms are here? Ignoring the zero for a moment, we have 1, 2, 3, and so on up through 837 – 467. So without the zero, we have 837 – 467 terms. And since we had previously ignored the zero, there is one more term. Thus, there are 837 – 467 + 1 terms between 467 and 837.
Is there a pattern here? We investigate by looking for the numbers between a and b, inclusive.
a, a+1, a+2, …, b
If we start numbering from 0, we have
0 1 2 b-a
a, a+1, a+2, …, b
So there are 1 + b-a terms, i.e. the number of integers between one number and another, inclusive, is just their difference, plus 1. We summarize this in the following theorem:
Theorem 1
There are b – a + 1 integers between a and b, inclusive. (Where b>a.)
In the previous examples, we talked about the number of integers, inclusive. What if we had picked exclusive? Well, there is only a small difference between inclusive and exclusive: exclusive always leaves out the two numbers on the end. So there should always be two fewer integers in the exclusive case than the inclusive case. Since there are b – a + 1 integers in the inclusive case, there are (b – a + 1) – 2 = b – a – 1 integers in the exclusive case. Thus:
Theorem 2
There are b – a – 1 integers between a and b, exclusive. (Where b > a.)
One more example:
How many integers are there between 51 and 416, exclusive?
Now that we have formulas, this should be a piece of cake. This is the exclusive case, so there are 416 – 51 – 1 = 364 integers
Some problems for you to try:
1. How many integers are there between 123 and 720, inclusive? Exclusive?
2. How many integers are there between 495 and 1002, exclusive?
3. How many integers are there between 49.5 and 100.2, inclusive? (Careful!)
Now, it’s great that we can determine the number of integers between two given integers, but not all problems are going to be like that. We move on to something rather different:
3. Choices by Multiplication
Suppose I flip a standard (2-sided) coin once. How many possibilities are there?
Well, I could get heads, or I could get tails, so there are
2 possibilities. Surprised?
Suppose I flip a standard coin twice. How many possibilities are there now?
Abbreviating heads as H and tails as tails, there are 4 choices: HH, HT, TH, and TT.
What if I flip the coin three times? How many possibilities now?
We could list: HHH, HHT, HTH, HTT, THH, THT, TTH, TTT. Therefore there are 8 choices.
What about four flips?
This is starting to get irritating, isn’t it? I don’t want to list a bunch of possibilities. There must be a better way.
[See the tree diagram.]
Thus, there are 2*2*2*2 = 16 possibilities.
I have a standard six-sided die. How many possibilities are there if I roll it twice?
There are six possibilities for each roll, so for two rolls, there are 6*6 = 36 possibilities.
What if I roll the die three times?
Again, there are six possibilities for each roll, so for three rolls, there are 6*6*6 = 216 possibilities.
This doesn’t just apply to dice and coins. Consider the following problem:
Joe is at a restaurant with 3 different main courses, 4 different drinks, and 2 different desserts. How many ways are there for him to pick one main course, one drink, and one dessert?
The total number of possibilities is just (# ways of picking a main course)*(# ways of picking a drink)*(# ways of picking a dessert) = 3*4*2 = 24
How many four letter “words” are possible using a standard 26-letter alphabet?
There are 26 choices for the first letter, 26 choices for the second letter, 26 for the third, and 26 for the fourth, so there are 26*26*26*26 = 264 = 456976 possibilities in all.
We can summarize these results as follows:
Theorem 3
If there are a1 ways of choosing item #1, a2 ways of choosing item #2, a3 ways of choosing item #3, etc., then there are a1 × a2 × a3 × … possibilities in all.
Problems for you to try
1. In how many ways can Sara go through points A, B, C, and D (in that order) if there are three paths from A to B, two from B to C, and six from C to D?
2. How many possibilities are there if I roll two standard dice and flip three standard coins?
3. How many ways can Jane pick a meal from Burger Bob’s if a meal consists of one entrée, one side, one drink, one kind of ice cream, and one toy, and Burger Bob offers three kinds of entrées, seven different sides, four drinks, two kinds of ice cream, and three toys?
4. Distinct Objects
Four children are going to give their presentations on the Roman Empire. In how many different orders can they make their presentations?
There are four places that a student can present: first, second, third, or fourth. There are four people to fill those four places. So there should be 4*4*4*4 different orders, right?
WRONG! The method we used above doesn’t work for these kinds of problems because once a person makes their presentation, they can’t make it again. For example, Emily could not present her project all four times!
We need to use a different method to find the number of possibilities. I’ll draw a couple of lines to represent each place.
______, ______, ______, ______
1st 2nd 3rd 4th
There are four choices for first, since any one of the four students can make their presentations in this spot. So we fill in:
___4__, ______, ______, ______
Regardless of which unlucky soul we chose to go first, we know that only three people remain. So there are only three choices for the second spot.
___4__, ___3__, ______, ______
Now only two remain, so there are two choices for the third spot.
___4__, ___3__, ___2__, ______
The remaining person must go last, so there is only one choice
___4__, ___3__, ___2__, ___1__
In all, there are 4 choices for the first spot, 3 for the second, 2 for the third, and 1 for the fourth, for a total of 4*3*2*1 = 24 possible orders.
Another example:
The pirates are at it again! They have captured the captain, the first mate, the cook, the stowaway, and an oarsman, and they are going to make every one of them walk the plank. How many possible orders are there for walking the plank?
Like the previous problem, we draw some lines to represent each place.
__ __ __ __ __
There are five choices for the first plank-walker, four for the second, three for the third, two for the fourth, and one for the last, so there are
_5_*_4_*_3_*_2_*_1_ = 120 possible orders.
As in the previous problem, the captain, the first mate, the cook, the stowaway, and an oarsman are all being forced to walk the plank. But just as the first sailor is about to jump, the captain cries “I shall be first; ‘tis my captain’s honor”. Then the first mate shouts “and I shall follow him; ‘tis my duty”. If the pirates comply with the sailors’ requests, how many possible orders are there?
Since the captain must go first and the first mate must go second, there is one choice for the first plank-walker and one for the second. Then, since there are three left, there are three choices for third. Then, since there are two left, there are two choices for fourth. The remaining person must go last, so there is only one choice for last. In all, there are
_1_*_1_*_3_*_2_*_1_ = 6 possible orders.
I have five different colors of M&Ms, and I want to give a different color to each of four people. How many ways can I do this?
Let the lines represent the four people.
___ * ___ * ___ * ___
(P1) (P2) (P3) (P4)
There are 5 choices for person 1, since I can give him/her any of the five different colors. After that, I only have four choices, since one color is already used up, so there are 4 choices for person 2. Then, I have 3 choices for person 3 and 2 choices for person 2.
_5_ * _4_ * _3_ * _2_ = 120 ways.
In general, when you try to solve these problems, draw the lines and figure out the number of possibilities for each line.
5. What’s the Difference?
In sections 3 and 4, our method of solving the problems was the same: first, we determined the number of choices for each pick, then we multiplied the number of choices for each pick together. The only real difference is that in section 3, the number of choices was not affected by the outcome of previous choices, while in section 4, it was. (For instance, when flipping a standard coin, there are always two choices, whereas when picking people to walk the plank, there are a varying number of choices because some of the people have already walked the plank.)
6. Probability
The probability of an event is simply the number of times that the event will happen out of a total number of outcomes.
For instance, the probability of rolling a 1 with a single die is 1/6, since there are six possible outcomes and only one of them results in a roll of a 1.
Example: If I have five M&Ms in a cup, and one of them is red, what is the probability that I will pull a red M&M out of the cup in one try?
When I reach into the cup, I can pull any of the five M&Ms out, so there are five possible outcomes. Since only one M&M is red, the probability of be pulling a red M&M out is 1/5.
Example:
What is the probability of getting two heads after flipping a coin twice?
There are four different possibilities when a coin is flipped twice: HH, HT, TH, and TT. Of those, only one of them has two heads, so the probability is ¼.
Example: What is the probability of getting exactly two heads after flipping a coin three times?
There are eight different possibilities when a coin is flipped twice: HHH, HHT, HTH, HTT, THH, THT, TTH, TTT. In three of these possibilities, there are exactly two heads (HHT, HTH, and THH). Thus, the probability is 3/8.
All of the above examples used the same method of calculating the probability: finding the number of desirable outcomes and dividing it by the total number of outcomes. But there is another way.
To return to the coin example, the probability of getting a heads in the first flip is ½. The probability of getting a heads in the second flip is also ½. The probability of both of these events occurring is ½ * ½ = ¼.
Example: What is the probability of getting three heads in three flips?
Since the probability of getting a heads in the first, second, and third flips is ½, the probability of all three happening is ½ * ½ * ½ = 1/8.
Example: What is the probability of getting double sixes when rolling two dice?
Since the probability of getting a six when rolling a single die is 1/6, the probability of that happening twice is 1/6 * 1/6 = 1/36.
Problems for you to try:
1. What is the chance that a person will roll triple threes when she rolls three standard (six-sided) dice?
2. What is the probability of getting a six and heads when you roll one standard six-sided die and flip one coin?
3. What are the chances of getting a combined roll of (that is, when the numbers on the dice add up to) seven when you roll two standard six-sided dice? (Hint: First determine the number of outcomes where the numbers on the two dice add up to seven.)