HMMT 十一月 2020 · 冲刺赛 · 第 12 题

HMMT November 2020 — Guts Round — Problem 12

[8] In a single-elimination tournament consisting of 2 = 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? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HMMO 2020, November 14–21, 2020 — GUTS ROUND Organization Team Team ID#

解析

[8] In a single-elimination tournament consisting of 2 = 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? Proposed by: Cory Hixson Answer: 45 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 ≤ k ≤ 8, we can then conclude that there are 1 + 2 + · · · + 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.