Maths Olympiad Prep

Library / /585 of 740

, 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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

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