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 100$. We are now going to pick teams of $5$ players, where the team's skill is determined by the sum of the 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? Note that each team must be unique in that a player cannot play for both teams

This problem, which I lovingly call the League of Legends Problem, is the initial question I had in mind when I asked here, however the answer I got was a brute force that didn't provide any additional insight.

With the pigeonhole principle, it is possible to show that $n\leq 101$, as you can pair up numbers that sum to $101$ combined with the guaranteed number that will have two players of that skill.

Purely heuristically though, it appears that the true bound should be much smaller, around $20-35$, but I am not sure what direction to go explicitly finding this.

As a bonus, it would be nice if we could find a way to generalize to other bounds of skills levels and team sizes

---

Edit: I'll add a proof that $n\leq 101$ here

Proof: Note that if at any point we find that we have $5$ skill levels that have $2$ or more players, then we are done

Suppose $n=101$, by the pigeonhole principle we know there must exist at least two players with the same skill level, take the two players and assign them to different teams. We have now reduced the problem to finding a $4$v$4$ with $n=99$.

If those $99$ players are distributed across distinct skill levels, then we can take $4$ pairs of numbers that add to $101$, ie $(1,100),(2,99),\ldots,(50,51)$ and put two pairs on each team. Since there are $99$ players and $50$ possible pairs, there must be at least $4$ pairs we can choose.

Finally, suppose we don't have $99$ distinct skills, but rather there are some possible repeated values. Well by our first point we know that if we can make $4$ pairs of repeated values then we are done since we already have $1$. This means at most we can have $3$ skills levels with at most $3$ players (if we had $4$ players on a skill level we could pair them up). However, even with this we $93$ distinct skill levels, which means we can still find $4$ pairs that add up to $101$.

Therefore we can always find a balance pair of teams. QED.

Answer 1

An upper bound can be constructed as follows :

Let $n$ denote the number of players.

First step : If there are two players of identical strength, put each one in one of the teams and iterate. If you get two teams of five players you are done.

You can therefore assume that you get at most $k\leq 4$
such pairs.

If $k\leq 3$, you have to form two balanced teams of $5-k\geq 2$ players chosen among $n-2k$ players, all of unequal strength (otherwise, you get two more players of equal strength).

If $k=4$, use three pairs of players of equal strength. There remain now two or three players of equal strength leading to a fourth pair of equal strength. Remove one or two of these players in order to get a set of at least $n-6-2=n-8$ players, all of different strength among which we have to chose two balanced teams of two players.

Up to adding at most $8$ we can therefore assume that we deal only with players of different strength (which we label by their strength) and we have to form balanced teams containing the same number $\alpha$ of players with $\alpha$ in $\lbrace 2,3,4,5\rbrace$. (For simplicity, I do not try to optimize everything.)

If $\alpha=2$, the sum $a+b$ of possible strengths of a pair $\lbrace a,b\rbrace$ is in the range $1+2=3,\ldots, 99+100=199$ containing $197$ different elements. Since $a+b=c+d$ implies either $\lbrace a,b\rbrace=\lbrace c,d\rbrace$ or $\lbrace a,b\rbrace\cap\lbrace c,d\rbrace=\emptyset$, we can use pigeonholes in order to get $n=21$ (since ${21\choose 2}>197$). If $\alpha=4$ we use this construction twice in order to get $n=25$.

If $\alpha=5$ we can get down to $\alpha=3$ after loosing $4$ elements.

The case $\alpha=3$ is slightly trickier since two balanced triplets might have a common element.

Given a triplet $a,b,c$, there are at most $\max((n-3)/2,6)$ more triples of the same sum which intersect $\lbrace a,b,c\rbrace$ and which have all pairwise intersections. Indeed, there are at most $(n-3)/2$ such triplets all containing the same element of $\lbrace a,b,c\rbrace$. Suppose now that there is a triplet $\lbrace a,x,y\rbrace$ (with $x,y$ different from $b,c$ and there are three triplets $\lbrace b,z_i,t_i\rbrace$. Then one of them has to be disjoint of $\lbrace,a,x,y\rbrace$. This gives rise to at most $6$ such triplets (and $6$ is generally much smaller than $(n-3)/2$).

This shows that if there are strictly more than $1+\max((n-3)/2,6)=\max((n-1)/2,7)$ triplets with the same sum, two triplets must be disjoint.

Possible sums for triplets are in the range $6,\ldots,98+99+100=297$ containing $292$ elements.

We can therefore apply the pigeonhole principle if ${3\choose n}>292\cdot (n-1)/2$ and $n\geq 15$.

This happens for $n=31$ leading to the upper bound $31+4=35$.

Answer 2

I am using integer linear programming to find the largest $n$ such that for some set of $n$ players with skill levels in $\{1,\dots,m\}$ there is no pair of evenly matched teams of size $k$. Add $1$ to get your smallest $n$ that guarantees a match.

Here are some results for smaller instances:

    m\k  1   2   3   4   5
     1   1   3   5   7   9
     2   2   4   6   8  10
     3   3   5   7   9  11
     4   4   5   7   9  11
     5   5   6   8  10  12
     6   6   6   8  10  12
     7   7   6   8  10  12
     8   8   7   9  11  13
     9   9   7   9  11  13
    10  10   7   9  11  13
    11  11   7   9  11  13
    12  12   7   9  11  13
    13  13   8   9  11  13
    14  14   8  10  12  14
    15  15   8  10  12  14
    16  16   8  10  12  
    17  17   8  10  12  
    18  18   8  10  12  
    19  19   9  10  12  
    20  20   9  10  12  
    21  21   9          
    22  22   9          
    23  23   9          
    24  24   9          
    25  25  10          
    26  26  10          
    27  27  10          
    28  28  10          
    29  29  10          
    30  30  10          

The $k=1$ column is obvious. The $k=2$ column matches OEIS A130234(m+1) initially but disagrees starting at $m=19$. For your desired $(m,k)=(100,5)$ case, the following multiset of $17$ skills yields a lower bound of $18$ for your smallest $n$: $$\{1,2,3,5,8,14,25,45,100,100,100,100,100,100,100,100,100\}$$

A logarithmic fit of the $k=5$ column suggests that $17$ is indeed the maximum value for $m=100$.