1982 USAMO Problems/Problem 1

Problem

In a party with $1982$ 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?

Solution

We induct on $n$ to prove that in a party with $n$ people, there must be at least $(n-3)$ people who know everyone else. (Clearly this is achievable by having everyone know everyone else except three people $A, B, C$ , who do not know each other.)

Base case: $n = 4$ is obvious.

Inductive step: Suppose in a party with $k$ people (with $k \ge 4$ ), at least $(k-3)$ people know everyone else. Consider a party with $(k+1)$ people. Take $k$ of the people (leaving another person, $A$ , out) and apply the inductive step to conclude that at least $(k-3)$ people know everyone else in the $k$ -person group, $G$ .

Now suppose that everyone in the group $G$ knows each other. Then take $3$ of these people and $A$ to deduce that $A$ knows a person $B \in G$ , which means $B$ knows everyone else. Then apply the inductive step on the remaining $k$ people (excluding $B$ ) to find $(k-3)$ people out of them that know everyone else (including $B$ , of course). Then these $(k-3)$ people and $B$ , which enumerate $(k-2)$ people, know everyone else.

Suppose that there exist two people $B, C \in G$ who do not know each other. Because $k-3 \ge 1$ , there exist at least one person in $G$ , person $D$ , who knows everyone else in $G$ . Now, take $A, B, C, D$ and observe that because $B, C$ do not know each other, either $A$ or $D$ knows everyone else of $A, B, C, D$ (by the problem condition), so in particular $A$ and $D$ know each other. Then apply the inductive step on the remaining $k$ people (excluding $D$ ) to find $(k-3)$ people out of them that know everyone else (including $D$ , of course). Then these $(k-3)$ people and $D$ , which enumerate $(k-2)$ people, know everyone else.

This completes the inductive step and thus the proof of this stronger result, which easily implies that at least $1982 - 3 = \boxed{1979}$ people know everyone else.

1982 USAMO (Problems • Resources)
Preceded by First Question	Followed by Problem 2
1 • 2 • 3 • 4 • 5
All USAMO Problems and Solutions

Page

Toolbox

Search

1982 USAMO Problems/Problem 1

Problem

Solution

See Also