In an EGMO exam, there are three exercises, each of which can yield a number of points between $0$ and $7$. Show that, among the $49$ participants, one can always find two such that the first in each of the three tasks was at least as good as the other.
Problem
Source: Swiss IMO TST 2016. Problem 12
Tags: combinatorics
28.07.2017 19:27
Define $D=\{2^a3^b5^c: 0\le a,b,c\le 7\}$ Consider the loser $(D,\mid)$. We just want to find the largest antichain of $D$. It is asserted by the fact that $D$ can be expressed as a disjointed union of symmetric chains. So the largest antichain is as large as $\{2^a3^b5^c\in D:a+b+c=10\}$, which has less than 49 elements.
28.07.2017 19:44
We name 2 sequences with n numbers "comparable" if $a_i\geq b_i$ for all $i=1,n$ Let's say we can't find. Let's look at the 1st problem and at the 2nd one. (x,y)-means that x points are on problem 1, and y points on problem 2.($0\leq x,y\leq 7$) Look at the next sequences: 1. $(0,1)<(0,2)<...<(0,7)<(1,7)<(2,7)<...<(7,7)$-15 pairs. 2.$(1,0)<(1,1)<(1,2)<...<(1,6)<(2,6)<(3,6)<...<(7,6)$-13 pairs. 3.$(2,0)<(2,1)<(2,2)<...<(2,5)<(3,5)<(4,5)<...<(7,5)$-11pairs. 4.$(3,0)<(3,1)<(3,2)<(3,3)<(3,4)<(4,4)<...(7,4)$-9 pairs. We have a total of 48 pairs, which leaves us with 16 unused pairs. Claim 1. We can't have more than 9 participants with the respectively pair of points(for 1 and 2) in the same sequence). Proof: By Pigeonhole Principle, we'll have 2 contestants with the same score on problem 3, which makes them "comparable" because they are in the same sequence. So we have a maximum of 8 participants in every sequence, which gives us maximum $8*4=32$ participants. Now for the rest of 16 unused pairs, obviously we can't have 2 participants with the same score on problems 1 and 2, otherwise they would have "comparable" scores. Leaves us with maximum 16 participants for these 16 unused pairs. So we have a total of maximum $32+16=48$ participants, which is a contradiction.
28.07.2017 20:33
This is a special case of the de Bruijn-Tengbergen-Kruyswijk theorem: Given a poset $P=\prod_{i=1}^nC_i$, where $C_i=\{0,1,\dots,k_i\}$ (so $P$ is the product of $n$ finite chains), with the "product order" $$(x_1,x_2,\dots,x_n)\preceq(y_1,y_2,\dots,y_n)\iff x_i\leq y_i\quad\forall1\leq i\leq n$$(which makes $P$ a ranked poset), the maximal length antichain is the set of elements with "middle rank" i.e. the elements $(x_1,x_2,\dots,x_n)$ with $\sum_{i=1}^nx_i=\left\lfloor\frac{1}{2}\sum_{i=1}^n k_i\right\rfloor$. Recall that the rank of an element $(x_1,\dots,x_n)\in P$ is $\sum_{i=1}^nx_i$. Call a sequence of elements $A_1,\dots,A_k\in P$ a symmetric chain if $\operatorname{rank}(A_1)+\operatorname{rank}(A_k)=\sum_{i=1}^nk_i$ For each $1\leq i<k$, $\operatorname{rank}(A_{i+1})-\operatorname{rank}(A_i)=1$. We make the following crucial claim: Claim. $P$ can be partitioned into disjoint symmetric chains. Proof. We proceed by induction on $n$. The base case $n=0$ is trivial, so we prove the result for $P'=P\times C_{n+1}$, where $C_{n+1}=\{0,1,\dots,k_{n+1}\}$. Take a symmetric chain $A_1,\dots,A_k$ of $P$, and suppose $A_i=(a_{i,1},\dots,a_{i,n})$. Our induction would be complete if we show that we can partition the set $(A_i,j)=(a_{i,1},\dots,a_{i,n},j)$, where $1\leq i\leq k$ and $0\leq j\leq k_{n+1}$, into disjoint symmetric chains. Indeed, we have the following "diagonal" construction (where elements of the same colour are in the same symmetric chain): $$\begin{array}{cccc} \color{red}{(A_1,0)} & \color{green}{(A_2,0)} & \dots & \color{blue}{(A_k,0)} \\ \color{red}{(A_1,1)} & \color{green}{(A_2,1)} & \dots & \color{blue}{(A_k,1)} \\ \vdots & \vdots & \ddots & \vdots \\ \color{red}{(A_1,k_{n+1}-1)} & \color{green}{(A_2,k_{n+1}-1)} & \dots & \color{green}{(A_k,k_{n+1}-1)} \\ \color{red}{(A_1,k_{n+1})} & \color{red}{(A_2,k_{n+1})} & \color{red}{\dots} & \color{red}{(A_k,k_{n+1})} \end{array}$$This completes the induction. $\blacksquare$ Now partition $P$ into disjoint symmetric chains, and consider the set $S$ of elements with middle rank. Each symmetric chain contains exactly one of the elements of $S$, so we have $|S|$ symmetric chains in the partition. Also, no two elements of an antichain can appear in the same symmetric chain, so the size of an antichain is at most $|S|$, concluding the proof. Returning to the original problem, consider $\{0,1,\dots,7\}^3$ as the set of all possible triples of scores on the exercises, endowed with the product order. A simple computation tells us that there are $48$ triples with rank $10$, so by Dilworth's theorem, we can partition $P$ into $48$ chains. The result is now clear by the pigeonhole principle.