Two football teams

Question

Twenty two football players have agreed to split every week into two teams and play a match against each other. Every week, teams will be chosen differently, 11 players in each team, and they will play until each of the (231) possible pairs, A and B, of players among the 22 players will have played at least once against each other.

At least how many matches will be necessary before this happens?

More generally, if $2n$ players are to split into two teams of $n$ players each in order play a certain game against each other, how many matches are necessary before everyone among the $2n$ players has played against every other player at least once?

Answer 1

Here is one neat way of organising the matches, which is optimal.

First I'll describe a general method that works for any number 2n that is

a power of 2, say 2n=2^k.

Method:

Number the players in binary from 0 to 2n-1. These are all k-bit binary numbers. Then arrange k matches, where the teams in the k-th match are determined by the k-th bit in the players' numbers.

This works because:

Any two players have different numbers, and so their numbers will differ in at least one bit position. In those matches they will be on opposite teams. Note also that in every match both teams contain exactly n players as required.

By leaving out some of the players in the matches you can use same team arrangement with any smaller number of players.

To reduce n, leave out any pair of players with complementary numbers (i.e. numbers that differ in every bit). These players are on opposite teams in every match, so removing them keeps the teams of equal size in all matches.

So for $2n$ players this method uses k matches where

k=ceiling(lg(2n))

Here is the n=11 case explicitly.

22<2^5 so we use 5-bit numbers resulting in 5 matches. The table below shows this. The players a-v are numbered from 5 to 26 (shown vertically in binary) because I have removed 5 pairs from the 32 players that this match schedule could accomodate (0-4 and their complements 27-31).

.....abcdefghijklmnopqrstuv.....
00000000000000001111111111111111  abcdefghijk/lmnopqrstuv
00000000111111110000000011111111  abclmnopqrs/tuvdefghijk
00001111000011110000111100001111  defglmnotuv/abchijkpqrs
00110011001100110011001100110011  adehilmpqtu/bcfgjknorsv
01010101010101010101010101010101  bdfhjlnprtv/acegikmoqsu

Now let's prove this is optimal, using the idea given by loopy_walt in the comments below, which is basically the reverse of the steps that were used to construct the teams:

Suppose we have a solution using k matches. Assign each player a k-bit binary number, where the k-th bit is 0 or 1 depending on whether the player is in the first or the second team in the k-th match.
Since this is a solution, every pair of players will play on opposing teams at least once. Therefore, every player will have a number assigned to them that is different from every other number. So they have 2n unique k-bit binary numbers, which is only possible when 2n<=2^k, or equivalently k>=lg(2n). The least possible k is therefore k=ceiling(lg(2n)), which the previously described method achieves.

Answer 2

Notation: let $p_i$ be the player number i and n the size of a team.

First approach, very inefficient:

Let's start for n = 2
Then two matches are necessary.
For example ($p_1$ and $p_2$) against ($p_3$ and $p_4$)
Followed by ($p_1$ and $p_3$) against ($p_2$ and $p_4$)
So now consider n = 3
We have two new players, $p_5$ and $p_6$.
Consider the subteam $t_1$ consisting of $p_1$ and $p_2$ and the sub-team $t_2$ consisting of $p_3$ and $p_4$.
We know from the case $n=2$ that 2 matches are necessary to have all the possible combination with the elements $t_1, t_2, p_5$ and $p_6$ hence the total number of matches will be 4 (2 times the case $n=2$).
Generalisation
Proceeding like this, we need $2^{n-1}$ matches so that each player will have played against all the others.
Deducing $n=11$
$2^{10}$ = 1024 matches

Second approach:

This approach has been proposed by Jaap Scherphuis (see comment bellow):

Consider that for $n=2$ you'll need two matches, those two matches ensure that a given player plays against everyone else.
For $n=3$ you can add the two new players to the previous configurations:
For example ($p_1$, $p_2$ and $p_5$) against ($p_3$, $p_4$ and $p_6$)
Followed by ($p_1$, $p_3$ and $p_5$) against ($p_2$, $p_4$ and $p_6$)
In this cas $p_5$ plays all his matches with $p_1$ so he plays against everybody except $p_1$ (and same for $p_6$ and $p_4$).
But if you add a third match with the position of $p_5$ and $p_6$ reversed then it's enough.
Therefore you need three matches.
Generalisation: you'll need at least n matches.