1982 USAMO Problems/Problem 1
In a party with people, among any group of four there is at least one person who knows each of the other three. What is the minimum number of people in the party who know everyone else?
We induct on to prove that in a party with people, there must be at least people who know everyone else. (Clearly this is achievable by having everyone know everyone else except three people , who do not know each other.)
Base case: is obvious.
Inductive step: Suppose in a party with people (with ), at least people know everyone else. Consider a party with people. Take of the people (leaving another person, , out) and apply the inductive step to conclude that at least people know everyone else in the -person group, .
Now suppose that everyone in the group knows each other. Then take of these people and to deduce that knows a person , which means knows everyone else. Then apply the inductive step on the remaining people (excluding ) to find people out of them that know everyone else (including , of course). Then these people and , which enumerate people, know everyone else.
Suppose that there exist two people who do not know each other. Because , there exist at least one person in , person , who knows everyone else in . Now, take and observe that because do not know each other, either or knows everyone else of (by the problem condition), so in particular and know each other. Then apply the inductive step on the remaining people (excluding ) to find people out of them that know everyone else (including , of course). Then these people and , which enumerate people, know everyone else.
This completes the inductive step and thus the proof of this stronger result, which easily implies that at least people know everyone else.
|1982 USAMO (Problems • Resources)|
|1 • 2 • 3 • 4 • 5|
|All USAMO Problems and Solutions|