Problem 1428

Solution:
If every person knows $1686$ others then for each person, there are $2023 - 1686 - 1 = 336$ people that they don't know. Now consider any group of $p$ people from the office. There will be at most $336p$ people who don't know someone in the group ($336$ for each person in the group). Therefore there are at least $(2023 - p) - 336p$ people not in the group who know everyone in the group. If $p \leq 6$ then
$$(2023 - p) - 336p \geq (2023 - 6) - 336 \times 6 = 1.$$
So for any group of at most $6$ 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 = 2$ people who know each other, and then, while $p \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 $7$ people each knowing everyone in the group.

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

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

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

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

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