Maths Olympiad Prep

Library / HMMT November /526 of 672

HMMT November, 2012

Combinatorics Difficulty 5.3 AIME, harder Prove it United States

Problem:

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 PP is it possible that PP 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.)

Solution

Solution:

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=1516-1=15 lowest skill levels, so our answer is 64−15=4964-15=49.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.