Olympiad combinatorics problem (probably related to graph theory?) Let me state the problem first. The problem is from the 2017 Japanese Mathematical Olympiad.
There are $n$ people in the group, where $n$ is greater than or equal to 3. Each day, some people (more than or equal to 3 people) from the group have a social gathering. For each gathering, everyone who participated in the gathering shake hands with each other. After the gathering of $n$-th day, any two people among total $n$ people shook their hands exactly once throughout all gathering. Show that the number of people attending each gathering is constant.
I tried to formulate it in a graph-theoretical way. On the very first day, there are $n$ vertices and no edge. Then we start to add a "clique" in this graph. After $n$ such operations, the graph became a complete graph (with no duplicate edges). Now what we want to show is the size of each clique added is always the same.
Number of total edges in $K_n$ is ${n \choose 2}$. As we add each clique with the size $k_i$, we are adding ${k_i \choose 2}$ edges. So I assume that it can be formulated as: $${n \choose 2} = {k_1 \choose 2} + {k_2 \choose 2} + \cdots + {k_n \choose 2}$$ Then $k_1 = k_2 = \cdots = k_n$. However I am not sure about the correctness.
Both formulation do not give me a hint about how to approach this problem. I am not skilled in both graph theory and combinatorics.
Thanks in advance!
 A: For each person $P$, let $\|P\|$ denote the number of gatherings $P$ was part of. For each gathering $g$, let $\|g\|$ denote the number of people who participated in the gathering.
Lemma. If $P$ is not part of $g$, then $\|P\| \ge \|g\|$.
Proof. Let $\|g\|=k$ and let $P_1, \dots, P_k$ be the people who participated in $g$. For each $i$, there has to be another gathering $g_i$ where $P$ and $P_i$ shook hands; the gatherings $g_1, \dots, g_k$ must be distinct, because if $g_i = g_j$ then $P_i$ and $P_j$ shake hands twice (once in $g$ and once in $g_i$). Since $P$ participates in all $k$ gatherings $g_1, \dots, g_k$, we have $\|P\| \ge k = \|g\|$. $\qquad\square$
To make use of this fact, we want to number the people $P_1, \dots, P_n$ and the gatherings $g_1, \dots, g_n$ such that $P_i$ does not participate in $g_i$ for $i=1, \dots, n$. This is a perfect matching between the people and the gatherings, in the "nonparticipation" graph where an edge $(P,g)$ means that $P$ was not part of $g$. We check Hall's condition: for any set of $k$ people, there are at least $k$ gatherings that not all of them were part of.

*

*If $k=1$, we want to know that there's nobody who was part of every gathering. Well, each person shakes hands a total of $n-1$ times, but they shake hands at least once in every gathering, so they're in at most $n-1$ gatherings (and out of at least one).

*If $2 \le k \le n-1$, then there's at most one gathering containing all $k$ people (because they can't shake hands twice), so at least $n-1$ (and therefore at least $k$) gatherings that don't contain all $k$ of them.

*If $k=n$, then there's $n$ gatherings, and no gathering contains all $n$ people.

So now we have inequalities $\|P_1\| \ge \|g_1\|$ through $\|P_n\| \ge \|g_n\|$. Well, both $\|P_1\| + \dots + \|P_n\|$ and $\|g_1\| + \dots + \|g_n\|$ count the number of pairs $(P,g)$ where person $P$ participated in gathering $g$. So the two sums are equal, and this can only happen if $\|P_i\| = \|g_i\|$ for all $i$.
Let's sort the gatherings such that $\|g_1\| \ge \dots \ge \|g_n\|$. Suppose there is a strict inequality here at some point: $\|g_i\| > \|g_{i+1}\|$. Then $\|P_{i+1}\|, \dots, \|P_n\|$ are all less than $\|g_1\|, \dots, \|g_i\|$ and so by the converse of our lemma, $P_{i+1}, \dots, P_n$ all participate in $g_1, \dots, g_i$. This results in two people participating in two gatherings together unless one of two cases holds:

*

*$i=1$, so $P_2, \dots, P_n$ all participate in $g_1$ together. But then $g_2$ (and all the ones after) can include at most one of $P_2, \dots, P_n$, so $\|g_2\| \le 2$, which is ruled out by the problem.

*$i=n-1$, so $P_n$ participates in all of $g_1, g_2, \dots, g_{n-1}$. But now $\|P_n\| = n-1$, and by assumption $\|P_{n-1}\| > \|P_n\|$: it must be $n$. But we've already shown that nobody can be part of all $n$ gatherings.

So we can't have $\|g_i\| > \|g_{i+1}\|$ for any $i$, which means $\|g_1\| = \dots = \|g_n\|$, which was what we wanted. (Incidentally, it also means that $\|P_1\| = \dots = \|P_n\|$.)

The proof above is an adaptation of the proof in this 1948 paper by de Bruijn and Erdos. That paper actually analyzes this case as a side note: it shows that without the requirement that there are only $n$ gatherings, there must always be at least $n$.
If all gatherings have size $k$, then we have $\binom n2 = n \binom k2$, which simplifies to $n = k^2-k+1$. There are constructions where this works for many, but not all, $k$. For example:

*

*When $k=3$, number the people $1, 2, \dots, 7$ and take the gatherings whose participants are the sets $\{1, 2, 3\}$, $\{1,4,5\}$, $\{1,6,7\}$, $\{2,4,6\}$, $\{2,5,7\}$, $\{3,4,7\}$, $\{3,5,6\}$. This construction is known as the Fano plane.

*The Fano plane is a projective plane over $\mathbb F_2$, and we can generalize the construction to any finite field $\mathbb F_q$. Here, $q$ must be a prime power, and $k$ will be $q+1$.

*When $k-1$ is not a power of a prime, it is an open problem to show that no constructions exist. (We know that $k-1=6$ and $k-1=10$ are impossible as of 1989, and haven't managed to even deal with $k-1=12$ since then.)

