One hundred tennis players took part in a tournament where they played with each other exactly one game, with no draws. At the end of the tournament a table (ranking) is formed depending on the number of victories. It is known that one tennis player finished the tournament on $k$-th place and is the only one with that number of victories, and he has beaten every tennis player who is placed above him in the table and lost to anyone ranked weaker than him on the table. Find the smallest value of $k$.
Problem
Source: Serbia JBMO TST 2020 P4
Tags: combinatorics
Tesla.CY
07.09.2020 13:50
any ideas?
Marinchoo
07.09.2020 23:18
We label the players as $A_{1}, A_{2}, A_{3},\cdots, A_{100}$ depending on the leaderboard results($A_{1}$ got the most points and $A_{100}$ has the least points). Now lets say that we look at an example for $k$. If we look at the group ${A_{k+1}, A_{k+2},\cdots, A_{100}}$: They have played exactly $\frac{(100-k)(99-k)}{2}$ mathes. That means that the sum of the results of these people is at least $(100-k) + \frac{(100-k)(99-k)}{2}$, because $A_{k}$ lost to all people of this group. Now we know that $A_{k}$ has more points than any of the people of this group, so we derive the inequality: $(k-1)(100-k) > (100-k)+\frac{(100-k)(99-k)}{2}$. We know its true, because $A_{k}$ has $k-1$ points and we know that $A_{k}$ has more points than any player of ${A_{k+1}, A_{k+2},\cdots, A_{100}}$, so we multiply by $100-k$. I really hope the inequality deriavtion is clear enough. Now we solve the inequality: $(k-1)(100-k) > (100-k)+\frac{(100-k)(99-k)}{2} \implies (k-1) > 1 +frac{99-k}{2} \implies 2k-2 > 2 + 99 - k \implies 3k > 103$, so $k>34$. We get a setup for $k=35$: We look at the graph with vertices $A_{36},\cdots , A_{100}$. By induction we can see that we can construct a directed graph( the direction decides the winner of the match) with $2n+1$ vertices and n directed edges coming out of each vertex. We construct the cycles $A_{36},A_{37},\cdots,A_{100}; A_{36},A_{38},A_{40}\cdots; A_{36}, A_{39}, A_{42}$and so on. If we have a natural number $r>1$, for which $r\vert 65$, then we have more than one (exactly $\frac{65}{r}$) cycles $A_{36},A_{36+r},A_{36+2r},\cdots$, but also $A_{37},A_{37+r},A_{37+2r}\cdots$ and so on to the cycle $A_{35},A_{35+r},A_{35+2r},A_{35+3r}$. Now every cycle is directed (consists of directed edges) and either $(A_{i}, A_{j})$ or $(A_{j}, A_{i})$ is an edge. Inductively we have that every vertex has $32$ edges coming out of it. As $A_{35}$ has lost to all $A_{36},\cdots A_{100}$. So every $A_{36},\cdots A_{100}$ has $32+1$ points and $A_{35}$ has $34$ points. Now if we set that every $A_{i}$ for any $0<i<35$ has won every match to all $A_{36},\cdots A_{100}$, so every $A_{1},A_{2},\cdots,A_{34}$ has won at least $6$5 matches (all the matches between two of $A_{1},A_{2},\cdots,A_{34}$ we set the winner at random: for example only we set $A_{i}$ to have beaten $A_{j}$ if $i<j$ for $0<i<j<35$), so $A_{35}$ is in the $35$-th spot and we are done!
I hope you like this solution.
Tesla.CY
09.09.2020 12:27
Well done...nice solution!