Written by Colin+ in decision maths, modelling, sport.

Once upon a time, there was a Scrabble tournament. Sixteen of the county's greatest Scrabbleologists descended on the venue... only to find the organiser had lost the fixture list.

What the organise could remember was this: there were five rounds, and each player played each of the others exactly once.

Luckily, my dear readers, I was one of the sixteen... and we had enough time before the tournament started for me to work it out.

Has we just been nine, it would have been quite easy. You'd need four three-player rounds, and you'd start by laying out a table:

$\begin{array}{ccc} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{array}$

In the first round, you play across the rows (1 vs 2 vs 3); in the second, down the columns (1 vs 4 vs 7); in the third, along the forward diagonals with wrapping (1 vs 5 vs 9, 2 vs 6 vs 7 and 3 vs 4 vs 8) before, finally, the backward diagonals with wrapping (1 vs 6 vs 8, etc). That's quite neat, and works perfectly well. For nine players, at least.

For sixteen, the method breaks down for reasons (as far as I can gather) of group theory and permutations that I don't really understand. However, you can arrange the 16 another way. Here's how I approached it.

1. Arbitrarily, I decided that player 1's opponents would, in turn, be:

- 2, 3 and 4 in round A1

- 5, 6 and 7 in round B

- 8, 9 and 10 in round C

- 11, 12 and 13 in round D

- 14, 15 and 16 in round E.

It's almost as if there's a pattern!

2. Now for the clever bit: in each of the five rounds, one of those five groups of opponents is busy playing player 1 and each other; in the other round, the three players of each group need to be on separate tables. So (again arbitrarily), I set up round A as:

$\begin{array}{cccc} 1 & 2 & 3 & 4\\ \hline 5 & 8 & 11 & 14 \\ \hline 6 & 9 & 12 & 15 \\ \hline 7 & 10 & 13 & 16 \end{array}$

(Playing across the way).

3. In round B, Players 5, 6 and 7 are all playing each other and player 1. Because of the matchups in the previous round, player 8 (for example) can only play against 12 or 13 from the D group. Let's fix her up against 12, who has already played 15; 8 played 14 previously as well, so we're stuck with 8-12-16.

Using a similar argument for player 10, we end up with 10-11-15 and 9-13-14 left over, all of which are valid; I'll set them up like this:

$\begin{array}{cccc} 1 & 5 & 6 & 7\\ \hline 2 & 8 & 12 & 16 \\ \hline 3 & 9 & 13 & 14 \\ \hline 4 & 10 & 11 & 15 \end{array}$

4. Now we're getting somewhere. In round C, there are many fewer possibilities. 8, 9 and 10 are busy on player 1's table, and we know 11 must play 16, 12 must play 14 and 13 must play 15 this round. Player 6 has already played 12 and 15, so 6-11-16 is the only working combination; 7-12-14 and 5-13-15 bring up the rear. Player 2 can't meet 12 or 16 again, so we have 2-5-13-15, 3-6-11-16 and 4-7-12-14:

$\begin{array}{cccc} 1 & 8 & 9 & 10\\ \hline 2 & 5 & 13 & 15 \\ \hline 3 & 6 & 11 & 16 \\ \hline 4 & 7 & 12 & 14 \end{array}$

5. It's all over bar the checking! We're stuck with 5-16, 6-14 and 7-15 given the previous rounds. 16 can't play 2 or 3, either, which gives 4-5-16, 2-6-14 and 3-7-15 (with similar arguments for 14 and 15). Lastly, 9 can't play 3 or 14, so we have 4-5-9-16, 2-6-10-14 and 3-7-8-15.

$\begin{array}{cccc} 1 & 11 & 12 & 13\\ \hline 2 & 6 & 10 & 14 \\ \hline 3 & 7 & 8 & 15 \\ \hline 4 & 5 & 9 & 16 \end{array}$

6. And round E writes itself: there are four remaining foursomes that haven't played each other:

$\begin{array}{cccc} 1 & 14 & 15 & 16\\ \hline 2 & 7 & 9 & 11 \\ \hline 3 & 5 & 10 & 12 \\ \hline 4 & 6 & 8 & 13 \end{array}$

After working this out the hard way, as is so often the case, I figured out the pattern: it's all to do with permutations. There are five groups, as set out in step 1 - in each round, player 1 takes on one of the groups leaving the other four to battle it out between them. If you ignore the first row and look at the remaining columns, you'll see that each group remains in the same cyclic order - either everyone's in the same order as they started, or they've moved forward one, or they've moved backward one space.

The trick was to make sure no pair of offsets matched up in any round - if you moved on two of the groups the same number of steps in any round, you'd end up with repeated fixtures. In round A, everyone is offset by 0 steps (apart from group 2-3-4, who are playing on the top table).

In round B, group 2-3-4 is offset by 0, 5-6-7 is on the top table, 8-9-10 are offset by 0, 11-12-13 offset by 2 and 14-15-16 by 1. This whole thing looks nicer in a table:

$\begin{array}{c|c|c|c|c} 2-3-4 & 5-6-7 & 8-9-10 & 11-12-13 & 14-15-16 \\ \hline - & 0 & 0 & 0 & 0 \\ 0 & - & 0 & 2 & 1 \\ 0 & 0 & - & 1& 2 \\ 0 & 2 & 1 & - & 0 \\ 0 & 1 & 2 &0 & - \end{array}$

You can see (if you look really hard) that if you take any pair of columns, you never get the same pair of relative offsets between them. (Leaving the first row and column of zeros aside, there's a nice Latin Square feel to the remaining four by four grid).

Question: for what numbers of participants is it possible to make this sort of arrangement?2