Skip to main content
OlympiadHQ

Browse · MathNet

Print

Japan Junior Mathematical Olympiad

Japan counting and probability

Problem

In a certain fencing competition there were participants. Each participant had one match each with other participants. The number of winning matches of the participants turned out to be all different. Assume that there was no draw in all of the matches. How many distinct winner-loser combinations were possible for this competition?
Solution
By assumption there exists exactly person who won matches for , so let be the person who won matches for each (). Then we can see that

won all matches, so, he won over . lost to , but won over . lost to , but won over . lost to , but won over . lost to , but won over . lost to .

In this way, we can see that if we can determine who won how many games, then we can tabulate all the win-loss combinations at the tournament. Hence the number of possible combinations is .
Final answer
720

Techniques

Recursion, bijectionCounting two ways