Browse · MathNet
PrintJapan 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 .
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