AoPS - Problem

Source: China TST 1996, problem 4

Tags: combinatorics unsolved, combinatorics

orl

17.05.2005 21:20

3 countries $A, B, C$ participate in a competition where each country has 9 representatives. The rules are as follows: every round of competition is between 1 competitor each from 2 countries. The winner plays in the next round, while the loser is knocked out. The remaining country will then send a representative to take on the winner of the previous round. The competition begins with $A$ and $B$ sending a competitor each. If all competitors from one country have been knocked out, the competition continues between the remaining 2 countries until another country is knocked out. The remaining team is the champion. I. At least how many games does the champion team win? II. If the champion team won 11 matches, at least how many matches were played?

Suppose $A$ is the champion. $A$ plays $a$ times and loses $b$ times ($b\le8$). $A$ does not play when: (1) the first game starts with $B$ and $C$; (2) $A$ loses. So the number of games $A$ does not play is $1+b$ or $b$. The total number of games is equal to the total number of loses, which is $b+9+9=b+18$. Thus we get $1+b+a=b+18$ or $b+a=b+18$, whence $a=18$ or $a=17$. I. The number of wins for $A$ is $a-b\ge17-8=9$. Construction: $B$ and $C$ starts the game. $B,C,A$ loses repeatedly in this order. II. We have $a-b=11$, so $b=a-11=6$ or $7$. Thus the number of games is $b+18\ge24$. Construction: $B$ and $C$ starts the game. $B$ beats 6 representatives of $A$ and 7 representatives of $C$ in the first 13 games. Then $A$ beats all 11 remaining representatives from $B$ and $C$ in the last 11 games.