10 events, 10 teams

Question

I need help scheduling an event where there are 10 activities and 10 teams. Each team plays against another team for each activity. Each team must play each activity. Ideally, they would not play against the same team twice, but hopefully play against as many teams as possible. Help scheduling this?

Answer 1

Number the players from $0$ to $9$. Also, number the activities from $0$ to $9$. For $i\neq j$, players $i$ and $j$ oppose each other in activity $i+j\pmod(10)$. It is clear that a player never plays the same activity twice.

However, player $i$ does not play activity $2i$, and neither does player $i+5$. So for $i=0,1,2,3,4$ players $i$ and $i+5$ meet in activity $2i$.

This can be scheduled in $10$ rounds, with $5$ different activities in each round. Consider the $50$ matches as the vertices of a graph, where two vertices are adjacent if they are in the same activity or if they share a player. We can schedule the matches to meet the criteria if and only if the graph can be colored with $10$ colors. I created the matches as described above, except that I numbered from $1$ to $10$, and then ran the graph through a graph coloring program by Michael Trick that I've had forever. The chromatic number is in fact $10$.

Here is the schedule. The line 5 vs 9 at 3 means that player $5$ plays player $9$ at activity $3$.

Round 1

    5 vs 9 at 3
    7 vs 10 at 6
    3 vs 8 at 5
    4 vs 6 at 9
    1 vs 2 at 2

Round 2

    5 vs 8 at 2
    4 vs 7 at 10
    2 vs 6 at 7
    9 vs 10 at 8
    1 vs 3 at 3

Round 3

    8 vs 9 at 6
    2 vs 10 at 1
    1 vs 4 at 4
    5 vs 6 at 10
    3 vs 7 at 9

Round 4

    7 vs 8 at 4
    1 vs 5 at 5
    4 vs 10 at 3
    3 vs 6 at 8
    2 vs 9 at 10

Round 5

    2 vs 8 at 9
    3 vs 10 at 2
    4 vs 9 at 7
    1 vs 6 at 6
    5 vs 7 at 1

Round 6

    3 vs 8 at 10
    4 vs 9 at 2
    6 vs 10 at 5
    1 vs 7 at 7
    2 vs 5 at 6

Round 7

    1 vs 8 at 8
    2 vs 4 at 5
    6 vs 7 at 2
    5 vs 10 at 9
    3 vs 9 at 1

Round 8

    6 vs 8 at 3
    1 vs 9 at 9
    5 vs 10 at 4
    3 vs 4 at 6
    2 vs 7 at 8

Round 9

    6 vs 9 at 4
    1 vs 10 at 10
    4 vs 8 at 1
    2 vs 7 at 3
    3 vs 5 at 7

Round 10

    7 vs 9 at 5
    1 vs 6 at 1
    2 vs 3 at 4
    8 vs 10 at 7
    4 vs 5 at 8 

One can visually inspect the schedule to see that all $10$ players participate in each round, and that each round comprises $5$ different activities. The program checked that I made no error in constructing the matches; each player plays each activity once, and plays against each other player at least once.

Answer 2

Here is the best schedule my computer could come up with. As mentioned in the comments, in order for everyone to play every game, they will need to repeat at least one opponent, and this schedule has everyone repeating only one opponent.

My schedule takes $11$ rounds. Certainly, at least $10$ rounds are necessary, but I do not know if $10$ rounds is actually attainable.

          Game 1  Game 2  Game 3  Game 4  Game 5  Game 6  Game 7  Game 8  Game 9 Game 10
Round  1 │      │   4/9 │   7/8 │       │  5/10 │       │   2/3 │   1/6 │       │       │
Round  2 │      │   1/3 │   6/9 │       │   2/8 │       │  7/10 │       │   4/5 │       │
Round  3 │  5/6 │       │       │       │   3/7 │       │   1/4 │       │  9/10 │       │
Round  4 │  3/8 │       │       │  4/10 │       │   1/2 │       │   7/9 │       │   5/6 │
Round  5 │  4/7 │  2/10 │   1/5 │       │       │   3/9 │   6/8 │       │       │       │
Round  6 │ 1/10 │   6/7 │       │   3/5 │       │   4/8 │       │       │       │   2/9 │
Round  7 │      │       │       │   2/6 │   1/9 │   5/7 │       │       │       │   3/8 │
Round  8 │      │       │       │   8/9 │   4/6 │       │       │       │   2/7 │  1/10 │
Round  9 │      │       │   2/4 │   1/7 │       │       │   5/9 │  8/10 │   3/6 │       │
Round 10 │      │       │  3/10 │       │       │       │       │   2/5 │   1/8 │   4/7 │
Round 11 │  2/9 │   5/8 │       │       │       │  6/10 │       │   3/4 │       │       │

I solved this by first choosing which pairs play which activity using the method described at Wikipedia, and then turned the problem of assigning rounds to these pairs as a graph coloring problem, which I solved with a simple backtracking algorithm.

Answer 3

Here’s a simple solution with ten rounds. In each round $i$:

• teams $i$ and $i + 2$ play at activity $i$,
• teams $i + 6$ and $i + 7$ play at activity $i + 1$,
• teams $i + 5$ and $i + 9$ play at activity $i + 2$,
• teams $i + 1$ and $i + 4$ play at activity $i + 3$,
• teams $i + 3$ and $i + 8$ play at activity $i + 4$,

with all values taken $\bmod 10$.

round	act. 0	act. 1	act. 2	act. 3	act. 4	act. 5	act. 6	act. 7	act. 8	act. 9
0	0/2	6/7	5/9	1/4	3/8	.	.	.	.	.
1	.	1/3	7/8	6/0	2/5	4/9	.	.	.	.
2	.	.	2/4	8/9	7/1	3/6	5/0	.	.	.
3	.	.	.	3/5	9/0	8/2	4/7	6/1	.	.
4	.	.	.	.	4/6	0/1	9/3	5/8	7/2	.
5	.	.	.	.	.	5/7	1/2	0/4	6/9	8/3
6	9/4	.	.	.	.	.	6/8	2/3	1/5	7/0
7	8/1	0/5	.	.	.	.	.	7/9	3/4	2/6
8	3/7	9/2	1/6	.	.	.	.	.	8/0	4/5
9	5/6	4/8	0/3	2/7	.	.	.	.	.	9/1