For a competition a school wants to nominate a team of $k$ students, where $k$ is a given positive integer. Each member of the team has to compete in the three disciplines juggling, singing and mental arithmetic. To qualify for the team, the $n \ge 2$ students of the school compete in qualifying competitions, determining a unique ranking in each of the three disciplines. The school now wants to nominate a team satisfying the following condition: $(*)$ If a student $X$ is not nominated for the team, there is a student $Y$ on the team who defeated $X$ in at least two disciplines. Determine all positive integers $n \ge 2$ such that for any combination of rankings, a team can be chosen to satisfy the condition $(*)$, when a) $k=2$, b) $k=3$.
Problem
Source: Germany 2023, Problem 3
Tags: combinatorics, combinatorics proposed, graph theory, Tournament, Tournament graphs
17.06.2023 10:29
. Note that $a)$ was the $11$th grade version, $b)$ the $12$th grade version, which was significantly harder. Out of all $25$ students in grade $12$, only six points were awarded, not one person scoring more than one.
08.03.2024 18:25
Question (2) is a terrific problem! The whole China IMO Team (including leaders and observers) failed to solve it for a long time. Finally, Chunji Wang solved this problem in Japan after IMO, when he was at Tokyo Disneyland. Now Let's see his splendid idea! I found it difficult to write out in English so here is a Chinese solution:
Attachments:
P3.pdf (323kb)
07.08.2024 03:51
I tried to translate Chunji Wang's solution. If there are any mistakes in the translation, let me know. (Question: Why should we take the student with $(a_{i_0},b_{n+1-i_0}$)? His juggling skill of $a_{i_0}$ is at least as strong as $a_{i_0+1}$. So shouldn't we take $(a_{i_0+1},b_{n-i_0})$ or am I missing something?)