Maths Olympiad Prep

Library / /48 of 115

Combinatorics Difficulty 7.2 National olympiad, round 2 Find the answer

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

A number or a short expression. Spacing and $ signs are ignored.

Solution

We induct on nn to prove that in a party with nn people, there must be at least (n3)(n-3) people who know everyone else. (Clearly this is achievable by having everyone know everyone else except three people A,B,CA, B, C , who do not know each other.)
Base case: n=4n = 4 is obvious.
Inductive step: Suppose in a party with kk people (with k4k \ge 4 ), at least (k3)(k-3) people know everyone else. Consider a party with (k+1)(k+1) people. Take kk of the people (leaving another person, AA , out) and apply the inductive step to conclude that at least (k3)(k-3) people know everyone else in the kk -person group, GG .
Now suppose that everyone in the group GG knows each other. Then take 33 of these people and AA to deduce that AA knows a person BGB \in G , which means BB knows everyone else. Then apply the inductive step on the remaining kk people (excluding BB ) to find (k3)(k-3) people out of them that know everyone else (including BB , of course). Then these (k3)(k-3) people and BB , which enumerate (k2)(k-2) people, know everyone else.
Suppose that there exist two people B,CGB, C \in G who do not know each other. Because k31k-3 \ge 1 , there exist at least one person in GG , person DD , who knows everyone else in GG . Now, take A,B,C,DA, B, C, D and observe that because B,CB, C do not know each other, either AA or DD knows everyone else of A,B,C,DA, B, C, D (by the problem condition), so in particular AA and DD know each other. Then apply the inductive step on the remaining kk people (excluding DD ) to find (k3)(k-3) people out of them that know everyone else (including DD , of course). Then these (k3)(k-3) people and DD , which enumerate (k2)(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 19823=19791982 - 3 = \boxed{1979} people know everyone else.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.