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!
Best Answer
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.
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:
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: