5: Counting and Probability
BFL Competition Math 2022
Review - Principles of Counting
Fundamental Principle of Counting: If there are A ways to do one thing and B ways to do another thing, and they don’t affect each other, then there are A*B ways to do both things.
Remember to correct for overcounting by “undoing” the way we overcounted - this is usually done by dividing if we counted everything more than once
A permutation of n objects is a way to arrange them in order, and the number of permutations is typically given by n! (unless you overcounted)
The number of ways to choose k objects from n objects is n!/k!(n-k)!
Make sure to understand why each of these are true
Examples
Richard, Michael, Derek, and Anya all want to hang out tomorrow, but all of them are undecided as to whether to go. How many possible groups can there be who go? (It can be no people, just one person, or any number of them)
Consider the 4x3 grid to the right. How many total rectangles are there? How many paths are there to walk from the bottom left corner to the top right corner if you can only walk up and to the right along the lines of the grid?
How many ways are there to distribute 8 candy bars among 3 students if each student must get at least one?
| | | |
| | | |
| | | |
Counting Strategies
Problem (1983 AIME)
The numbers 1447, 1005, and 1231 have something in common: each is a four-digit number beginning with 1 that has exactly two identical digits. How many such numbers are there?
Combinatorial Identities/Arguments
Pascal’s Identity:
Vandermonde’s Identity:
These are pretty straightforward to prove algebraically, but let’s see how we can interpret them as combinatorial situations!
Example (2020 AIME I)
A club consisting of 11 men and 12 women needs to choose a committee from among its members so that the number of women on the committee is one more than the number of men on the committee. The committee could have as few as 1 member or as many as 23 members. Let N be the number of such committees that can be formed. Find the sum of the prime numbers that divide N.
Problem (classic)
If I roll a die and you roll a die, what is the probability that I roll a higher number than you?
Example (2022 Spring BMH)
Fred and Frank are playing a game where they alternate turns. Fred begins with the number 60. Then, each player names a positive integer that divides the number given by the other player and is less than the given number. The game ends when a player says the number 1. A possible sequence is 60, 20, 5, 1. How many different sequences are possible?
More Advanced Strategies
Bijections: counting the same thing in more than one way - we just did this before! This is helpful because if we show that we can count something in an easier way then we can just do that
Invariants: focusing on something that remains the same - for example if we have to tile a floor with 2x1 dominos then the floor has to have an even number of tiles
More Advanced Strategies
Recursion: we can solve a problem by plugging in smaller numbers, and then using them to build up to what we want - for instance the number of ways to climb a total of n stairs if you can climb 1 or 2 stairs at a time is given by the nth Fibonacci number.
Generating Functions: turning counting problems into algebra problems - for example the generating function for rolling dice is x1 + x2 + x3 + x4 + x5 + x6. Rolling two dice is like doing (x1 + x2 + x3 + x4 + x5 + x6)2, and the number of ways to roll a 7 would be the coefficient of x7.
Probability Fundamentals
Keep in mind that probability is defined as the amount of desired outcomes compared to the total possible outcomes, and the probability of an event A is written P(A).
If two events A and B don’t affect each other, then the probability of both A and B is P(A)*P(B), due to the fundamental principle of counting.
If the result of event A affects event B, then we need to consider the effect it has.
Again, make sure to understand why these make sense!
Geometric Probability
If there is a finite number of outcomes, we can just handle probability using counting.
But if we have to work with something like a line or a plane, there’s an infinite amount of points, making it impossible to count.
In this situation, we might think about using geometric quantities like lengths, areas, angles, or volumes to find probability.
Problem (classic)
Derek and I want to meet outside my house at some point between 11:00 and 12:00. I will choose a random time to leave, but since it’s hot outside I’ll only wait for him for 10 minutes, after which I will just leave, and he will do the same. What is the probability that we will successfully meet each other?
Conditional Probability
(Monty Hall Problem) There are 3 boxes, one of which contains $1000. You can randomly guess one of them, and you get the money if you guess the right box. After you make your choice, I will tell you one of the boxes that doesn’t contain the money. Then, you have the option to pick again. Should you choose the other box?
P(A given B) = P(A and B)/P(B)
(AoPS) Three coins are flipped. If at least one of them comes up heads, then what is the probability that they all come up heads?
Probability with States
Some situations will involve frogs jumping around randomly, possibly making an infinite sequence of moves that is again impossible to count.
To deal with this, we can draw a state diagram to understand how the frog’s situation changes depending on what moves it makes.
The Frog Problem (2020 AMC 10A)
A frog sitting at the point (1, 2) begins a sequence of jumps, where each jump is parallel to one of the coordinate axes and has length 1, and the direction of each jump (up, down, right, or left) is chosen independently at random. The sequence ends when the frog reaches a side of the square with vertices (0, 0), (0, 4), (4, 4), and (4, 0). What is the probability that the sequence of jumps ends on a vertical side of the square?
Final Tips
Being good at combinatorics comes with experience, and it takes a lot of practice solving problems to develop the intuition.
Think about approaching the problem from the perspective of something you want to find
Recap
Counting strategies - casework, complementary, construction
Combinatorial arguments - come up with a combinatorial interpretation to justify a relationship
A lot of the time, probability can be approached with a counting thought process
If there are infinite cases to consider, other strategies exist like geometric probability and probability with states.
Thank you for coming!
Slides and problems will be posted in the next few days, reach out to dengr557@gmail.com with any questions