Metric Space - Combinatorics question: Minimum number of people who know each other in a party of 1982

Problem Intro

While looking for combinatorics problems to solve, I stumbled across this gem on Math stackexchange

While there is a link to the solution, my solution differs from it.

My proof is more a solution by construction

The question is as follows:

In a party with 1982 persons, among any group of 4, there is at least one person, who knows each of other three. What is the minimum number of people in the party who knows everyone else?

Solution

The key bit here is Given any group of 4 people, there is at least one person who knows each of the other three . From hereon out we'll refer to this bit as Statement A

So if we enumerate all the possible groups of 4 people from the total head count of 1982 i.e \( \mathbf{C}^{1982}_{4} \), and Statement A applies to all of these groups

So we start building our solution by crafting these \( \mathbf{C}^{1982}_{4} \) groups manually while keeping in mind (again) Statement A has to be fullfilled.

Let's say we enumerate all the people in the party as \( p_1, p_2, p_3, \ldots, p_{1982} \)

We start by saying \( p_1 \) knows everyone else in the party.

The number of groups (order is irrelevant) of 4 people that can be formed from \( p_1 \) and the rest of the party is \( \mathbf{C}^{1981}_{3} \)

Now we move on to the next person \( p_2 \) who knows everyone else in the party, but while forming groups of 4 this time we want to avoid double counting so we'll avoid the groups already constructed as part of \( p_1 \)'s portion'

The number of groups (order is irrelevant) of 4 people that can be formed from \( p_2 \) and the rest of the party (excluding the groups that have \(p_1 \)) is \( \mathbf{C}^{1980}_{3} \)

As we go down the line we'll have to avoid the groups already constructed using the previous people

So to make it clear as to how significant the double counting is, this is let's consider the following:

By the time we make it to \( p_{1979} \), the groups that can be formed from \( p_{1979} \) and the rest of the party (excluding the groups that have \(p_1, p_2, \ldots, p_{1978} \)) is \( \mathbf{C}^{3}_{3} \)

Let's tally up the total count we have so far:

\( \mathbf{C}^{1981}_{3} + \mathbf{C}^{1980}_{3} + \ldots + \mathbf{C}^{3}_{3} = \mathbf{C}^{1982}_{4} \) (from the Hockey Stick Identity)

So we built groups of four manually and we've arrived at the limit of \( \mathbf{C}^{1982}_{4} \) groups by the time we're done with the 1979th person and we've done so in such a way that Statement A is satisfied

Something to point out: We've been left with 3 people who all the other folks know but they don't know each other but know everybody else, i.e \( p_{1980}, p_{1981}, p_{1982} \)

So the minimum number of people in the party who know everyone else is 1979