Combinatorics Generalized Pigeonhole Principle question

Question

I cant solve this exercise / I dont understand it: There are n kids and 3 possible classes. Every couple of kids are going to the same class, prove that there is a class that 2/3 of the kids are going to.

Answer 1

Let $n$ be the number of kids, and let $x\ge y\ge z$ be the class sizes. We have to show that $x\ge\frac23n$.

We may assume that each kid is in at least two classes, for if some kid were in only one class, then they weould all have to be in that class.

Let $p$ be the number of pairs $(C,K)$ consisting of a class and a kid in that class.

Counting then one way, we clearly have $$p=x+y+z\le3x.\tag1$$

Counting them another way, since there are $n$ kids and each kid is in at least two classes, $$p\ge2n.\tag2$$

Combining the inequalities $(1)$ and $(2)$, we get $$3x\ge2n,$$ that is, $$x\ge\frac23n.$$

Answer 2

Here is a way of proving it for all $n \geq 2$.

Assume that we can place $n$ children into $3$ classes such that every child shares at least one class with every other child and such that every class has size less than $\frac{2}{3} n$.

Let $m$ denote the smallest integer greater than $\frac{1}{3} n$ and let $k$ denote the largest integer less than $\frac{2}{3} n$.

Note that if such a class arrangement is possible, we can expand each class such that each class contains $k$ students. Thus we assume each of the three classes has $k$ students.

Choose one of the three classes and label this Class $1$. Since Class $1$ has $k$ students, the number of students not in Class $1$ is equal to $m$.

Now these $m$ students must all be in the same class. I'll leave this for you to show. Call this Class $2$. Since Class $2$ has $k$ students, this means that exactly $k-m$ students from Class $1$ must be in Class $2$ along with these $m$ students.

Since the $m$ students not in Class $1$ still do not have a class with the remaining $k-(k-m) = m$ students from Class $1$, Class $3$ must contain at least all of these students. However, this would imply Class $3$ has at least $2m$ students which is larger than $k$. Contradiction.

Thus, in order for such a class arrangement to be possible, one of the three classes must contain at least $\frac{2}{3} n$ students.