Browse · MathNet
PrintKorean Mathematical Olympiad
South Korea counting and probability
Problem
Three schools , and participate in a chess tournament with five students from each school. Let be the list of the players from , , respectively. Let , , be the scores that schools , , make, respectively, when the tournament is over following the rules described below. Find the remainder of the number of possible triples when it is divided by .
1. Players from each school have matches in order from the first one, and if a player is once defeated then he (or she) is eliminated from the tournament. The first match of the tournament is between the players and .
2. When from school is defeated by from , if there are players left from the school other than , then have another match with a player from , if there is no player left in but there are players from then have a match with . The tournament is over when no player is left in two schools.
3. School adds points to its score when from wins a match.
1. Players from each school have matches in order from the first one, and if a player is once defeated then he (or she) is eliminated from the tournament. The first match of the tournament is between the players and .
2. When from school is defeated by from , if there are players left from the school other than , then have another match with a player from , if there is no player left in but there are players from then have a match with . The tournament is over when no player is left in two schools.
3. School adds points to its score when from wins a match.
Solution
(i) The triple can be made only when wins exactly times, and is only when wins games. The number of games that a player can win is strictly less than . Therefore, the number of possible triples is exactly the same as the number of different processes of the tournament.
(ii) Let be the number of possible triples when , , students from schools , , , respectively, participate in the tournament. Two possible results of the first match will give us the following: If there is no player left for a school, then we have a binomial number, and we have Moreover, we have . Since the number we are looking for is , let us consider the number : Therefore, the remainder of divided by is if is odd and if is even.
(iii) Let us calculate modulo . is odd and the answer is .
(ii) Let be the number of possible triples when , , students from schools , , , respectively, participate in the tournament. Two possible results of the first match will give us the following: If there is no player left for a school, then we have a binomial number, and we have Moreover, we have . Since the number we are looking for is , let us consider the number : Therefore, the remainder of divided by is if is odd and if is even.
(iii) Let us calculate modulo . is odd and the answer is .
Final answer
4
Techniques
Recursion, bijectionEnumeration with symmetryAlgebraic properties of binomial coefficients