prove that the number of students in the school is at most k

Question

Students in a school go for ice cream in groups of at least two. After $k > 1$ groups have gone, every two students have gone together exactly once. Prove that the number of students in the school is at most k using a combinatorial approach.

Source: problem 1 from this olympiad training handout.

There is a slick solution using incidence vectors mentioned in the handout, though the handout also mentions that there is a combinatorial solution that's somewhat long and non-intuitive. How would one find a combinatorial solution for this problem? E.g. would one count the number of students in the school in two different ways or find some sort of bijection? We can obviously make similar observations to the beginning of the linear algebraic solution: if some student went for ice cream only once, everyone else has to have gone with that student. Since each group has at least two students, no other groups can be formed (otherwise some two students will have gone together more than once). $k>1$ thus yields a contradiction. Hence every student must have gone for ice cream at least twice. The incidence vector $v_i \in \mathbb{R}^k$ defined in the solution satisfies $(v_i)_j = 1$ if student i went with the jth group and 0 otherwise. I think a similar definition can be used in a combinatorial approach.

It might also be useful to at least consider a proof by induction, though from my understanding inductive proofs aren't exactly "combinatorial" in nature. Combinatorial proofs usually involve bijections or the direct counting of objects. If $k=2,$ then $n(n-1)/2$ pairs of students must have gone together, where n is the number of students. If $n-1 \ge x \ge 2$ students are in the first group, then each of these students must go together with the $n-x$ remaining students in the second group, so the second group must have $n$ students, which is a contradiction because then the pairs of students that appeared in the first group will appear again in the second group. Hence in fact we must have $k \ge 3$.

As an example, if there are $4$ students $1,2,3,4$ and $k=4$, then we can have the groups $\{1,2,3\}, \{1,4\}, \{2,4\}, \{3,4\}.$ It doesn't seem possible to have $k=3$ when there are 4 students.

Answer 1

If we think of the students as $n$ vertices of the complete graph $K_n$, and the "ice cream groups" as cliques of the complete graph, then we can formulate the problem as the following:

Let $k$ and $n$ be positive integers. Suppose the complete graph $K_n$ can be partitioned into $k$ smaller cliques with at least two vertices. Then $n \leq k$.

This led me to finding an answer in https://cstheory.stackexchange.com/a/31586, which stated that this is a known result by Bruijn, de, N. G. and Erdös, P., published in a 1948 work titled "On a combinatorial problem". The publication can be found in https://research.tue.nl/en/publications/on-a-combinatorial-problem. The relevant result is the first half of Theorem 1; the second half describes the groups/cliques to achieve the equality.

Arguably, the key fact for the proof is the following statement labeled (2) in Bruijn and Erdös' work:

For any student $s$ and any student group $G$, if $s$ is not in $G$, then the number of students in $G$ cannot exceed the number of groups containing $s$.

I would say that the half-page proof is indeed combinatoric and should fulfil OP's request for a combinatorial proof. The proof is also self-contained.