Problem Set 4: Counting
Q1. Sum Rule (Addition Principle)
A restaurant offers 3 types of pizzas and 4 types of sandwiches.
If you want to order either a pizza or a sandwich, how many choices do you have?
Answer: 3+4=7.
Transport Choice
To go to college, Riya can either take a bus (5 different buses) or a train (2 different trains).
In how many ways can she travel?
Answer: 5+2=7
Q2. Product Rule (Multiplication Principle)
(a). A boy has 4 shirts and 3 pants. In how many ways can he choose an outfit (shirt + pant)?
Answer: 4×3=12.
Password Creation
(b) An email account requires a 2-digit number followed by a 1-letter code.
If digits can be chosen in 10 ways (0–9) and letters in 26 ways (A–Z), how many possible
passwords?
Answer: 10×10×26=2600.
Q3. Sports Participation: In a college:
60 students play Cricket (C)
50 play Football (F)
40 play Hockey (H)
20 play both Cricket & Football
15 play both Football & Hockey
10 play both Cricket & Hockey
5 play all three
Students who play at least one sport
¿∨C∨+¿ F∨+¿ H∨−¿
Q4. Imagine a summer camp with 100 children numbered from 1 to 100 (like their ID).
They are grouped by the activity they attend, depending on whether their number is divisible by:
2 → Group A (Games)
3 → Group B (Dance)
4 → Group C (Painting)
5 → Group D (Music)
Now, the camp leader wants to know:
How many children do not belong to any group at all (i.e., their number is not divisible by 2, 3, 4, or
5)?
Alternately this question means, find the number of positive integers 1≤n≤100 and n is not
divisible by 2,3,4 or 5
Step 1: Define the Sets
Let:
- A: Set of integers divisible by 2,
- B: Set of integers divisible by 3,
- C: Set of integers divisible by 4,
We have to find the count of integers not in A ∪ B ∪ C ∪ D.
- D: Set of integers divisible by 5.
Step 2: Calculate Individual Terms
- |A| = 50
- |B| = 33
- |C| = 25
- |D| = 20
Similarly, for pairwise intersections:
- |A ∩ B| = 16
- |A ∩ C| = 25
- |A ∩ D| = 10
- |B ∩ C| = 8
- |B ∩ D| = 6
- |C ∩ D| = 5
For triple intersections:
- |A ∩ B ∩ C| = 8
- |A ∩ B ∩ D| = 3
- |A ∩ C ∩ D| = 5
- |B ∩ C ∩ D| = 1
For the quadruple intersection:
- |A ∩ B ∩ C ∩ D| = 1
Step 3: Apply Inclusion-Exclusion
|A ∪ B ∪ C ∪ D| = |A| + |B| + |C| + |D| - |A ∩ B| - |A ∩ C| - |A ∩ D| - |B ∩ C| - |B ∩ D| - |C ∩ D| + |A
Using the principle of inclusion-exclusion:
∩ B ∩ C| + |A ∩ B ∩ D| + |A ∩ C ∩ D| + |B ∩ C ∩ D| - |A ∩ B ∩ C ∩ D|.
|A ∪ B ∪ C ∪ D| = 50 + 33 + 25 + 20 - 16 - 25 - 10 - 8 - 6 - 5 + 8 + 3 + 5 + 1 - 1 = 74.
Substituting values:
Step 4: Complement
The total number of integers from 1 to 100 is 100. The number of integers not divisible by 2, 3, 4, or
5 is: 100 - 74 = 26.
Conclusion: The number of integers 1 ≤ n ≤ 100 that are not divisible by 2, 3, 4, or 5 is: 26.
Q5. You have 25 apples (n=25) and 6 baskets (k=6).
(25−1)/6+ 1=4 +1=5
At least one basket has 5 apples.
Q6. You have 25 apples that you want to distribute into some baskets such that that at least one
basket must contain 5 apples.
n=25, k=?
( 25−1 ) / k +1 ≥ 5
k ≤ 24 /4=6
If k=6 floor(24/6)+1=5
If k<6 (say 5 baskets), then: floor(24/5)+1=4+1=5
So the maximum number of baskets that still guarantees at least one has 5 apples is 6.
If baskets are fewer than 6, the guarantee is still stronger (more than 5 in some basket).
Q7. If there are 6 baskets, what is the minimum number n of apples you must place (in total) so that
you are guaranteed at least one basket contains 5 apples?
n=?, k=6
( n−1 ) / 6+1 ≥ 5
k ≤ 24 /4=6
This gives us n ≥ 25 i.e. there must be atleast 25 apples so that it is guaranteed at least one basket
contains 5 apples
Q8. How many friends must you guarantee that at least five will have birthday in the same month.
Step 1: Set the Parameters
• k=12: The number of months.
• We want at least five friends in a single month.
Step 2: Apply the Extended Pigeonhole Principle
Let n be the total number of friends. Each month is treated as a "container," and the friends are
"items" distributed among these containers. To guarantee that at least one month has at least 5
friends, we apply the principle:
floor((n - 1) / k) + 1
Step 3: Solve for n
Solving the inequality:
(n - 1) / k) + 1≥5
n≥12×4+1=49
Conclusion: To guarantee that at least five friends have their birthdays in the same month, you need
at least 49 friends.
Q9. A cinema hall has 100 seats.
On the first day, 10 people come to watch the movie.
From the second day onward, the number of people increases by 5 more than the previous day’s
audience (because of word-of-mouth popularity). How many people watch the movie on the nth day?
Step 1: Define the sequence
Let a n = number of people watching on day n.
Day 1: a 1=10
Each day: people = yesterday’s people + 5.
Step 2: Form the recurrence relation
a n=a n−1 +5
Q10. Suppose you open a savings account with:
Initial deposit = ₹1000
Every month you add = ₹500
The bank gives 2% interest per month on the balance.
Question: How much money will you have after n months?
Step 1: Define the sequence
Let a n = money in the account after n months.
Step 2: Form recurrence relation
At the end of each month:
Last month’s money earns interest: a n=a n−1 +0.02 a n−1=1.02⋅ an−1
Plus the new deposit of ₹500
So:
a n=1.02 ⋅an−1 +500
So the recurrence relation here is:
a n=1.02 an−1 +500 , a0=1000
Q11. Handshake Problem: In a party with n people, each person shakes hands with every other
person exactly once. Find the total number of handshakes using a recurrence relation and solve it
using the substitution/iterative method.
Solution
Step 1: Define the sequence
Let H(n) = total number of handshakes among n people.
Step 2: Form the recurrence
If there are only 2 people: H(2)=1.
For n people:
The nth person shakes hands with the other (n−1) people.
Plus the handshakes already done among the first (n-1) people.
So,
H ( n )=H ( n−1 ) + ( n−1 ) , H ( 2 )=1
Step 3: Use substitution/iterative method
Expand step by step:
H ( n )=H ( n−1 ) + ( n−1 )=H ( n−2 )+ ( n−2 ) + ( n−1 )=H ( n−3 ) + ( n−3 ) + ( n−2 ) + ( n−1 )
Continue…
¿ H ( 2 ) +2+3+⋯+ ( n−1 )=1+2+3+⋯+ ( n−1 )
Step 4: Simplify the sum
n (n+1)
The sum 1+2+3+⋯+ ( n−1 ) +n−n= −n
2
So,
n ( n−1 )
H ( n )=
2
The total number of handshakes among n people is:
n ( n−1 )
H ( n )=
2
Proof by induction
Base case: n=2.
2 ( 2−1 )
With 2 people there is exactly 1 handshake. The formula gives =1. So the base case holds.
2
Inductive hypothesis: Assume the formula holds for some integer k≥2; that is
k ( k−1 )
H (k )= .
2
Inductive step: Consider k+1 people. The (k+1)th person must shake hands with each of the other k
people, contributing k new handshakes. The handshakes among the first k people are H(k). So
H ( k +1 )=H ( k ) +k .
Substitute the inductive hypothesis:
k ( k−1 ) k ( k −1 ) +2 k k ( k +1 )
H ( k +1 )= + k= =
2 2 2
Thus the formula holds for k+1.
By induction, the formula
n ( n−1 )
H ( n )=
2
is true for all integers n≥2