HMMT 十一月 2012 · THM 赛 · 第 9 题

HMMT November 2012 — THM Round — Problem 9

[ 6 ] 64 people are in a single elimination rock-paper-scissors tournament, which 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 P is it possible that P wins the first four rounds that he plays? (A 6-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 two 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, the 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 players. 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-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 P is it possible that P wins the 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 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, the 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 players. After the sixth round, 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 themselves constitute a bracket, is always won by the person with the highest skill level. Therefore, a person wins her first four rounds if and only if she has the highest skill level among the people in her 16-person sub-bracket. This is possible for all but the people with the 16 − 1 = 15 lowest skill levels, so our answer is 64 − 15 = 49.