Browse · MathNet
Print55rd Ukrainian National Mathematical Olympiad - Fourth Round
Ukraine counting and probability
Problem
At the tennis tournament in one circle attended the 8 girls (i.e. every tennis player has played with each other exactly once, draws in tennis does not happen). Oksana took the second place recruited points and there is no other participant with the same number of points. What is the maximum number of games could lose Olesya who won in this tournament?
Solution
Suppose that Olesya lost 2 games. Then she scored 5 points. Oksana could not score 4 points, because then all together all teams had supplied the maximum wins. But in total we have games, a contradiction. Similarly Oksana could not score 3 or less points, or Olesya lose 3 more games. Thus, only Olesya could lose up to 1 game. This option is possible, as evidenced by the table (Fig. 28) example.
Fig. 28
| M | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | p |
|---|---|---|---|---|---|---|---|---|---|
| 1 | X | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 6 |
| 2 | 1 | X | 1 | 0 | 1 | 0 | 1 | 0 | 4 |
| 3 | 0 | 0 | X | 1 | 0 | 1 | 0 | 1 | 3 |
| 4 | 0 | 1 | 0 | X | 1 | 0 | 1 | 0 | 3 |
| 5 | 0 | 0 | 1 | 0 | X | 1 | 0 | 1 | 3 |
| 6 | 0 | 1 | 0 | 1 | 0 | X | 1 | 0 | 3 |
| 7 | 0 | 0 | 1 | 0 | 1 | 0 | X | 1 | 3 |
| 8 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | X | 3 |
Final answer
1
Techniques
Counting two waysColoring schemes, extremal arguments