Prove a Minimum with Lower Bounds and Constructions
第11讲 逻辑推理（2）· 第3课
A minimum proof has two jobs: show that a smaller answer cannot work, and then build a plan that reaches your claimed number.
Fewer cannot work. This many can work. Therefore it is the minimum.
A minimum proof needs two different jobs
Finding a number that works is not enough. We must also prove that every smaller number fails.
Prove that every solution needs at least this many.
Show a real plan that uses exactly this many.
The lower bound and construction meet at the same number.
proved impossible
so it is achievable
Collect ten separate news items
First prove how many letters are needed before anyone can know all ten pieces of news.
Complete practice problem
Ten friends live far apart. Each friend initially knows one different piece of good news. They may communicate only by sending letters. A letter may contain everything its sender currently knows, but it has only one recipient. It transfers information only to that recipient: a reply is another letter. Friends remember all news they receive. Count letters, not days of travel. What is the minimum number of letters needed so that all ten friends know all ten pieces of news?
After one person knows everything, spread it to nine others
The first fully informed person does not finish the problem. Everyone else must also receive the complete collection.
The first complete knower
At the instant the first person learns all ten items, that receiving person is the first fully informed person. The other nine are not yet all informed.
One recipient per letter
One complete letter can make at most one additional person fully informed. Therefore nine more people require at least nine more letters.
Construct a plan using exactly 18 letters
The lower bound says at least 18. Now build a plan that actually reaches 18.
Generalize the letter proof to n friends
The same lower-bound and construction argument works for any positive whole number n of friends, each starting with one different news item and using the same one-recipient rule.
Why the formula works
9
letters
9
letters
One chosen collector does not send to or receive from themself. That is why each phase uses n − 1, not n.
Turn correct-answer totals into error totals
The second original investigation asks how many questions are guaranteed to be correct for all four students. Here an “error” is one student’s answer to one question that is not correct. Two students missing the same question count as two errors, but spoil only one question for the all-four-correct set.
Complete practice problem
A test has 15 questions. Four students answer 11, 12, 13, and 14 questions correctly. What is the minimum number of questions that all four students must have answered correctly?
Prove the lower bound in two different ways
Both methods show that at least five questions must be correct for all four students.
Method A · Spread the errors
To make the shared-correct set as small as possible, place errors on as many different questions as possible.
Method B · Count correct marks
The four students have:
If a question is not correct for all four, it contributes at most 3 correct marks.
The five marks above 45 force at least five questions to gain a fourth correct mark.
Construct an arrangement with exactly five shared correct answers
Now make the lower bound achievable. Click cells to switch between correct ✓ and error ✕.
Independent workshop
Solve at least 6 of 8 fresh problems. Each has a local hint.
Hint
The other six original news items must leave their owners.
Hint
One letter can newly fully inform at most one person.
Hint
Match the collection-and-distribution plan to the two lower bounds.
Hint
Could there still be a shorter plan?
Hint
Subtract each correct count from ten.
Hint
Use your total error count to bound how many different questions can contain an error.
Hint
Stack the errors inside the largest individual error set.
Hint
Both parts must refer to the same number.
Independent exit ticket
Solve all five fresh problems. The certificate also requires Missions 1–9.
Hint
Each of the two phases needs n − 1 letters.
Hint
Subtract each score from twelve.
Hint
Spread errors as widely as possible.
Hint
Check each row quota and the number of distinct spoiled columns.
Hint
A lower bound applies to every possible arrangement.
Achievement unlocked
Minimum-Proof Architect
This certifies that the learner can prove lower bounds, construct matching examples, generalize a communication minimum, and use extremal error placement to guarantee overlap.
Lesson 11.3 · Grade 5 Math Reasoning
Optional reflection — not automatically graded
Teaching notes
The information-group lower-bound explanation, animated network, general n-friend model, clickable answer matrix, workshop, and assessments are added instructional scaffolds.The letter model explicitly follows the original condition that each letter has one recipient and may contain everything the sender currently knows.