62nd Ukrainian National Mathematical Olympiad

Question

A country held a one-round tennis tournament. Participants received 1 point for winning the match, and 0 points for losing. There are no draws in tennis. At the end of the tournament, Oleksii saw the number of points scored by each participant, as well as the schedule of all the matches in the tournament, which showed the pairs of players, but not the winners. He chooses a match in some particular order (however he wants) and tries to guess the winner, after which he is told if he is correct. Prove that Oleksii can act in such a way that he is guaranteed to guess the winners of more than half of the matches. (Oleksii Masalitin)

Accepted Answer

Let's choose player A, who has the lowest number of points. He has at least as many defeats as wins, so by indicating a defeat in each his game, Oleksii will guess at least half of the results of player A. Then Oleksii subtracts the results of player A from the results of each participant and again selects player B with the lowest number of points and repeats this procedure. If the corresponding player has an odd number of games, then Oleksii will guess more than half of the results of this player, if the number of games is even, then at least half, but then he guessed more than half for A and B together, since the number of games for them was of different parity. Let's continue to choose the player with the lowest number of points. In total, he will guess more than half of all outcomes.