There are $3$ classes with $n$ students in each class, and the heights of all $3n$ students are pairwise distinct. Partition the students into groups of $3$ such that in each group, there is one student from each class. In each group, call the tallest student the tall guy. Suppose that for any partition of the students, there are at least 10 tall guys in each class, prove that the minimum value of $n$ is $40$.
Problem
Source: CGMO 2020 Day1 P3
Tags: combinatorics
10.09.2020 15:37
Let this 3 classes be A, B, C, respectively. Let the heights of students from class A be $a_1, a_2, \dots, a_n$, heights of class B be $b_1, \dots, b_n$, heights of class C be $c_1, \dots, c_n$. WLOG let $a_1>a_2>\dots>a_n, b_1>b_2>\dots>b_n, c_1>c_2>\dots>c_n$ and $a_{\left\lceil\frac{n}{2}\right\rceil}>b_{\left\lceil\frac{n}{2}\right\rceil}$ and $a_{\left\lceil\frac{n}{2}\right\rceil}>c_{\left\lceil\frac{n}{2}\right\rceil}$ For any $i$ in range $[1, \left\lceil\frac{n}{2}\right\rceil]$, we arrange students with heights $a_i, b_{n+1-i}, c_{n+1-i}$ to be in the same group. Since $$n+1-i \ge n+1-\left\lceil\frac{n}{2}\right\rceil \ge \left\lceil\frac{n}{2}\right\rceil$$we have $$a_i \ge a_{\left\lceil\frac{n}{2}\right\rceil} > b_{\left\lceil\frac{n}{2}\right\rceil} \ge b_{n+1-i}, a_i \ge a_{\left\lceil\frac{n}{2}\right\rceil} > c_{\left\lceil\frac{n}{2}\right\rceil} \ge c_{n+1-i}$$so there must be at least $\left\lceil\frac{n}{2}\right\rceil$ tall guys in class A. Since the number of tall guys from class B or C combined must be at least $20$, $n - \left\lceil\frac{n}{2}\right\rceil \ge 20, n \ge 40$. On the other hand, if class A has heights $111-120, 1-30$, class B has $91-110, 31-50$, class C has $51-90$, it’s easy to check that each class has at least 10 tall guys.
27.10.2020 20:49
I do in this way but I am stuck. Let $(a_i)_{i=1}^n,(b_i)_{i=1}^n,(c_i)_{k=1}^n$ be 3 pairwise disjoint increasing sequences of positive integer and be a partition of $1,2,\dots,3n$. If the following condition holds for 10 times in each sequence then $n \geq 40$; the $i^{th}$ sequence less than $2i$.