Maths Olympiad Prep

Library / /25 of 41

Combinatorics Difficulty 5.8 AIME, harder Prove it New Zealand

Problem:
There are 20232023 employees in the office, each of them knowing exactly 16861686 of the others. For any pair of employees they either both know each other or both don't know each other. Prove that we can find 77 employees each of them knowing all 66 others.

Solutions — 2

Solution 1

Solution:
If every person knows 16861686 others then for each person, there are 202316861=3362023 - 1686 - 1 = 336 people that they don't know. Now consider any group of pp people from the office. There will be at most 336p336p people who don't know someone in the group (336336 for each person in the group). Therefore there are at least (2023p)336p(2023 - p) - 336p people not in the group who know everyone in the group. If p6p \leq 6 then
(2023p)336p(20236)336×6=1.(2023 - p) - 336p \geq (2023 - 6) - 336 \times 6 = 1.
So for any group of at most 66 people, there exists at least one person not in the group that knows everyone in the group. Hence we perform the following process.

- Start with a random group of p=2p = 2 people who know each other, and then, while p6p \leq 6, choose a person who knows all the current members of the group (at random) and add them to the group.

This process ends with a group of 77 people each knowing everyone in the group.

Solution 2

Solution:
We will show by induction that, for non-negative integers kk and n>0n > 0, if there are nk+1nk + 1 people such that any of them know at least n(k1)+1n(k - 1) + 1 of the others, then there are k+1k + 1 people who all know each other. For k=0k = 0 this is true, as we have one person.

Now assume this is true for some integer kk. Among any n(k+1)+1n(k + 1) + 1 people who all know at least nk+1nk + 1 of the others, pick an arbitrary person PP, and a set S\mathcal{S} of nk+1nk + 1 people that PP knows.

For any person in S\mathcal{S}, they must know at least n(k1)+1n(k - 1) + 1 others in S\mathcal{S}, as there are exactly nn people outside of S\mathcal{S}, and they know at least nk+1nk + 1 people in total. Hence by our induction hypothesis, S\mathcal{S} contains k+1k + 1 people who all know each other.

As PP knows everyone in S\mathcal{S}, including PP gives a group of k+2k + 2 people who all know each other, proving our inductive result.

Now letting n=337n = 337 and k=6k = 6, we get the desired result.

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.