Library / /40 of 62

, 2020

Combinatorics Difficulty 5.7 AIME, harder Prove it United States

Problem:

In a single-elimination tournament consisting of $2^{9}=512$ teams, there is a strict ordering on the skill levels of the teams, but Joy does not know that ordering. The teams are randomly put into a bracket and they play out the tournament, with the better team always beating the worse team. Joy is then given the results of all 511 matches and must create a list of teams such that she can guarantee that the third-best team is on the list. What is the minimum possible length of Joy's list?

Solution

Solution:

The best team must win the tournament. The second-best team has to be one of the 9 teams that the first best team beat; call these teams marginal. The third best team must have lost to either the best or the second-best team, so it must either be marginal or have lost to a marginal team. Since there is exactly one marginal team that won $k$ games for each integer $0 \leq k \leq 8$ , we can then conclude that there are $1+2+\cdots+9=45$ teams that are either marginal or lost to a marginal team. Moreover, it is not hard to construct a scenario in which the third-best team is any of these 45 teams, so we cannot do better.

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.