Pigeonhole Principle
We are purchasing bottles of soda for a party. The store has 10 brands of soda. How many bottles should we buy to guarantee that we have at least 2 bottles of some soda brand?
Pigeons: n bottles of soda
Holes: 10 soda brands
Min-max number of pigeons in a hole: 2
----
Goal: Find the lowest integer value of n that satisfies the below equation.
ceil(n / 10) = 2
1 < n / 10 <= 2
10 < n <= 20
The minimum valid value for n is 11.
We must buy 11 bottles to guarantee that we have at least 2 bottles of some soda brand.
You have a math textbook, a biology textbook, and a notebook. You want to place these books on your bookshelf. How many different arrangements of the books are possible?
3! = (3)(2)(1) = 6 possible arrangements
BMN
BNM
MBN
MNB
NBM
NMB
How many integers between 0 and 80 (inclusive) are divisible by 2 or 4?
|div by 2| = 41
|div by 4| = 21
|div by 2 AND 4| = 21
|div by 2 OR 4|
= |div by 2| + |div by 4| – |div by 2 AND 4|
= (41) + (21) – (21)
= 41 integers
What is the probability of rolling an even number on a fair 19-sided die (values 1–19)?
9/19
ATM PINs are 4 digits long, with each digit being 0-9.
You are waiting for the person in front of you to finish using the ATM. If you say a random 4-digit number out loud, what is the probability that you've guessed their PIN?
1/1000
In our class of 37 students, what is the minimum number of students guaranteed to have birthdays in the same month?
Pigeons: 37 student birthdays
Holes: 12 months
Min-max number of pigeons in a hole: x
----
Goal: Solve for x in the below equation.
ceil(37 / 12) = x
ceil(3.083...) = x
4 = x
It is guaranteed that at least 4 students will have birthdays in the same month.
You are a barista designing the menu for your coffee shop.
Your shop offers 4 different coffee flavors and 3 different tea blends. Your customers can choose to order their drink with or without milk.
How many different orders are possible for a single drink at your shop?
Customers can order coffee with/without milk, or tea with/without milk.
(coffee options)(milk options) + (tea options)(milk options)
= (4)(2) + (3)(2)
= 8 + 6
= 14 possible orders for a single drink
How many integers between 0 and 120 (inclusive) are divisible by 8 OR 12?
|div by 8| = 16
{0, 8, 16, 24, 32, 40, 48, 56, 64, 72, 80, 88, 96, 104, 112, 120}
|div by 12| = 11
{0, 12, 24, 36, 48, 60, 72, 84, 96, 108, 120}
|div by 8 AND 12| = |div by 24| = 6
{0, 24, 48, 72, 96, 120}
|div by 8 OR 12|
= |div by 8| + |div by 12| – |div by 8 AND 12|
= (16) + (11) – (6)
= 21 integers
You have a red die and a blue die.
Given that you just rolled a 3 on the red die, what is the probability that you roll a 5 on the blue die?
1/6
(These are independent events, so the result of the red die does not change the probability distribution of rolling the blue die!)
A coin toss game with a fair coin costs $2 to play.
If the coin lands on heads, you win $5.
If it lands on tails, you must pay an additional $2.
Is this game worth playing?
Possible outcomes
coin=H
coin=T
Random variable values
Let random variable X represent your winnings from the game.
X(coin=H) = –$2 + $5 = $3
X(coin=T) = –$2 – $2 = –$4
Probabilities
P(coin=H) = 0.5
P(coin=T) = 0.5
Expected value
E[X] = P(coin=H)X(coin=H) + P(coin=T)X(coin=T)
E[X] = (0.5)($3) + (0.5)(–$4)
= ($1.50) + (–$2)
= (–$0.50)
Answer
The expected value of playing the game is negative, so no, the game is not worth playing.
Our class has 37 students. Our classroom is built with several rows, containing various numbers of seats per row:
Row 1: 6 seats
Row 2: 6 seats
Row 3: 6 seats
Row 4: 6 seats
Row 5: 6 seats
Row 6: 6 seats
If every student is in attendance, what is the minimum number of students sitting in a single row?
Pigeons: 37 students
Holes: 6 rows of seats
Min-max number of pigeons in a hole: x
----
Goal: Solve for x in the below equation.
ceil(37 / 6) = x
ceil(6.16...) = x
7 = x
It is guaranteed that at least 7 students will be sitting in a single row.
A password for a website has the following restrictions:
- It must be exactly 6 characters long, using only lowercase letters (a-z) or digits (0-9).
- The first character must be a letter.
- All characters must be different.
How many different passwords can be created?
Note: You do not have to simplify combinations, permutations, exponents, factorials, or fractions.
36 possible characters
Position 1: 26 options
Position 2: 35 options
Position 3: 34 options
Position 4: 33 options
Position 5: 32 options
Position 6: 31 options
Final answer:
(26) * P(35, 5)
How many ways can you arrange 5 people in a line if two specific people must stand next to each other?
2 × 4! = 48
What is the probability of flipping exactly 3 heads in 5 flips of a fair coin?
Example: HHTHT
Size of sample space |S|:
2^5 = 32
Size of event space |E|:
C(5, 3) = 10
Probability |E| / |S|:
C(5, 3) / (2^5) = 10/32 = 5/16
In the casino game "7 Up 7 Down", you roll 2 fair 6-sided dice and sum the numbers.
If the sum is 7, you win $10.
If the sum is above 7, you win $5.
If the sum is below 7, you lose $6.
Each round costs a $3 buy-in before rolling.
Is this game worth playing?
Possible outcomes
sum=7 (6 dice rolls)
sum>7 (15 dice rolls)
sum<7 (15 dice rolls)
Random variable values
Let random variable X represent your winnings from the game.
X(sum=7) = –$3 + $10 = $7
X(sum>7) = –$3 + $5 = $2
X(sum<7) = –$3 – $6 = –$9
Probabilities
P(sum=7) = 6/36
P(sum>7) = 15/36
P(sum<7) = 15/36
Expected value
E[X] = P(sum=7)X(sum=7) + P(sum>7)X(sum>7) + P(sum<7)X(sum<7)
E[X] = (6/36)($7) + (15/36)($2) + (15/36)(–$9)
= ($42/36) + ($30/36) + (–$135/36)
= $(72/36) – $(135/36)
= –$63/36
= –$1.75
Answer
The expected value of playing the game is negative, so no, the game is not worth playing.
Let set A = {1, 2, 3, ..., 58} (all integers from 1 to 58, inclusive).
Your task is to randomly select distinct elements from set A until it is guaranteed that you have 2 elements that sum to 59. What is the minimum number of selections necessary?
Pigeons: n selections
Holes: {1, 58}, {2, 57}, ... {29, 30} -> 29 disjoint pairs that sum to 59
Min-max number of pigeons in a hole: 2
----
Goal: Find the lowest integer value of n that satisfies the below equation.
ceil(n / 29) = 2
1 < n / 29 <= 2
29 < n <= 58
The minimum valid value for n is 30.
We must make 30 random selections to guarantee that we have 2 elements that sum to 59.
A professor needs to select 4 Teaching Assistants (TAs) from a pool of 10 graduate students. However, two of the students, Taylor and Morgan refuse to work together in the teaching team. How many different possible TA teams can the professor form under this constraint?
Total groups : C(10, 4) = 210,
Groups that have Taylor and Morgan in it : C(8,2) = 28,
Groups that follow the constraint = 210 - 28 = 182
In a room of n people, each person shakes hands with everyone else exactly once. No person shakes hands with themselves :) If a total of 45 handshakes take place, how many people are in the room (i.e find n)?
n choose 2 = 45
=> n(n-1) = 90
=> n^2 - n - 90 = 0
=> (n + 9)(n - 10) = 0
=> n = 10
You are the owner of a cafe reviewing your customer data. During your review, you observe the following facts from last year:
- 70% of your customers ordered coffee.
- 40% of your customers ordered a pastry.
- 30% of your customers ordered a coffee and a pastry.
What is the probability that a randomly selected customer from last year ordered neither a coffee nor a pastry?
P(ordered coffee) = 0.7
P(ordered pastry) = 0.4
P(coffee AND pastry) = 0.3
Goal: Find P(NOT (coffee OR pastry)).
----
Use inclusion-exclusion principle:
P(coffee OR pastry)
= P(coffee) + P(pastry) – P(coffee AND pastry)
= (0.7) + (0.4) – (0.3)
= 0.8
----
P(NOT (coffee OR pastry)) = 1 – 0.8 = 0.2
The probability that a randomly selected customer from last year ordered neither a coffee nor a pastry is 20%.
As a small business owner, you sell custom t-shirts online.
Each shirt costs you $8 to make, and you sell it for $15.
There’s a 60% chance a customer buys a shirt with no issue,
a 30% chance they buy and return it (you refund $15),
and a 10% chance they buy and report a defective shirt (you replace it for free, costing $8 more).
Does this business model yield a positive expected profit per shirt?
Possible outcomes
no problem
returned
replaced
Random variable values
Let random variable X represent your profit.
X(no problem) = –$8 + $15 = $7
X(returned) = –$8 + $15 – $15 = –$8
X(replaced) = –$8 + $15 – $8 = –$1
Probabilities
P(no problem) = 0.6
P(returned) = 0.3
P(replaced) = 0.1
Expected value
E[X] = P(no problem)X(no problem) + P(returned)X(returned) + P(replaced)X(replaced)
E[X] = (0.6)($7) + (0.3)(–$8) + (0.1)(–$1)
= ($4.20) + (–$2.40) + (–$0.10)
= $1.70
Answer
Yes, this business model is profitable!
Let set A = {1, 2, 3, ..., 15} (all integers from 1 to 15, inclusive).
Your task is to randomly select distinct elements from set A until it is guaranteed that you have 2 elements that sum to 16. What is the minimum number of selections necessary?
Setting up the problem: Selecting 8 would be a "wasted" selection, since 8 + 8 is impossible. We can ignore 8 in our calculation, then add 1 to the final answer to account for the possibility that one of our selected integers is 8.
Pigeons: n selections
Holes: {1, 15}, {2, 14}, ... {7, 9} -> 7 disjoint pairs that sum to 16
Min-max number of pigeons in a hole: 2
----
Goal: Find the lowest integer value of n that satisfies the below equation. The final answer will be n + 1.
ceil(n / 7) = 2
1 < n / 7 <= 2
7 < n <= 14
The minimum valid value for n is 8, so n + 1 = 9.
We must make 9 random selections to guarantee that we have 2 elements that sum to 16.
A small class has 7 students.
The professor wants to split the class into 3 different groups of size 2, 2, and 3 for a project.
How many different ways can the class be divided into groups of these sizes?
Note: You do not have to simplify combinations, permutations, exponents, factorials, or fractions.
Possible answers:
- [C(7, 2) * C(5, 2) * C(3, 3)] / 2
- [C(7, 2) * C(5, 3) * C(2, 2)] / 2
- [C(7, 3) * C(4, 2) * C(2, 2)] / 2
Why divided by 2?
Example: Imagine we use this method to count groupings of students from {a, b, c, d, e, f, g}:
{{ab} {cd} {efg}}
...
{{cd} {ab} {efg}} -- REDUNDANT
...
If the teams had names (e.g. Team X (size 2), Team Y (size 2), Team Z (size 3)), then we would be counting ordered triples of subsets, and ( {ab}, {cd}, {efg} ) would be different from ( {cd}, {ab}, {efg} ).
However, we are not worried about identifying or ordering the teams in any way, so we want to count sets of subsets. The two teams of size 2 are not unique in any way, so we need to make sure that we do not double-count { {ab}, {cd}, {efg} } and { {cd}, {ab}, {efg} }, since these are the same set.
How many ways can 120 unique books be arranged on 10 identical bookshelves if each bookshelf must contain exactly the same number of books?
Note: You do not have to simplify combinations, permutations, exponents, factorials, or fractions.
C(120,12) × C(108,12) × C(96,12) × ... × C(24,12) × C(12,12) ÷ 10!
In a group of 4 friends, each person independently chooses their favorite ice cream flavor from vanilla, chocolate, strawberry, or mint with equal probability. What is the probability that at least two people choose the same flavor?
Each person has 4 choices of flavors so there at 4^4 = 256 ways that they can pick any flavor.
The number of ways each of them pick a different flavor is 4! = 24.
Therefore the total ways in which at least two people pick the same flavor is 256 -24 = 232 and the probability of that happening is 232/256 = 0.906
There are 37 people in this class. What is the probability that at least two people in the class share a birthday?
Use WolframAlpha and round your answer to 4 significant figures.
Note: Ignore leap years so that there are 365 days in a year, and assume that every day of the year has an equal (i.e 1/365) chance of being someone's birthday.
P(at least two people share a birthday) = 1 – P(all different birthdays)
----
To find P(all different birthdays):
Size of sample space |S|: Total possible "birthday lists"
If we list all 37 students and their birthdays, there are 365^37 possible lists.
Size of event space |E|: "Birthday lists" with all different birthdays:
P(365, 37)
Probability:
P(all different birthdays) = P(365, 37) / (365^37)
P(at least two people share a birthday) = 1 – [P(365, 37) / (365^37)]
≈ 0.8487, or 84.87%