HMMT 十一月 2012 · THM 赛 · 第 9 题
HMMT November 2012 — THM Round — Problem 9
题目详情
英文原题
[6] 64 people are in a single elimination rock-paper-scissors tournament, whi ch consists of a 6-round
knockout bracket. Each person has a different rock-paper-scissors skill level, and in any game, the
person with the higher skill level will always win. For how many players Pis it possible that Pwins
the first four rounds that he plays?
(A6-round knockout bracket is a tournament which works as follows:
(a) In the first round, all 64 competitors are paired into 32 groups, and the tw o people in each group
play each other. The winners advance to the second round, and the losers are eliminated.
(b) In the second round, the remaining 32 players are paired into 16 groups. Again, t he winner of
each group proceeds to the next round, while the loser is eliminated.
(c) Each round proceeds in a similar way, eliminating half of the remaining player s. After the sixth
round, only one player will not have been eliminated. That player is declared the champion. )
解析
英文解析
- [ 6 ] 64 people are in a single elimination rock-paper-scissors tournament, which consists of a 6-roundknockout bracket. Each person has a different rock-paper-scissors skill level, and in any game, theperson with the higher skill level will always win. For how many players P is it possible that P winsthe first four rounds that he plays?
(A 6-round knockout bracket is a tournament which works as follows:
Theme Round
(a) In the first round, all 64 competitors are paired into 32 groups, and the two people in each groupplay each other. The winners advance to the second round, and the losers are eliminated.
(b) In the second round, the remaining 32 players are paired into 16 groups. Again, the winner ofeach group proceeds to the next round, while the loser is eliminated.
(c) Each round proceeds in a similar way, eliminating half of the remaining players. After the sixthround, only one player will not have been eliminated. That player is declared the champion.)
Answer: 49 Note that a sub-bracket, that is, a subset of games of the tournament that themselvesconstitute a bracket, is always won by the person with the highest skill level. Therefore, a person winsher first four rounds if and only if she has the highest skill level among the people in her 16-personsub-bracket. This is possible for all but the people with the 16 − 1 = 15 lowest skill levels, so ouranswer is 64 − 15 = 49.