Prove that there are at least $n$ pairwise disjoint sets in the same class. Let $S$ be a set containing $n^{2}+n-1$ elements, for some positive integer $n$. Suppose that the $n$-element subsets of $S$ are partitioned into two classes. Prove that there are at least $n$ pairwise disjoint sets in the same class.
I was thinking to use induction on $|S|$, with base $n=1$, and it works for $n=1$. However I am not able to proceed.
 A: (Not a solution, but a response to OP's comment. Too long to be a comment.)
There can be several motivating reasons for the induction on $k$, independent of knowing the solution.

*

*Knowing that olympiad problems that seem inaccessible often have a "nice" solution after making an insightful observation.

*Playing with $n^2 + n -1$ early on quickly gets out of hand. If we wanted to get a stronger handle on the problem, we should look for "Find the smallest $N(n,k)$ such that when we partition ....".

*It is not uncommon for olympiad problems to be a unique case of an inductive process. This allows them to hide suggestions that would have made the problem much easier. E.g. Prove that a $8 \times 8$ chessboard with 1 square removed can be tiled by $L-$shaped triminos.

*Study the counterexample when we have $n^2+n - 2$ elements and no $n$ pairwise disjoint sets: Let set $A$ have $n^2 - 1$ elements and set $B$ have the other $n-1$ elements. Let the first class be any n-element subset of $A$, and the second class be the rest of the n-element subsets (which clearly have a non-zero intersection with $B$). Then clearly we can find at most $n-1$ disjoint sets in a class, with a suggested indexing via a bijection with $B$. This suggests a generalized counterexample that $k$ subsets of size $n$ are not possible if we have a $B$ with $k-1$ elements, and set $A$ with $ kn-1$ elements which gives us $(k+1)n - 2 $ elements, and suggests (wishful thinking) that with $N(n,k) = (k+1)n - 1 $ elements we can find $k$ disjoint subsets.

*(weak) Your suggested induction approach doesn't seem to yield a nice inductive hypothesis step, so if we really wanted to use induction we need to figure out a valid variable $k$ to induct on.

A: This is USAMO 2007 Problem 3.
I will prove the stronger claim: If we have $k \cdot (n + 1) - 1$ elements, then we will have at least $k$ disjoint subsets in a class. Applying this result with $k = n$ gives the desired result. We can proceed by inducting on $k$.
When $k = 1$, this is clearly true since if we have $n$ elements, then we'll have $1$ disjoint subset in a class.
Now we consider two disjoint but exhaustive cases.
First consider the case in which all $(n + 1)$-element subsets have all of their $n$-element subsets in a single class. Take any two $n$-element subsets, say $S_1$ and $S_k$. Clearly, there exists a sequence $S_1, S_2, \ldots, S_k$ such that any two consecutive terms belong to the same subset with $n + 1$ elements. Thus, $S_1$ and $S_k$ are in the same class, which means all subsets are in a single class. Therefore, we can find $k$ disjoint subsets of size $n$.
Next consider the case in which there is a single $(n + 1)$-element subset, say $S$, such that $S$ has two $n$-element subsets in distinct classes. In this case, there are exactly $(k - 1)(n + 1) - 1$ elements that aren't in $S$. However, by assumption, we'd have $k - 1$ disjoint subsets in some class, which pair with some other subset. We can use these $k - 1$ subsets to form $k$ disjoint subsets of size $n$, as desired.
