Maths Olympiad Prep

Library / Iranian Mathematical Olympiad /214 of 270

Iranian Mathematical Olympiad

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: 5→6→2→4→3→1⏞Permutation of Tests  ⟹  {1,2,3,4,6,9}⏞,Student 10: 3→4→1→6→5→2  ⟹  {1,2,3,5,7,10},Student 11: 5→6→2→4→1→3  ⟹  {1,2,3,4,6,11},Student 12: 1→2→3→5→6→4  ⟹  {1,2,4,5,8,12},Student 13: 3→4→1→6→2→5  ⟹  {1,2,3,5,7,13},Student 14: 1→2→3→5→4→6  ⟹  {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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

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