Complete cases and counterexamples
Đã giới thiệu| English | Ý nghĩa |
|---|---|
| proof by exhaustion/pruːf baɪ eɡˈzɔːstʃn/ | Chứng minh bằng liệt kê |
When do three cases cover every integer?
- Testing a thousand integers may miss the next counterexample. A complete list of possible remainders can instead settle every integer.
- This lesson studies proof by exhaustion 穷举证明: A proof that checks every possibility in a finite, complete set of cases.
The method
- Write n=3k, 3k+1 or 3k+2 for integer k.
- These are all possible remainders on division by 3, including negative integers.
- Evaluate the expression in each case.
- One counterexample disproves a universal claim; examples supporting a claim do not prove it.
Why does checking n=0,1,2 not prove a claim about every integer’s remainder on division by 3?
Độ khó 1/5 · 100 xu + một phần thưởng nhỏ cho lần hoàn thành đầu tiên trong ngày
The three remainder classes with a general k cover every integer, positive or negative, in one argument each. Checking sample values verifies only those values.
A worked case
For n=3k, n²=9k² is divisible by 3. For n=3k+1, n²=3(3k²+2k)+1. For n=3k+2, n²=3(3k²+4k+1)+1. Thus an integer square has remainder 0 or 1, never 2. The claim that n²+n+41 is always prime fails at n=41: its value is 1763=41×43.
Complete cases and counterexamples
Write n=3k, 3k+1 or 3k+2 for integer k
Classify each argument and explain the condition that makes it valid or incomplete.
How many remainder cases are needed for division by 3?
Độ khó 2/5 · 140 xu + một phần thưởng nhỏ cho lần hoàn thành đầu tiên trong ngày
The possible remainders are 0,1,2, giving three cases.
Where it goes wrong
- A finite sample is not exhaustion unless it contains every possible case.
- Checking n=0,1,2 alone is not enough: the expressions involving arbitrary integer k justify all integers.
Not true: If a claim works for the first hundred integers, it has been proved for all integers. Checking cases proves a claim only when every case is checked; integers go on forever.
What remainder does 8² have on division by 3?
Độ khó 2/5 · 140 xu + một phần thưởng nhỏ cho lần hoàn thành đầu tiên trong ngày
64=3×21+1.
If a claim works for the first hundred integers, it has been proved for all integers.
Độ khó 1/5 · 100 xu + một phần thưởng nhỏ cho lần hoàn thành đầu tiên trong ngày
Checking cases proves a claim only when every case is checked; integers go on forever.
Applying it
- Choose a complete case split, such as parity or remainders.
- State why no case is missing.
- For a false universal claim, give a valid input and verify the failure directly.
Evaluate n²+n+41 at n=41.
Độ khó 2/5 · 140 xu + một phần thưởng nhỏ cho lần hoàn thành đầu tiên trong ngày
41²+41+41=1763=41×43.
Match each proof outcome to what establishes it.
Độ khó 2/5 · 140 xu + một phần thưởng nhỏ cho lần hoàn thành đầu tiên trong ngày
A finite complete case list proves by checking each case; a finite INCOMPLETE sample is just evidence.
In your course
- AQA A-level Mathematics (7357), specification section A.
- Every paper allows a calculator, but method marks still need the expression or equation written before its value.
- Proof by exhaustion: A proof that checks every possibility in a finite, complete set of cases.
- Write n=3k, 3k+1 or 3k+2 for integer k.
- Watch for: A finite sample is not exhaustion unless it contains every possible case.