In the country of Sugarland, there are $13$ students in the IMO team selection camp. $6$ team selection tests were taken and the results have came 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 $6$ 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 $13$ students have a chance of being a team member? Proposed by Morteza Saghafian
Problem
Source: Iranian TST 2017, first exam, day1, problem 2
Tags: combinatorics, Iran, Iranian TST
05.04.2017 18:11
Hum maybe i miss something but if a student has $0$ il all the tests. He has no chance for being a team member?
05.04.2017 19:26
mamouaz1 wrote: Hum maybe i miss something but if a student has $0$ il all the tests. He has no chance for being a team member? I think it asks if there exists a configuration of rankings so that for every student, there is a permutation of the tests in which that student qualifies. Edit: I live in Sugar Land
05.04.2017 20:45
rafayaashary1 wrote: I live in Sugar Land That's pretty intresting
06.04.2017 05:06
06.04.2017 11:45
07.04.2017 06:38
What is the maximum number of students there can be so that there is still a chance of being a team member?
07.04.2017 10:32
MathPanda1 wrote: What is the maximum number of students there can be so that there is still a chance of being a team member? I think there was an example for $14$ students. But don't have an idea about the maximum number.
26.04.2017 08:45
TEST: 1 2 3 4 5 6 A A A A A A B B B B B B C C C D D D D D D C C C E E F F G G H I J K L M Satisfies the conditions
08.05.2017 21:52
MathPanda1 wrote: What is the maximum number of students there can be so that there is still a chance of being a team member? Here is an example for $14$ students: \begin{tabular}{l*{5}{c}r} Test & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline 1st place& A & A & A & A & A & A \\ 2nd place & B & B & B & B & B & B \\ 3rd place & C & C & D & D & E & E \\ 4th place& F & G & G & H & H & F \\ 5th place& I & J & K & L & M & N \\ \end{tabular} For example, $I$ can get into the team with the order $(4,3,5,2,6,1)\rightarrow(A,B,E,C,F,I)$.
25.02.2019 00:33
"That's an awfully tricky yes-no question to put on a TST..." You should know about pre-history of a problem: https://artofproblemsolving.com/community/c6h46293p292638
01.07.2021 00:28
$\textbf{Yes.}$ This is in fact possible, with the following setup, where each column represents the top 6 scorers on each problem, and the contestants are numbered $01,02,\ldots,13$. 01 01 01 01 01 01 02 02 02 02 02 02 03 03 03 03 03 03 04 04 04 04 04 04 05 05 06 06 07 07 08 09 10 11 12 13
30.12.2022 17:25
It is indeed possible. Number the students 01 to 13 and suppose that the top 6 on each problem is as follows 01 01 01 01 01 01 02 02 02 02 02 02 03 03 03 03 03 03 04 04 04 04 04 04 05 05 06 06 07 07 08 09 10 11 12 13 And assign the rest of the rankings arbitrarily. Then in any IMO team, students 01 through 04 must be included. Students 05 and 09 can be included through the permutation 654312, and something similar can be sued to include any of the other students. $\blacksquare$
10.03.2023 13:16
\begin{tabular}{l*{5}{c}r} Test & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline 1st place& 1 & 1 & 1 & 2 & 2 & 2 \\ 2nd place & 3 & 4 & 5 & 3 & 4 & 5 \\ 3rd place & 6 & 7 & 8 & 8 & 6 & 7 \\ 4th place& 9 & 10 & 11 & 12 & 13 & 14 \\ \end{tabular} is a shorter example for $14$. You work backwards to verify that this works, notice that showing any $4$th place student can get into the team is sufficient. Let me demonstrate an example for any student in $5$th place say $11$: To get $11$ you must get students $8,5,1$ into the team first, you have to get $8$ from Test $4$ and $5$ from Test $6$ which are always different by construction. And you should also take student $3$ from Test $1$ before you start taking $8$, notice that Test $1$, $4$, $6$, $3$ are all different again. So you first take the left out tests, $2$, $5$ in this case, then take $1$, $4$, $6$, $3$ in order.
05.12.2023 20:45
1 2 3 5 8 1 2 3 6 9 1 2 3 7 A 1 2 4 5 B 1 2 4 6 C 1 2 4 7 D $\blacksquare$
07.01.2024 02:50
Quite difficult but very satisfying to solve. Consider the construction $$\begin{tabular}{c|c|c|c|c|c|c} & Problem 1 & Problem 2 & Problem 3 & Problem 4 & Problem 5 & Problem 6 \\ \hline Student 1 & 1 & 1 & & 2 & & \\\hline Student 2 & 2 & & 1 & 1 & & \\\hline Student 3 & & 2 & & & 1 & \\\hline Student 4 & & & 2 & & & 1 \\\hline Student 5 & 3 & 3 & & & & \\\hline Student 6 & 4 & & & & & \\\hline Student 7 & & 4 & & & & \\\hline Student 8 & & & 3 & 3 & & \\\hline Student 9 & & & 4 & & & \\\hline Student 10 & & & & 4 & & \\\hline Student 11 & & & & & 2 & 2 \\\hline Student 12 & & & & & 3 & \\\hline Student 13 & & & & & & 3 \end{tabular}$$ where the columns denote problems, rows denote students, and the entry in $(r, c)$ corresponds to the rank of student $r$ on problem $c$. The places left blank can be chosen arbitrarily. Now, observe that: Students $1, 2, 3, 4$ can get on the team as if the problem they are ranked first on is chosen first; Student $5$ can get on the team if the problems are chosen in the order $3, 4, 5, 1$; Student $6$ can get on the team if the problems are chosen in the order $3, 4, 5, 2, 1$; Student $7$ can get on the team if the problems are chosen in the order $3, 4, 5, 1, 2$; Students $8$ through $10$ can get on the team by symmetry (with $3, 4$ replaced with $2, 1$ and so on). Student $11$ can get on the team if the problems are chosen in the order $4, 1, 2, 3, 5$; Student $12$ can get on the team if the problems are chosen in the order $4, 1, 2, 3, 6, 5$; Student $13$ can get on the team if the problems are chosen in the order $4, 1, 2, 3, 5, 6$. So all $13$ students can get on the team, which concludes the proof. Remark: The underlying idea behind the construction was to use the top $2 \times 4$ square to easily be able to eliminate top ranks; then, for each pair, we would be able to uplift three students who were ranked lower, which suffices for the $13$ students.
07.01.2024 08:21
Very tricky question. We can $choose$ This $ configuration$ satisfies 1 2 5 9 1 2 6 10 1 3 7 11 1 3 5 12 1 4 6 13 1 4 7 8
19.09.2024 14:53
What a great problem! Label the students with the numbers the letters $A$ through $M$. Motivation: Notice that the following 'pyramid' structure is very natural to consider. If the tests were chosen in numerical order, then $A$ would be admitted first, in the second test $B$ would be admitted as $A$ has already been chosen, and so on until $F$ is admitted. \begin{tabular}{l*{5}{c}r} Test & 1 & 2 & 3 & 4 & 5& 6 \\ \hline 1st& A & A& A & A& A& A\\ 2nd& {} & B & B & B & B& B \\ 3rd & {} & {} & C & C & C & C \\ 4th & {} & {} & {} & D & D & D \\ 5th & {} & {} & {} & {} & E & E \\ 6th & {} & {} & {} & {} & {} & F\\ \end{tabular}This is not necessary but it is sufficient in that every student that appears at the bottom of a pyramid (size $1$ to $6$) in some permutation can be possibly chosen. This idea leads naturally to the following construction. Construction: \begin{tabular}{l*{5}{c}r} Test & 1 & 2 & 3 & 4 & 5& 6 \\ \hline 1st& A & A& A & A& A& A\\ 2nd& B & B & B & B & B& B \\ 3rd & C & C & C & C & C & C \\ 4th & G & G & G & D & D & D \\ 5th & H & H & H & E & E & E \\ 6th & I & J & K & L & M & F\\ \end{tabular}
06.11.2024 20:58
Great problem! (i love these yes no problems, specially this kind) Constriction: \begin{tabular}{l*{5}{c}r} Test & 1 & 2 & 3 & 4 & 5& 6 \\ \hline 1st& A & A& A & A& A& A\\ 2nd& B & B & B & B & B& B \\ 3rd & C & C & C & C & C & C \\ 4th & D & D & D & D & D & D \\ 5th & E & E & F & F & G & G \\ 6th & M & L & K & J & I & H\\ \end{tabular}It is not difficult to verify how this works.
10.01.2025 18:30
Yes, consider \[\begin{array}{|c|c|c|c|c|c|} \hline 1 & 2 & 3 & 4 & 5 & 6 \\ \hline A & A & A & A & A & A \\ \hline B & B & B & B & B & B \\ \hline C & C & C & C & C & C \\ \hline D & D & D & D & D & D \\ \hline E & E & F & F & G & G \\ \hline H & I & J & K & L & M \\ \hline \end{array}\]