HMMT 二月 2013 · COMB 赛 · 第 7 题
HMMT February 2013 — COMB Round — Problem 7
题目详情
英文原题
A single-elimination ping-pong tournament has 22013players, seeded in order of ability. If the player with seed xplays the player with seed y, then it is possible for xto win if and only if x≤y+ 3. For how many players Pit is possible for Pto win? (In each round of a single elimination tournament, the remaining players are randomly paired up; each player plays against the other player in his pair, with the winner from each pair progressing to the next round and the loser eliminated. This i s repeated until there is only one player remaining.)
解析
英文解析
- A single-elimination ping-pong tournament has 2 players, seeded in order of ability. If the playerwith seed x plays the player with seed y , then it is possible for x to win if and only if x ≤ y + 3. Forhow many players P it is possible for P to win? (In each round of a single elimination tournament, theremaining players are randomly paired up; each player plays against the other player in his pair, with the winner from each pair progressing to the next round and the loser eliminated. This is repeateduntil there is only one player remaining.)
Answer: 6038 We calculate the highest seed n that can win. Below, we say that a player xvicariously defeats a player y if x defeats y directly or indirectly through some chain (i.e. x defeats x ,
who defeated x , . . . , who defeated x , who defeated y for some players x , . . . , x ).1
2 n 1 n
We first consider the highest seeds that are capable of making the semifinals. The eventual winnermust be able to beat two of these players and thus must be able to beat the second best player in thesemifinals. The seed of the player who vicariously beats the 1-seed is maximized if 1 loses to 4 in the first round, 4 to 7 in the second round, etc. Therefore 3 · 2011 + 1 = 6034 is the maximum value ofthe highest seed in the semifinals. If 1, and 2 are in different quarters of the draw, then by a similarargument 6035 is the largest possible value of the second best player in the semis, and thus 6038 isthe highest that can win. If 1 and 2 are in the same quarter, then in one round the highest remainingseed will not be able to go up by 3, when the player who has vicariously beaten 1 plays the player whovicariously beat 2, so 3 · 2011 − 1 = 6032 is the highest player the semifinalist from that quarter could be. But then the eventual winner still must be seeded at most 6 above this player, and thus 6038 isstill the upper bound.
Therefore 6038 is the worst seed that could possibly win, and can do so if 6034, 6035, 6036, 6038 allmake the semis, which is possible (it is not difficult to construct such a tournament). Then, note that any player x with a lower seed can also win for some tournament – in particular, it suffices to take
Combinatorics Testthe tournament where it is possible for player 6038 to win and switch the positions of 6038 and x .
Consequently, there are 6038 players for whom it is possible to win under some tournament.