Solved Exercises on Counting with Restrictions

Master counting with restrictions: inclusion-exclusion, complementary counting, and advanced applications through these 5 detailed exercises.

Solution: Exercises 1 to 3
1 Complementary Counting
Exercise 1
How many 4-digit numbers contain at least one 7?
Definition:

Complementary Counting: Instead of counting what we want, count what we don't want and subtract from the total. Often easier when the restriction is "at least one" or "not all."

Complementary counting method:
  1. Count the total possible outcomes
  2. Count the outcomes that violate the restriction
  3. Subtract: Desired outcomes = Total - Violating outcomes
Total 4-digit numbers
9000
No 7s allowed
5103
At least one 7
9000-5103
Result
3897
Step 1: Count total 4-digit numbers

Range: 1000 to 9999. Total = 9999 - 1000 + 1 = 9000.

Step 2: Count 4-digit numbers with NO 7s

Thousands digit: 1,2,3,4,5,6,8,9 (8 choices, can't be 0 or 7). Other digits: 0,1,2,3,4,5,6,8,9 (9 choices each). Total = 8×9×9×9 = 5832.

Step 3: Apply complementary counting

Numbers with at least one 7 = Total - Numbers with no 7s = 9000 - 5832 = 3168.

3168 four-digit numbers contain at least one 7
Final answer:

There are 3,168 four-digit numbers that contain at least one 7.

Applied rules:

• Complementary counting: Count what we don't want, subtract from total

• Restriction handling: "At least one" often implies complementary approach

• Fundamental counting principle: Multiply independent choices

2 Inclusion-Exclusion Principle
Exercise 2
Among 100 people, 60 like coffee, 50 like tea, and 30 like both. How many like neither?
Definition:

Inclusion-Exclusion Principle: For two sets A and B: |A ∪ B| = |A| + |B| - |A ∩ B|. This prevents double-counting elements in both sets.

Coffee lovers
|A|=60
Tea lovers
|B|=50
Both lovers
|A∩B|=30
Either lover
|A∪B|=80
Step 1: Apply inclusion-exclusion principle

|A ∪ B| = |A| + |B| - |A ∩ B| = 60 + 50 - 30 = 80.

Step 2: Find those who like neither

Total people - People who like at least one = 100 - 80 = 20.

Step 3: Verify with Venn diagram concept

Coffee only: 60-30=30, Tea only: 50-30=20, Both: 30, Neither: 100-(30+20+30)=20.

20 people like neither coffee nor tea
Final answer:

There are 20 people who like neither coffee nor tea.

Applied rules:

• Inclusion-exclusion: |A ∪ B| = |A| + |B| - |A ∩ B|

• Overcounting prevention: Subtract intersection to avoid double counting

• Complementary principle: Total - Desired = Undesired

3 Arrangement with Adjacency Restriction
Exercise 3
In how many ways can 5 people be seated in a row if two particular people must sit together?
Definition:

Treating as a Unit: When objects must be adjacent, treat them as a single unit. Count arrangements of the unit with other objects, then arrange objects within the unit.

Treat couple as unit
4 units
Arrange units
4!=24
Arrange inside unit
2!=2
Total
24×2=48
Step 1: Treat the two people as a single unit

Instead of 5 people, we now have 4 units: the couple (as one unit) + 3 other individuals.

Step 2: Arrange the 4 units

The 4 units can be arranged in 4! = 24 ways.

Step 3: Arrange the two people within their unit

The two people in the unit can be arranged in 2! = 2 ways (AB or BA).

Step 4: Apply fundamental counting principle

Total arrangements = 24 × 2 = 48.

48 ways to seat 5 people with 2 together
Final answer:

There are 48 ways to seat 5 people in a row with 2 particular people sitting together.

Applied rules:

• Treat as unit: Combine restricted objects into a single entity

• Multiplication principle: External arrangements × internal arrangements

• Adjacency restriction: Use grouping method for adjacent requirements

Rules and methods, laws,...
\(|A \cup B| = |A| + |B| - |A \cap B|\)
Inclusion-Exclusion Principle
Complementary Counting
Desired = Total - Undesired
Count what we don't want
Inclusion-Exclusion
|A∪B| = |A| + |B| - |A∩B|
Avoid double counting
Three Sets
|A∪B∪C| = |A|+|B|+|C| - |A∩B|-|A∩C|-|B∩C| + |A∩B∩C|
Complex overlaps
Unit Treatment
(n-1)! × k!
k objects together in n
Key definitions:

Counting with Restrictions: Methods for counting arrangements or selections when certain conditions must be met.

Complementary Counting: Counting desired outcomes by subtracting unwanted outcomes from total outcomes.

Inclusion-Exclusion Principle: A method to count elements in the union of sets by adding individual counts and subtracting overlaps.

Treating as Unit: Grouping objects that must satisfy adjacency conditions into a single entity.

Complete methodology:
  1. Identify the restriction: Determine what condition must be satisfied
  2. Choose appropriate method: Complementary, inclusion-exclusion, unit treatment, etc.
  3. Break down the problem: Separate the counting into manageable parts
  4. Apply the method: Execute the chosen strategy systematically
  5. Combine results: Use addition, subtraction, or multiplication as needed
  6. Verify: Check if the answer makes logical sense
Tip 1: For "at least one" problems, use complementary counting.
Tip 2: When objects must be adjacent, treat them as a single unit.
Tip 3: For overlapping categories, use inclusion-exclusion to avoid double counting.
Tip 4: Draw diagrams or use visual aids for complex restrictions.
Common errors: Forgetting to account for overlaps, misapplying inclusion-exclusion, not treating units correctly, miscounting totals.
Key insight: Restrictions often make problems easier by reducing the sample space to consider.
Essential formulas:

• Complementary: Desired = Total - Undesired

• Inclusion-exclusion (2 sets): |A ∪ B| = |A| + |B| - |A ∩ B|

• Inclusion-exclusion (3 sets): |A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|

• Adjacent objects: (n-1)! × k! for k objects together in n positions

Solution: Exercises 4 to 5
4 Multiple Restrictions
Exercise 4
How many 5-digit numbers can be formed using digits 1,2,3,4,5 if the first digit must be even and the last digit must be odd?
Definition:

Multiple Simultaneous Restrictions: When several conditions must all be satisfied at once, count possibilities for each position while respecting all constraints.

First digit (even)
2 choices
Last digit (odd)
3 choices
Middle digits
3! arrangements
Total
2×3×6=36
Step 1: Identify available digits

Given digits: {1, 2, 3, 4, 5}. Even digits: {2, 4}. Odd digits: {1, 3, 5}.

Step 2: Apply first restriction

First digit must be even: 2 choices (2 or 4).

Step 3: Apply second restriction

Last digit must be odd: 3 choices (1, 3, or 5).

Step 4: Arrange remaining digits

After choosing first and last digits, 3 digits remain for the middle 3 positions: 3! = 6 arrangements.

Step 5: Apply fundamental counting principle

Total = 2 × 3 × 6 = 36.

36 five-digit numbers satisfy the conditions
Final answer:

There are 36 five-digit numbers that can be formed with the given restrictions.

Applied rules:

• Simultaneous restrictions: Apply all constraints together

• Sequential counting: Address each position with its constraints

• Without replacement: Each digit used only once

5 Three-Set Inclusion-Exclusion
Exercise 5
In a survey of 100 students: 60 study math, 50 study physics, 40 study chemistry, 30 study math and physics, 25 study math and chemistry, 20 study physics and chemistry, and 15 study all three. How many study none?
Definition:

Three-Set Inclusion-Exclusion: |A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|. This accounts for all possible overlaps between three sets.

Individual sets
60+50+40=150
Pairwise intersections
30+25+20=75
Triple intersection
15
Total studying
150-75+15=90
Step 1: Apply three-set inclusion-exclusion

|M ∪ P ∪ C| = |M| + |P| + |C| - |M ∩ P| - |M ∩ C| - |P ∩ C| + |M ∩ P ∩ C|

= 60 + 50 + 40 - 30 - 25 - 20 + 15 = 150 - 75 + 15 = 90

Step 2: Find students studying none

Total students - Students studying at least one subject = 100 - 90 = 10.

Step 3: Verify with principle

We added individual sets (overcounting), subtracted pairwise intersections (correcting overcount), added back triple intersection (correcting undercount).

10 students study none of the subjects
Final answer:

There are 10 students who study none of the three subjects.

Applied rules:

• Three-set inclusion-exclusion: |A∪B∪C| = |A|+|B|+|C| - |A∩B|-|A∩C|-|B∩C| + |A∩B∩C|

• Systematic correction: Add individual counts, subtract pairwise overlaps, add back triple overlap

• Complementary counting: Total minus desired gives undesired

Comprehensive Summary: Counting with Restrictions
\(|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|\)
Three-Set Inclusion-Exclusion
Key definitions:

Counting with Restrictions: Methods for counting arrangements or selections when certain conditions must be satisfied.

Complementary Counting: Counting desired outcomes by subtracting unwanted outcomes from total outcomes.

Inclusion-Exclusion Principle: A method to count elements in the union of sets by adding individual counts and subtracting overlaps.

Treating as Unit: Grouping objects that must satisfy adjacency conditions into a single entity.

Simultaneous Restrictions: Multiple conditions that must all be satisfied at the same time.

Complete methodology:
  1. Problem analysis: Identify all restrictions and requirements
  2. Method selection: Choose appropriate technique (complementary, inclusion-exclusion, etc.)
  3. Constraint breakdown: Handle each restriction systematically
  4. Counting execution: Apply the chosen method step-by-step
  5. Result combination: Use arithmetic operations to find the final answer
  6. Verification: Check if the answer is reasonable and complete
Tip 1: For "at least one" or "not all" problems, try complementary counting first.
Tip 2: When objects must be adjacent, treat them as a single unit initially.
Tip 3: For overlapping categories, use inclusion-exclusion to avoid double counting.
Tip 4: For multiple restrictions, address them in order of complexity.
Tip 5: Always verify your answer makes logical sense in the context.

Common errors: Forgetting to account for overlaps, misapplying inclusion-exclusion, not treating units correctly, failing to consider all restrictions simultaneously.
Memorization aid: "Complement: Total - Bad = Good", "Inclusion-Exclusion: Add, subtract, add back".
Advanced insight: Restrictions can sometimes simplify problems by reducing the sample space to consider.
Essential formulas and principles:

• Complementary counting: Desired outcomes = Total outcomes - Undesired outcomes

• Two-set inclusion-exclusion: |A ∪ B| = |A| + |B| - |A ∩ B|

• Three-set inclusion-exclusion: |A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|

• Adjacent arrangements: (n-1)! × k! for k objects together in n positions

• n-set inclusion-exclusion: Alternating sum of all possible intersections

Example progression (Simple to Complex):

• Simple: Single restriction (at least one occurrence)

• Intermediate: Two overlapping categories (inclusion-exclusion)

• Advanced: Adjacency requirements (unit treatment)

• Complex: Multiple simultaneous restrictions

• Advanced: Three or more overlapping sets

Key takeaways for memorization:

• "At least one" often suggests complementary counting

• Overlapping categories require inclusion-exclusion to avoid double counting

• Adjacent requirements suggest treating objects as a single unit

• Multiple restrictions must be satisfied simultaneously

• Always verify that your answer respects all given constraints

Questions & Answers

Question: How do I know when to use complementary counting vs direct counting?

Answer: Use complementary counting when:

  • The condition is "at least one," "not all," or "some but not all"
  • Counting the undesired outcomes is simpler than counting desired ones
  • You have many different ways to satisfy the condition

Use direct counting when the condition is straightforward to enumerate. For example, "numbers with at least one 7" is easier via complementary counting (total - numbers with no 7s) than direct counting.

Question: Why do we subtract the intersection in inclusion-exclusion? Isn't that removing too much?

Answer: When you add |A| + |B|, you count elements in A ∩ B twice - once in |A| and once in |B|. Since elements in the intersection should only be counted once in |A ∪ B|, you subtract |A ∩ B| to correct for this double counting.

Think of it as: "I counted them twice, so I need to remove one count to get the correct total."

Question: Can I use inclusion-exclusion with more than three sets? How does the pattern continue?

Answer: Yes! The inclusion-exclusion pattern continues with alternating signs:

  • Start with sums of individual sets
  • Subtract sums of all pairwise intersections
  • Add sums of all three-way intersections
  • Subtract sums of all four-way intersections
  • Continue alternating until you reach the n-way intersection

For four sets: |A∪B∪C∪D| = |A|+|B|+|C|+|D| - |A∩B|-|A∩C|-|A∩D|-|B∩C|-|B∩D|-|C∩D| + |A∩B∩C|+|A∩B∩D|+|A∩C∩D|+|B∩C∩D| - |A∩B∩C∩D|