Consider a ping-pong match between two teams, each consisting of $1000$ players. Each player played against each player of the other team exactly once (there are no draws in ping-pong). Prove that there exist ten players, all from the same team, such that every member of the other team has lost his game against at least one of those ten players.
Problem
Source: Baltic Way 1998
Tags: combinatorics proposed, combinatorics
A-Thought-Of-God
28.04.2021 08:35
Bump. Any solutions?
phoenixfire
10.08.2021 11:06
Claim: In a match between two teams (of any size), there exists a player, in some team, such that this player won the games he played against at least half of the members of the other. Call such players BoB.
Assume for the sake of contradiction that such a player cannot exist. Let the two teams be $A$ and $B$ with sizes $a$ and $b$ respectively. Now by our assumption, we get that in total each team has won less than $\frac{a \cdot b}{2}$ games or less than $a \cdot b$ games have been played in total as each game has (exactly) one winner. But in all, there are $a \cdot b$ games played. This implies a contradiction.
Process 1: Find a BoB and for every BoB that we find, we discard every other player (from the other team) that played against BoB but lost. Apply Process 1 to the two teams. Repeat Process 1 until there are no players left in one of the teams. This means that all BoB's of the other team form the group (which we now call $G$) with the required property. Each time we selected a BoB, the size of the other team was reduced at least by half. And since initially the size was a number less than $2^{10}$, we cannot apply Process 1 more than ten times. Hence $|G| \leq 10$. And if $|G| < 10$ we can add any other player.