Counting Principles and Pigeonhole Principle

Sum Rule

If we have $n1$ ways to complete a task, or $n2$ ways, and the task cannot be completed both ways, then there are $n1 + n2$ ways to do the task.
Think of the sum rule in terms of sets.
- Set A with $n1$ elements and set B with $n2$ elements.
- If the sets are disjoint (do not have anything in common), their intersection is an empty set.
If two sets with a finite number of elements are disjoint, the cardinality of their union is the sum of their individual cardinalities: $|A \cup B| = n1 + n2$ .
If sets overlap, the situation becomes a subtraction rule or inclusion-exclusion principle.

Combining Principles

Most problems require the use of both the product rule and the sum rule.

Example: Bit Strings

How many bit strings are there of length six or less, not counting the empty string (length zero)?
We are considering lengths 6, 5, 4, 3, 2, and 1.
Number of bit strings of length six: $2^6$ . Similarly, for length five: $2^5$ , and so on.
Since we consider "or" (length six or less), we add them: $2^6 + 2^5 + 2^4 + 2^3 + 2^2 + 2^1 = 64 + 32 + 16 + 8 + 4 + 2 = 126$ .

Example: Strings with at Least One 'a'

How many strings of four letters of the English alphabet contain at least one letter 'a'? (Case doesn't matter.)
Use the technique of counting the complement of the event.
First, count the total number of all strings of length four: $26^4$ (26 choices for each position).
Second, count the number of strings without the letter 'a': $25^4$ (25 choices for each position).
Subtract the number of strings without 'a' from the total number of strings: $26^4 - 25^4$ . This gives strings that contain at least one A.
Sometimes, it's easier to count the complement (those that do not satisfy the condition) and subtract it from the total.

Divisibility Problem

Problem Statement

How many positive integers less than 1,000 are divisible by 7?

Solution

We want to find the number of multiples of 7 between 1 and 999.
Divide 999 by 7: $999 / 7 \approx 142.714$ .
The result is between 142 and 143.
$142.7$ is not a valid answer because we need a non-negative integer, as we are counting the number of integers.
We use the floor function to find the largest integer less than or equal to $999/7$ , which is 142.
$\lfloor \frac{999}{7} \rfloor = 142$ .

General Rule

To find the number of multiples of $n$ between 1 and $k$ , calculate $\lfloor \frac{k}{n} \rfloor$ .

Example: Divisible by 7 but not by 11

Problem Restatement

Find the number of positive integers less than 1,000 that are divisible by 7 but not by 11.

Logical Form

The problem can be expressed as "divisible by 7 AND NOT divisible by 11".

Venn Diagram Representation

Let A be the set of numbers divisible by 7 and B be the set of numbers divisible by 11.
We want to find the numbers in A but not in B (i.e., $A - B$ ).

Key Insight

First, we know there are 142 numbers divisible by 7.
We want to remove the numbers that are divisible by both 7 and 11.

Divisibility Rule

If a number is divisible by both 7 and 11, then it's divisible by their product, 77 (since 7 and 11 are relatively prime).
Therefore, any number divisible by 7 and 11 can be written as $7 "." 11 "." t = 77t$ , where t is an integer.

Reason

An integer divisible by 7 can be written as $7s$ . If $7s$ is also divisible by 11 (where 7 is not a multiple of 11), then s must be divisible by 11. Thus, $s = 11t$ .

Illustration

Example: $154 = 7 "." 22 = 7 "." (11 "." 2) = 77 "." 2$ .

Number of Multiples of 77

We calculate the number of multiples of 77 less than 1,000:
$\lfloor \frac{999}{77} \rfloor = 12$ .

Final Calculation

There are 142 integers divisible by 7.
There are 12 integers divisible by both 7 and 11 (i.e., divisible by 77).
The number of integers divisible by 7 but not by 11 is: $142 - 12 = 130$ .

Number of Positive Integers Divisible by Both 7 and 11

Based from previous calculations, there are $\lfloor \frac{999}{77} \rfloor = 12$ positive integers divisible by both 7 and 11

Number of Positive Integers Divisible by Either 7 or 11

Problem Statement

How many positive integers less than 1,000 are divisible by either 7 or 11?

Venn Diagram

A represents numbers divisible by 7, and B represents numbers divisible by 11.
We are looking for $|A \cup B|$ , the cardinality of the union of A and B.

Inclusion-Exclusion Principle

The formula for the cardinality of the union of two sets is:
$|A \cup B| = |A| + |B| - |A \cap B|$ .

Known Values

Numbers divisible by 7 ( $|A|$ ): 142
Numbers divisible by both 7 and 11 ( $|A \cap B|$ ): 12
We need to find the number of integers less than 1,000 divisible by 11 ( $|B|$ ).

Calculation of |B|

$|B| = \lfloor \frac{999}{11} \rfloor = 90$ .

Applying the Formula

$|A \cup B| = 142 + 90 - 12 = 220$ .

Illustration for Inclusion-Exclusion

Considering multiples of 2 and 3 less than 20:
- Multiples of 2: 10
- Multiples of 3: 6
- Naively adding gives 16, but this counts multiples of 6 (2 * 3) twice.
Multiples of both 2 and 3:
- By six: 3
Actual number of integers divisible by 2 or 3 should be 10 3 = (16 - 3) - 13

Division Rule

Description

The division rule applies when a task can be completed in $n$ ways, but each way can also be completed in $d$ different ways. You divide to account for over counting.

*Suggestion: Look at EXAMPLE 21 to better understad how this works

Tree diagrams

Description

The diagram is a means of organizing or visualazing the objects you are counting

Example

Bit string count of length four that DO NOT have consecutive ones in it.

Pigeonhole Principle (Section 6.2)

Classical Form

If we have k holes and K + 1 pigeons, then when we place pigeons into holes, we will have at least one hole with at least two pigeons.
If k is a positive integer and k + 1 objects are placed into k boxes, then there is at least one box with at least two objects.

Generalized Pigeonhole Principle

Suppose we have n objects and k categories (boxes).
If n > k, we can guarantee that there is at least one category with at least m objects where $m = \lceil \frac{n}{k} \rceil$ , where the ceiling function gives the smallest integer greater than or equal to the number.

Zoom Session Example

Example: 14 people in a Zoom session (n = 14).
Guarantee: At least two people have birthdays in the same month of the year.
Categories (k): Months of the year (12).

Applying the Principle

$m = \lceil \frac{14}{12} \rceil = \lceil 1.166 \rceil = 2$ .
The pigeonhole principle guarantees at least one month with two people.
It doesn't guarantee which month, but one month has at least 2 people (could be more).

Key Aspects

The principle gives the minimum number in at least one category, not an exact number for specific categories.

Socks Example

Part A

A drawer contains a dozen brown socks and a dozen black socks, all unmatched.
How many socks must he take out to be sure that he has at least two socks of the same color?
Categories (k): Colors (brown and black), so k = 2.
Number of objects from drawer (N): To find
Find : Minimum number. M=2 equal to one
$2 = \lceil \frac{n}{2} \rceil$ .
Then: With the properties of ceiling expressions, that number n will be: 1 < \frac{n}{2} <= 2.
Multiply by two to have the final integer value : - 2 < n <= 4.
So, n is greater than 2 and less than or equal to 4. The possible integer values for n are 3 and 4, so the solution will be 3. So the minimum is 3.

Alternative Problem Statement

What if we had Brown, White, and Black, how many draws would we be taking from the drawer?

So the value will be 4, since M=2 (pair value), and K = 3 draws so: 2 = ceiling(N/3), then (N/3) <=4.

IMPORTANT:

Part B solution will be later

Next steps for study sessions

*B question, Pigeon Hole Properties.