Isn't a complete solution, only parcial, because i'm not certain if is completely right! Let G a graph with $C(n^{2}+n-1,n)$ vertices (each vertice assigned to one of the sets with n elements). Two vertices are linked by one edge if the intersection of your sets are empty. We easily see that each vertice have degree $C(n^{2}-1,n)$. If we cut G in two graphs X and Y (erasing the edges from X to Y, only considering the edges from one vertice of X to X, and the same for Y), i found that, using turan, if the two sets don't have a $K_{n}$, we will get a contradction! My doubt is about my computations, but i guess that my idea isn't wrong!

N.T.TUAN wrote: 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 think maybe it should be $|S|=n^{2}+n-1$ in the title of the topic. Let us prove the stronger problem by induction: Proposition:Let $S$ be a set containing $nk+k-1$ elements, for some positive integer $n,k$. Suppose that the $n-$ element subsets of $S$ are partitioned into two classes. Prove that there are at least $k$ pairwise disjoint sets in the same class. Proof: Induction base: For $k=1$, the statement is obvious. Induction step: assume that for all integer not greater than $k$, we have proved the proposition, Let us prove the $k+1$ case: Let us say $A$ and $B$ (with $|A|=|B|=n$ and $A,B\subset S$) are adjacent if only if $\left|A\cap B\right|=n-1$. Separate into two cases: Case 1: If there exist $X,Y\subset S$ such that $X,Y$ are adjacent, and $X,Y$ are not in the same class, then Let us consider the set $S'=S-X\cup Y$ then $|S'|=n(k+1)+k+1-1-(n+1)=nk+k-1$, By the assumption of the induction, there exist $k$ pairwise disjoint sets in the same class,then these $k$ sets and one of $X,Y$ are pairwise disjoint and in the same class. (This is because $X,Y$ are not in the same class, and $(X\cup Y)\cap S'= \emptyset$.) Case 2: If for all $X,Y\subset S$ with the property that $X,Y$ are adjacent, $X,Y$ are in the same class, then we can prove easily that all the sets are in the same class. (Because we find some subset $A_{1}$ of $S$ with $|A_{1}|=n+1$; then all the subsets of $A_{1}$ must be in the same class, and for any element $u$ of $S-A_1$ and any $n-1$-elements set $P,P\subset A_{1}$, the subset $P\cup \{u\}$ is in the same class with all the subsets of $A_{1}$, then let $A_{2}=A_{1}\cup \{u\}$, then $A_{2}$ has the property that all the subsets of $A_{2}$ are in the same class; in the same way, we can find $A_{3}$, $A_{4}$,........., $A_{t}=S$.) I hope my solution is correct. I always commit some stupid and small mistakes, I am not so confident now....... (Er, Maybe I am so confident that always ignore the details )

I didn't check all the details, but you've got the right idea (I tried to solve it for quite a few hours, but then I finally... snapped... and I looked over the official solution).

Hawk Tiger wrote: Proposition:Let $S$ be a set containing $nk+k-1$ elements, for some positive integer $n,k$. Suppose that the $n-$ element subsets of $S$ are partitioned into two classes. Prove that there are at least $k$ pairwise disjoint sets in the same class. What is the motivation for this? Is there some heuristic that might lead you to believe the number of sets ($k$) and their sizes ($n$) are actually unrelated? (Sorry for the massive revive.)

v_Enhance wrote: Hawk Tiger wrote: Proposition:Let $S$ be a set containing $nk+k-1$ elements, for some positive integer $n,k$. Suppose that the $n-$ element subsets of $S$ are partitioned into two classes. Prove that there are at least $k$ pairwise disjoint sets in the same class. What is the motivation for this? Is there some heuristic that might lead you to believe the number of sets ($k$) and their sizes ($n$) are actually unrelated? 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." One way to see that it might be helpful: If you first look at the obvious bound $N(n,n)\le (2n-1)n$ (by considering the $2n-1$ pairwise disjoint sets $[1,n],[n+1,2n],\ldots,[(2n-2)n+1,(2n-1)n]$), it's fairly natural to think about the analogous bound $N(n,k)\le (2k-1)n$. (On the other hand, changing the number of classes just complicates the situation.) Of course, it's not immediately obvious that the $k$ and $k+1$ cases are related---at best you might be able to build off from $k$ to $k+1$, but a priori you might only expect it to give a better understanding of how $N(n,k)$ grows.

Quote: Proposition:Let $S$ be a set containing $nk+k-1$ elements, for some positive integer $n,k$. Suppose that the $n-$ element subsets of $S$ are partitioned into two classes. Prove that there are at least $k$ pairwise disjoint sets in the same class. Proof of easier proposition: Induct on $k$. If $k=1$, we are considering $n$-element subsets of an $n$-element set, which makes the statement trivial. Now suppose the statement holds for $k-1$, for some $k>1$, and AFSOC that we lose for $k$. Suppose that $A$ and $B$ are two $n$ element subsets of $S$, with $n-1$ elements in common. We claim that they are in the same class. Indeed, $S-A\cup B$ has size $(n+1)(k-1)-1$, so by the inductive hypothesis, one of the two classes has a collection $C$ of $k-1$ size $n$ subsets of $S-A\cup B$. So if $A$ and $B$ are in different classes, we can choose one of them appropriately to add to $C$, yielding a new collection of size $k$, as desired. So we've shown that replacing any element in an $n$ element subset of $S$ keeps its class constant, which easily implies that all $n$ element subsets of $S$ must be in the same class, which implies what we want.

EDIT: Oh wait I see now.

@above, why is isn't it $n+1$

if m=2 S has 2n - 1 elements and please show me there are at least n-elements $2$ pairwise disjoint sets in the same class.

if m=2 S has 2n - 1 elements and please show me there are at least n-elements $2$ pairwise disjoint sets in the same class.

Induction argument supplied by awang11. We show a generalization of this result: let $S$ be a set of $k(n+1)-1$ sets. Let the subsets of $S$ with cardinality $n$ be partitioned into two classes. Show that one of the classes contains $k$ pairwise disjoint sets. The proof is by induction on $k$. If $k=1$, the result is obvious. For $k\ge 2$, we use the following argument to achieve the result. Let $A$ and $B$ be sets with cardinality $n$ and $|A\cap B|=n-1$. We claim that $A$ and $B$ lie in the same class or we are done, which clearly suffices. Suppose that $A$ and $B$ lie in separate classes. By the inductive hypothesis on $T=S\setminus (A\cup B)$, one of the classes restricted to $T$ contains $k-1$ pairwise disjoint sets, so the result holds for $k$ by considering those $k-1$ pairwise disjoint sets by using the appropriate choice of $A$ and $B$ as the $k$-th set.

We prove the more general statement: in a set $S$ of $m(n+1)-1$ elements, if we partition the $n$-element subsets of $S$ into two classes, then there are at least $m$ pairwise disjoint sets in the same class. This is by induction on $m$, with the base case of $m=1$ being trivial. For the inductive step, consider any $n+1$ elements in $S$ and temporarily hide them; among the remaining $(m-1)(n+1)-1$ elements, we can find $m-1$ $n$-element subsets in the same family which are disjoint. Then, if we cannot find $m$ pairwise disjoint sets in the same class, no $n$-element subset formed from the $n+1$ hidden elements can be in the same family, so they must all be in the same family—in other words, any two $n$-element subsets which overlap in $n-1$ positions are in the same family. But this clearly implies that every $n$-element subset is in the same family, in which we can obviously find $m$ pairwise disjoint sets, as desired. $\blacksquare$ Remark: Perhaps a possible way to motivate the idea that the number of sets and their size is unrelated is to discover a class of "equality cases" where the size of $S$ is "tight": for some fixed $1 \leq k \leq n$, take $kn-1$ elements and color them red. Put every set with at least $k$ red elements in one family and the rest in another. We can find $n$ disjoint subsets in the second family by forming each subset using $k-1$ red elements and $n-k+1$ non-red elements, and we will have enough non-red elements to do this, but for $|S|=n^2+n-2$ this is no longer the case. However, the fact that the number of sets and their size is the same is not relevant to this "equality case". For the more general case we can take $km-1$ elements instead and essentially employ the same construction. Furthermore, it seems that the generalized statement is true in general by checking small cases, so it is motivated to pursue it instead, with induction now seeming viable.

Solved with hint 40\% to consider general. when generalizing makes it easier skull We induct on k with \# of elements k(n+1)-1, with base case k=1 evident; ignore an arbitrary n+1 elements. AWLOG the first family has by inductive hypothesis n-1 pairwise disjoint sets, FTSOC exactly that amount, then the other n+1 sets formed by the n+1 elements choosing n elements are all in the second family; in particular, any n sets that overlap in n-1 elements are in the same family, which by varying the such n+1 elements that are ignored, implies all sets are in the same family, so we can find n disjoint sets in the same family. We conclude.

We generalize to showing $k$ pairwise disjoint sets for $k(n+1)-1$ elements. The base case of $k=1$ holds. Now suppose it holds for $k$ and consider a set $S$ of $(k+1)(n+1) - 1$ elements and a partition. FTSOC there are not $k+1$ pairwise disjoint sets. By the inductive hypothesis, considering the $n$ element subsets of a $k(n+1) - 1$ subset $S' \subset S$ which can vary, one of the partitions of $S$ contains $k$ pairwise disjoint subsets with elements in $S'$. This implies that all subsets only containing elements in $S \setminus S'$ must be in the other partition. Since $S \setminus S'$ can be any subset of $n+1$ elements, repeating this as $S'$ varies implies that all elements are in the same partition, contradiction.

We instead suppose $|S| = k(n+1)-1$, and prove there are at least $k$ disjoint $n$-element subsets in the same class using induction starting from the trivial base case $k=1$ up to $k=n$. Assuming $k=m-1$ holds, we claim the hypothesis also holds for $k=m$: The hypothesis says we already have $m-1$ disjoint $n$-element subsets in, say, class $C_1$. Assume FTSOC we do not have the last subset. Consider a subset $T_1$ with $|T_1|=(m-1)(n+1)-1$, and let $T_1' = S \setminus T = \{a_1,\ldots, a_{n+1}\}$, where $|T_1'| = n+1$. The $\binom{n+1}{n}=n+1$ $n$-element subsets of $T'$ must all be in class $C_2$. Considering another subset $T_2$ with $T_2' = \{a_1,\ldots,a_n,a_{n+2}\}$, we again see all subsets of $T_2'$ must be in the same class, and since $\{a_1,\ldots,a_n\} \subset T_1', T_2'$, they all belong in class $C_2$ as well. By continuing to vary $T_i$, every $n$-element subset belongs in class $C_2$, contradiction. $\blacksquare$

We will prove a more generalized version of the problem, where $|S| = k(n+1)-1$ and we prove that there are at least $k$ pairwise disjoint sets in the same class. The base case of $k=1$ is vacuous. For the inductive step, suppose that the inductive hypothesis holds for $k$. FTSOC neither of the two classes have $k+1$ pairwise disjoint sets for $|S| = (k+1)(n+1)-1$. Take any set $T \subset S$ such that $|T| = k(n+1)-1$. We can split the elements of $T$ into a red class and a blue class; by the inductive hypothesis, one of the classes has $n$ pairwise disjoint sets, WLOG say the red class. The remaining $n+1$ $n$-element subsets are each disjoint from the $n$ pairwise disjoint sets in the red class, so they all must go in the blue class. Varying $T$ slightly over all possible subsets of $S$ yields that every $n$-element subset goes in the blue class, a contradiction. $\blacksquare$