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 skilllevels of the teams, but Joy does not know that ordering. The teams are randomly put into a bracket andthey 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-bestteam 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 theskill levels of the teams, but Joy does not know that ordering. The teams are randomly put into abracket and they play out the tournament, with the better team always beating the worse team. Joyis then given the results of all 511 matches and must create a list of teams such that she can guaranteethat 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 toeither 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 thenconclude 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.