How many players are needed so that two evenly matched teams can be picked?

Question

We have a pool of $n$ players of a game, each player is assigned a "skill" which is an integer $1\leq s\leq 10$. We are now going to pick teams of $2$ players, where the team's skill is determined by the sum of the two individual players skills.

My question, what is the smallest value of $n$ such that we are guaranteed that there exists a pair of teams that have the same skill level?

Example: Let $P=[2,5,4,1,3,4]$. In this case we can select players $P_0,P_2$ on one team, and players $P_1, P_3$ on the other as $2+4=1+5$

But we can see that if $P=[1,1,3,1,8,9]$ there does not exist a solution, so $n>6$.

This looks like it would be an application of the pigeonhole principle, as there are $20$ possible team skill levels, but I am not sure how proceed to find the pigeons when teams are forced into being the same size and cannot share players.

My first thought was to say that if we select any $2$ players arbitrary, then there are $\binom{n-2}{2}$ possible opponents, and we want to find the first $n$ for which that is bigger than $20$, which is $7$ implying that $n=9$, but that seems like I'm reaching.

Any insight?

Answer 1

Claim: Here's a set of 7 people where we can't get a match: $\{ 1, 1, 1, 3, 4, 5, 9 \}$.
Just check that the pair sums are distinct, if they involve distinct people.
IE $1+3 = 1+3$, but the same 3 person is used.

Structure avoider: If any of these 3 scenarios occur, then we can find our match.

1. (at least) 2 with the same skill level, happening for (at least) 2 skill levels
   • Just pair distinct skill levels up.
2. (at least) 4 with the same skill level
   • Just pair them up.
3. (at least) 6 distinct skill values

   • Note that the naive pigeonhole requires 7 people as ${ 7 \choose 2 } = 21 > 19$ skill sums. Instead, we have the following complex argument to show that we can lower it to 6 people.

   • Arrange them in decreasing order with $10 \geq a_1 \geq a_2 \ldots \geq a_6 \geq 1$.

   • Consider the consecutive difference $a_i - a_{i+1}$.

     • If there are 3 consecutive differences that are the same, then we can find our distinct pairs to form a match: $a_i - a_j = a_k - a_l \Rightarrow a_i + a_l = a_k + a_j$
     • When does 2 consecutive difference being the same not lead to a match? Thus, for a given value, at most 2 differences can take on the value, and these differences have to be next to each other.
     • Since $10-1 = 1 + 1 + 2 + 2 + 3$, this is the only possibility for the set of differences.

   • By symmetry, and since equal differences have to be next to each other, the only arrangements that we need to consider are

     • $(1, 1, 2, 2, 3)$. However the first 2 1's can pair against the second 2, meaning that $a_1 -a _3 = 2 = a_4 - a_5$.
     • $(1, 1, 3, 2, 2)$. However the first 2 1's can pair against the second 2, meaning that $a_1 - a_3 = 2 = a_4 - a_5$.
     • $ ( 3, 1, 1, 2, 2)$. However, the first 3 can pair against the adjacent 1 and 2, meaning that $a_1 - a_2 = 3 = a_3 - a_5$.

Corollary: With 8 people, we can find a match.
Basically, check that we must be in one of these 3 scenarios, hence we are done.

Corollary: In any counter example of 7 people, we must have 3 with the same skill level and 5 distinct skill levels.
Basically, check that any other setup results in one of these 3 scenarios.