Combinatorics Olympiad problem - Sort out a schedule

Solution 1:

I believe the following does the trick and that the $109$ is really a red herring, and that the problem has a solution for each odd $n \ge 3.$

Suppose $n=2m+1$ and consider the triples $(i,i+j,i+2j)$ where $i=1,2,3,\ldots,(2m+1)$ and $j=1,2,3,\ldots, m.$ We can construct a $(2m+1) \times m $ array of triples with $(i,i+j,i+2j)$ in the $i$th row and $j$th column. We work modulo $2m+1.$

For example here's a solution for $n=9.$

$$\begin{array} {cccc} (1,2,3) & (1,3,5) & (1,4,7) & (1,5,9) \\ (2,3,4) & (2,4,6) & (2,5,8) & (2,6,1) \\ (3,4,5) & (3,5,7) & (3,6,9) & (3,7,2) \\ (4,5,6) & (4,6,8) & (4,7,1) & (4,8,3) \\ (5,6,7) & (5,7,9) & (5,8,2) & (5,9,4) \\ (6,7,8) & (6,8,1) & (6,9,3) & (6,1,5) \\ (7,8,9) & (7,9,2) & (7,1,4) & (7,2,6) \\ (8,9,1) & (8,1,3) & (8,2,5) & (8,3,7) \\ (9,1,2) & (9,2,4) & (9,3,6) & (9,4,8) \end{array}$$

The number of triples = $m(2m+1)= { 2m+1 \choose m } = $ the number of distinct pairs of integers in $S= \{ 1,2,3,\ldots,2m+1 \} $ and all triples are unique, where the order of the elements is taken into account. (For suppose $(x,y,z)$ is in our array, then $x=i,y=i+j$ and $z=i+2j$ for some $i,j$ and thus if $x<y$ this triple is in the $x$th row and $(y-x)$th column, and if $x>y$ it is in the $x$th row and $(y-x + 2m+1)$th column. So its position is uniquely determined by its elements.

Moreover, if $(x,y,z)=(i,i+j,i+2j)$ is in the array then none of $(x,z,y),(z,y,x)$ and $(y,x,z)$ can be in the array, for if one of the positions of the elements is fixed the latter three triples cannot obey the construction rule, that its elements increase by $j,$ since we know that $x,$ $y$ and $z$ increase by $j.$

Now consider a pair of integers $(a,b),$ which appears in a given triple, $(a,b,c)$. There cannot exist another triple in the array $(a,b,d),$ say, with $c \ne d$ since $c$ is uniquely determined by $a$ and $b.$

The pair $(a,b)$ cannot appear in more than three triples, in whatever order (we've already noted that we cannot have both $(a,b,c)$ and $(b,a,c)$ hence the three and not six), since the remaining element is uniquely determined by $a$ and $b.$ However, it cannot appear in less than three triples since the number of triples equals the number of pairs of distinct integers in $S,$ so this would mean that another pair must appear in more than three triples, a contradiction.

Thus we have a solution for any odd $n \ge 3.$

So a solution for $n=11$ is:

$$\begin{array} {ccccc} (1,2,3) & (1,3,5) & (1,4,7) & (1,5,9) & (1,6,11) \\ (2,3,4) & (2,4,6) & (2,5,8) & (2,6,10) & (2,7,1)\\ (3,4,5) & (3,5,7) & (3,6,9) & (3,7,11) & (3,8,2) \\ (4,5,6) & (4,6,8) & (4,7,10) & (4,8,1) & (4,9,3) \\ (5,6,7) & (5,7,9) & (5,8,11) & (5,9,2) & (5,10,4) \\ (6,7,8) & (6,8,10) & (6,9,1) & (6,10,3) & (6,11,5) \\ (7,8,9) & (7,9,11) & (7,10,2) & (7,11,4) & (7,1,6) \\ (8,9,10) & (8,10,1) & (8,11,3) & (8,1,5) & (8,2,7) \\ (9,10,11) & (9,11,2) & (9,1,4) & (9,2,6) & (9,3,8) \\ (10,11,1) & (10,1,3) & (10,2,5) & (10,3,7) & (10,4,9) \\ (11,1,2) & (11,2,4) & (11,3,6) & (11,4,8) & (11,5,10) \end{array}$$

Note that I'm not using Steiner triples, as $11 \ne 6k+1$ or $6k+3.$