Given n teams of n people, go n rounds matching each person with different people from other teams

Question

There a n teams of n people, where n is a natural number greater than 1. In one round, each person from each team is grouped with one person from each of the other teams. This forms n sets of n people, where each set contains one person from each team. Is is possible do go for n rounds such that no two people are in the same set twice?

This problem was suggested to me by a teacher who used this scheme for some class exercise. It may be a generalization of the question “How do I rotate 3 groups of 4 people into teams....”

If n is a prime number, the answer is yes, and there is a simple formula for generating the sets. This uses the fact that the integers modulo n is a field when n is prime. Similarly, the answer is yes if n is a power of a prime, since we can match the numbers 1 to n with the elements of the finite field of n elements. But even for n = 6, the number of combinations gets quite large.

Another formulation of the problem: For any natural number n, can we find an n by $n^2$ matrix $a_{i,j}$ where each entry is a number from 1 to n and for any two rows $i_1$ and $i_2$ all of the ordered pairs $(a_{i_1,j},a_{i_2,j})$ are different? Can we do this is such a way, when you look at the n n-by-n submatrices (which correspond to the “rounds”), the entries in each row of each submatrix are distinct (i.e. the row is a permutation of 1..n)?

Answer 1

This is equivalent to finding a system of $n-1$ mutually orthogonal Latin squares (MOLS). Proof:

Number the teams $1$ to $n$, and the number people in team $1$ from $1$ to $n$. After the first round, label all $n^2$ people with an ordered pair $(i,j)$, where $i$ is the number of their team and $j$ is the number of the person from team $1$ they were grouped with.

For each round number $r\in \{2,3,\dots,n\}$, define a Latin square $M_r$ as follows. The cell $(i,j)$ in $M_r$ is labeled with $k$ whenever person $(i,j)$ played with person number $k$ from team $1$ in round $r$. For example, $(1,j)$ has label $j$, since person $(1,j)$ is in team $1$, so the person they played with in team $1$ is their self. You can verify $M_r$ is a Latin square, and that these squares are mutually orthogonal.

It is currently unknown whether there are any $n$ which are not prime powers for which $n-1$ MOLS of order $n$ exists. This is equivalent to finding a finite projective plane whose order is not a power of a prime.