Problem: Let $S$ be a set containing $n^2+n-1$ elements.
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.

Solution: We present two solutions which are really equivalent, but phrased differently.
We refer to the two classes as ``red'' and ``blue'', respectively.

\paragraph{First solution (Grant Yu).}
We define a set of $n+1$ elements to be \emph{useful}
if it has $n$-element subsets in each class.

Consider a \textbf{maximal collection of disjoint useful sets}
and assume there are $p$ such sets.
Then, let $T$ be the set of elements remaining (i.e.\ not in one of chosen useful sets).
\begin{claim*}
  All subsets of $T$ of size $n$ are the same color.
\end{claim*}
\begin{proof}
  Assume there was a red set $R$ in $T$.
  Replace the elements of $R$ one by one
  until we get to any other subset $R'$ of $T$.
  At each step, because no sets of $T$ form a useful set,
  the set remains red --- so $R'$ is red too.
  Since $R'$ is arbitrary, this proves the claim.
\end{proof}
We have $|T| = n^2+n-1 - p(n+1)$, and in particular $p < n$.
WLOG all sets in $T$ are red.
We can extract another red set from each of our chosen useful sets.
So we can get at least
\[ p + \left\lfloor \frac{|T|}{n} \right\rfloor
  = p + \left\lfloor n+1-p - \frac{1+p}{n} \right\rfloor
  \ge p + (n-p) = n.  \]


\paragraph{Second solution (by induction).}
We prove more strongly that:
\begin{claim*}
  Let $S$ be a set containing $k \cdot (n+1)-1$ elements.
  Then we can find $k$ pairwise disjoint sets of the same color.
\end{claim*}
The proof is by induction on $k \ge 1$.
The base case $k=1$ this is immediate; $\binom{S}{n}$ is a single set.

For the inductive step, assume for contradiction the problem fails.
Let $T$ be any subset of $S$ of size $(k-1)(n+1)-1$.
By the induction hypothesis, among the subsets of $T$ alone,
we can already find $k-1$ pairwise disjoint sets of the same color.
Now $S \setminus T$ has size $n+1$, and so we would have to have
that all $\binom{n+1}{n}$ subsets of $S \setminus T$ are the same color.

By varying $T$, the set $S \setminus T$ ranges over all of $\binom{S}{k+1}$.
This causes all sets to be the same color, contradiction.

\begin{remark*}
  Victor Wang writes the following:
  \begin{quote}
  I don't really like this problem,
  but I think the main motivation for generalizing the problem
  is that the original problem doesn't allow you to look at small cases.
  (Also, it's not initially clear where the $n^2+n-1$ comes from.)
  And pretty much the simplest way to get lots of similarly-flavored
  small cases is to start with $k=2,3$ in
  ``find the smallest $N(n,k)$ such that when we partition the $n$-subsets
  of a $\ge N(n,k)$-set into $2$ classes,
  we can find some $k$ pairwise disjoint sets in the same class''.
  \end{quote}
\end{remark*}