Inaugurated by IN-SPACe
ISRO Registered Space Tutor
S8-SA2-0149
What is a Proof by Exhaustion?
Grade Level:
Class 8
AI/ML, Data Science, Research, Journalism, Law, any domain requiring critical thinking
Definition
What is it?
A Proof by Exhaustion is a way to prove a statement is true by checking every single possible case. It's like checking every item on a small list to make sure they all follow a rule. This method works only when there is a limited, countable number of cases to check.
Simple Example
Quick Example
Imagine you have a small basket with only 5 fruits: 2 apples, 2 bananas, and 1 orange. You want to prove that 'every fruit in the basket is either red or yellow'. You would pick each fruit, one by one, and check its colour. If all apples are red, all bananas are yellow, and the orange is orange (not red or yellow), then your statement would be false because the orange doesn't fit the rule. If all were red or yellow, the statement would be proven true.
Worked Example
Step-by-Step
Let's prove that 'the square of any single-digit odd number is also an odd number'.
Step 1: Identify all single-digit odd numbers. These are 1, 3, 5, 7, 9.
---Step 2: Check the first case (number 1). 1 * 1 = 1. Is 1 an odd number? Yes.
---Step 3: Check the second case (number 3). 3 * 3 = 9. Is 9 an odd number? Yes.
---Step 4: Check the third case (number 5). 5 * 5 = 25. Is 25 an odd number? Yes.
---Step 5: Check the fourth case (number 7). 7 * 7 = 49. Is 49 an odd number? Yes.
---Step 6: Check the fifth case (number 9). 9 * 9 = 81. Is 81 an odd number? Yes.
---Step 7: Since we checked every single-digit odd number and found that its square is indeed an odd number, the statement is proven true by exhaustion.
Why It Matters
This method helps build strong logical thinking, useful in many fields. Data scientists use it to check all possible outcomes in small datasets, and lawyers might use it to review all specific pieces of evidence in a case. It teaches you to be thorough and leave no stone unturned, which is great for research and problem-solving.
Common Mistakes
MISTAKE: Trying to use proof by exhaustion for problems with infinite or very large numbers of cases. | CORRECTION: Only use this method when the number of cases is small and manageable enough to check individually.
MISTAKE: Missing one or more cases while checking. | CORRECTION: Always make a complete list of ALL possible cases first before starting to check them.
MISTAKE: Not clearly stating the rule or statement you are trying to prove. | CORRECTION: Before you start, write down exactly what you want to prove, so you know what you're checking for in each case.
Practice Questions
Try It Yourself
QUESTION: Prove by exhaustion that 'every month in a standard calendar year has at least 28 days'. | ANSWER: There are 12 months. All 12 months (Jan, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Dec) have at least 28 days. (Feb has 28 or 29, others have 30 or 31). So, the statement is true.
QUESTION: A small shop sells only 4 types of snacks: Samosa (Rs. 15), Vada Pav (Rs. 20), Pakora (Rs. 25), and Jalebi (Rs. 10). Prove that 'every snack costs less than Rs. 30'. | ANSWER: Samosa (15 < 30), Vada Pav (20 < 30), Pakora (25 < 30), Jalebi (10 < 30). All cases are true, so the statement is proven.
QUESTION: Consider all two-digit numbers where both digits are the same (e.g., 11, 22, ...). Prove that 'the sum of the digits of any such number is always an even number'. | ANSWER: The numbers are 11, 22, 33, 44, 55, 66, 77, 88, 99. Sum of digits: 1+1=2 (even), 2+2=4 (even), 3+3=6 (even), 4+4=8 (even), 5+5=10 (even), 6+6=12 (even), 7+7=14 (even), 8+8=16 (even), 9+9=18 (even). All sums are even, so the statement is proven.
MCQ
Quick Quiz
Which of the following problems is best suited for a Proof by Exhaustion?
Proving that 'the sum of two even numbers is always even'.
Proving that 'there are infinitely many prime numbers'.
Proving that 'every student in a class of 25 scored above 50% on a test'.
Proving that 'x + y = y + x for all real numbers x and y'.
The Correct Answer Is:
C
Option C has a finite and manageable number of cases (25 students) that can be individually checked. Options A, B, and D involve infinite numbers or general mathematical properties that cannot be checked case-by-case.
Real World Connection
In the Real World
Imagine you're developing an app for a small school. Before launching, you might use proof by exhaustion to check if 'every button on the app's main screen works correctly on all 3 supported phone models'. You'd test each button on each phone model to ensure no bugs. This systematic testing is crucial in software development, similar to how quality control teams at companies like Flipkart or Zomato check every batch of products or every delivery route in a small area.
Key Vocabulary
Key Terms
CASE: A specific situation or instance that needs to be checked | PROVE: To show that something is true using logic and evidence | FINITE: Having a limited or countable number of items | EXHAUSTION: The act of completely checking every single possibility without missing any
What's Next
What to Learn Next
Once you understand Proof by Exhaustion, you can explore other proof techniques like 'Proof by Contradiction' or 'Proof by Induction'. These methods help you prove statements even when there are too many cases to check individually, expanding your problem-solving toolkit!
