Basic Counting
Understanding the fundamentals of counting without actually counting
🤔 Why Counting?
Counting is a basic task in mathematics, but our objective is more sophisticated:
To determine how many objects there are without actually counting them one by one
Applications of Counting:
- ▸ Algorithm Analysis: Determining the number of steps an algorithm takes
- ▸ Probability: Estimating the likelihood of events (our focus in this course)
- ▸ Proofs: Techniques like the Pigeonhole Principle
📜 Brief History of Counting
The Ishango Bone
- • Possibly the oldest mathematical artifact still in existence
- • Dates back to the Upper Paleolithic period, approximately 20,000 years old
- • 10 cm long bone with a series of notches believed to be used for counting
🦴
Ishango Bone
~20,000
BCE
📱
Sumerian
Tablet
~2600 BCE
Sumerian Multiplication Table
- • Created around 2600 BCE in the Sumerian city of Shuruppak
- • Contains three columns with dots representing distances from 6 meters to 3 kilometers
- • The third column shows the product of the first two columns
- • Sumer was a region of ancient Mesopotamia in the Middle East
🔢 How Do We Count?
Question 1:
How many numbers are there between 21 and 31?
✓ Correct!
The numbers between 21 and 31 are: 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31.
That's 11 numbers in total.
Question 2 (General Case):
How many numbers are there between \(m\) and \(n\), where \(m < n\)?
Answer: \(n - m + 1\)
💡 Explanation:
When counting from \(m\) to \(n\) inclusive, we need to add 1 because we're including both endpoints.
For example: From 21 to 31 → \(31 - 21 + 1 = 11\) ✓
Practice Problem:
How many numbers between 33 and 67 are divisible by 4?
Step-by-step Solution:
- First, find the smallest number ≥ 33 that's divisible by 4: 36
- Next, find the largest number ≤ 67 that's divisible by 4: 64
- The numbers divisible by 4 form an arithmetic sequence: 36, 40, 44, ..., 64
- Number of terms = \(\frac{64 - 36}{4} + 1 = \frac{28}{4} + 1 = 7 + 1 = 8\)
Answer: 8 numbers
➕ The Sum Rule
Sum Rule
If there are \(m\) objects of the first type and \(n\) objects of the second type, then there are \(m + n\) objects of one of the two types.
Example: Pizza or Burger Places
🍕
7
Pizza places
🍔
5
Burger places
Total = 7 + 5 = 12 places
Example: Chess Piece Movement
A piece starts in the bottom left corner of a chessboard. In one move it can move one step to the right or one step up.
How many moves are needed to reach column 4, row 6?
To reach column 4, we need 3 moves to the right
To reach row 6, we need 5 moves up
Total moves = 3 + 5 = 8 moves
⚠️ Caution with Sum Rule!
Question:
Count all integers from 1 to 10 that are divisible by 2 or by 3.
❌ Incorrect Approach:
- • Numbers divisible by 2: 2, 4, 6, 8, 10 → 5 numbers
- • Numbers divisible by 3: 3, 6, 9 → 3 numbers
- • By sum rule: 5 + 3 = 8 ❌
✓ Correct Approach:
Let's count directly: 2, 3, 4, 6, 8, 9, 10
That's 7 numbers, not 8!
💡 Key Insight:
The number 6 was counted twice (it's divisible by both 2 and 3)!
In the sum rule, no object should belong to both types!