Maths Olympiad Prep

Library / /237 of 299

Combinatorics Difficulty 7.2 National Olympiad, round 2 Prove it Iran

In the country of Sugarland, there are 1313 students in the IMO team selection camp. 66 team selection tests were taken and the results have come out. Assume that no students have the same score on the same test. To select the IMO team, the national committee of math Olympiad have decided to choose a permutation of these 66 tests and starting from the first test, the person with the highest score between the remaining students will become a member of the team. The committee is having a session to choose the permutation.
Is it possible that all 1313 students have a chance of being a team member?

Solution

The answer of the problem is yes.
Although the statement is discussed on 1313 students, here is an example for 1414 students, all having a chance of being a team member. (students are labelled by 1,2,,141, 2, \ldots, 14.)

Test Rank#1#2#3#4#5#6
#1111111
#2222222
#3334455
#4676878
#591011121314
.....................

Note that the fifth person in each test can become a team member, only if all the other four persons above already have been chosen as a team member. Therefore, to prove that the example works, it suffices to show that the fifth person in each test can become a team member. For each of the students 9,10,11,12,13,149, 10, 11, 12, 13, 14, consider these permutations of tests

Student 9: 562431Permutation of Tests    {1,2,3,4,6,9},Student 10: 341652    {1,2,3,5,7,10},Student 11: 562413    {1,2,3,4,6,11},Student 12: 123564    {1,2,4,5,8,12},Student 13: 341625    {1,2,3,5,7,13},Student 14: 123546    {1,2,4,5,8,14}. \begin{array}{l} \text{Student 9: } \overbrace{5 \to 6 \to 2 \to 4 \to 3 \to 1}^{\text{Permutation of Tests}} \implies \overbrace{\{1, 2, 3, 4, 6, 9\}}, \\ \text{Student 10: } 3 \to 4 \to 1 \to 6 \to 5 \to 2 \implies \{1, 2, 3, 5, 7, 10\}, \\ \text{Student 11: } 5 \to 6 \to 2 \to 4 \to 1 \to 3 \implies \{1, 2, 3, 4, 6, 11\}, \\ \text{Student 12: } 1 \to 2 \to 3 \to 5 \to 6 \to 4 \implies \{1, 2, 4, 5, 8, 12\}, \\ \text{Student 13: } 3 \to 4 \to 1 \to 6 \to 2 \to 5 \implies \{1, 2, 3, 5, 7, 13\}, \\ \text{Student 14: } 1 \to 2 \to 3 \to 5 \to 4 \to 6 \implies \{1, 2, 4, 5, 8, 14\}. \end{array}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.