Browse · MathNet
Print63rd Czech and Slovak Mathematical Olympiad
Czech Republic counting and probability
Problem
Six teams will take part in a volleyball tournament. Each pair of the teams should play one match. All the matches will be realized in five rounds, each involving three simultaneous matches on the courts numbered 1, 2 and 3. Find the number of all possible draws for such a tournament. By a draw we mean a table in which an unordered pair of teams is written on the field , where and , if these two teams will meet each other in the -th round on the court . You are allowed to write down the resulting number as a product of prime factors (instead of writing its decimal expansion).
Solution
We postpone the question of permutations of the five rounds and the three courts to the end of our solution. Denoting first the teams by numbers (in a fixed way), we rearrange the five rounds of any satisfactory draw by means of the following numbering: Let and be the rounds with matches of the pairs of teams and , respectively. If a pair plays in the round and if a pair plays in the round , then are two distinct numbers from (otherwise the third pairs in the rounds and are identical). Let and denote the rounds with pairs , and respectively, where . Up to this moment, we have fixed an uncompleted draw 1: (1, 2), (3, a), 2: (1, 3), (2, b), 3: (1, a), 4: (1, b), 5: (1, c), which can be extended to a the complete draw in the only one way: 1: (1, 2), (3, a), (b, c), 2: (1, 3), (2, b), (a, c), 3: (1, a), (2, c), (3, b), 4: (1, b), (2, a), (3, c), 5: (1, c), (2, 3), (a, b). Since is any permutation of , the total number of the complete draws (written as above) is . Taking in account the number of the possible permutations of the five rounds and the number of possible permutations of the three courts, we conclude that the requested number of all draws is equal to
---
Alternative solution.
Let us denote the six teams by numbers and construct first an "unordered" draw in which the rounds will be "numbered" by the opponents of the team — see the following table in which the other opponents of the team are denoted as : 1: (1, 2), 2: (1, 3), (2, a), 3: (1, 4), (2, b), 4: (1, 5), (2, c), 5: (1, 6), (2, d). Note that is a permutation of the quadruple and that the following two restrictions are evident: The two-element sets , , , are pairwise distinct. It is clear that under these two conditions, the third pairs for the rounds - are uniquely determined, as well as the remaining two pairs for the round . Consequently, we have to calculate the number of permutations of the quadruple which satisfy the two above stated conditions. Using the inclusion-exclusion principle we conclude that the first condition is fulfilled by exactly nine permutations: Moreover, exactly three of them do not satisfy the second condition, namely the permutations , and . Thus the total number of the satisfactory permutations equals . We have proved that there are six "unordered" draws in the above specified sense. Combining this result with the idea of permuting the rounds and the courts, we conclude that the requested number of the draws is equal to
---
Alternative solution.
Let us denote the six teams by numbers and construct first an "unordered" draw in which the rounds will be "numbered" by the opponents of the team — see the following table in which the other opponents of the team are denoted as : 1: (1, 2), 2: (1, 3), (2, a), 3: (1, 4), (2, b), 4: (1, 5), (2, c), 5: (1, 6), (2, d). Note that is a permutation of the quadruple and that the following two restrictions are evident: The two-element sets , , , are pairwise distinct. It is clear that under these two conditions, the third pairs for the rounds - are uniquely determined, as well as the remaining two pairs for the round . Consequently, we have to calculate the number of permutations of the quadruple which satisfy the two above stated conditions. Using the inclusion-exclusion principle we conclude that the first condition is fulfilled by exactly nine permutations: Moreover, exactly three of them do not satisfy the second condition, namely the permutations , and . Thus the total number of the satisfactory permutations equals . We have proved that there are six "unordered" draws in the above specified sense. Combining this result with the idea of permuting the rounds and the courts, we conclude that the requested number of the draws is equal to
Final answer
5598720
Techniques
Inclusion-exclusionCounting two waysMatchings, Marriage Lemma, Tutte's theorem