Mathematical solution to split X teams into 3 Teams per day

Question

I am trying to split X number of Teams into "play days" which consist of 3 teams per day

There is more than one solution to solve this for 15 teams.

What is the best approach to find all possible fixtures/match plans for team count 9-21? Team count of 11, 14, 17 and 20 also cause problems, because total_matches/3="must be even/integer"

15 Teams // 105 Total Matches // 35 Total Days
D1 = 1:2  1:3  2:3
D2 = 2:4  2:5  4:5
D3 = 3:4  3:6  4:6
D4 = 4:1  4:7  1:7
D5 = 5:1  5:6  1:6
D6 = 6:2  6:7  2:7
7 = 7:3  7:5  3:5
8 = 8:1  8:9  1:9
9 = 9:2  9:10  2:10
10 = 10:1  10:11  1:11
11 = 11:2  11:8  2:8
12 = 12:1  12:13  1:13
13 = 13:2  13:14  2:14
14 = 14:1  14:15  1:15
15 = 2:12  2:15  12:15
16 = 3:8  3:10  8:10
17 = 3:9  3:11  9:11
18 = 3:12  3:14  12:14
19 = 4:8  4:12  8:12
20 = 5:8  5:13  8:13
21 = 6:8  6:14  8:14
22 = 7:8  7:15  8:15
23 = 9:4  9:13  4:13
24 = 9:5  9:12  5:12
25 = 10:4  10:14  4:14
26 = 11:4  11:15  4:15
27 = 12:6  12:10  6:10
28 = 13:3  13:15  3:15
29 = 14:5  14:11  5:11
30 = 5:10  5:15  10:15
D31 = 6:9  6:15  9:15
D32 = 6:11  6:13  11:13
D33 = 7:9  7:14  9:14
D34 = 7:10  7:13  10:13
D35 = 7:11  7:12  11:12

Answer 1

The number of possible combinations/matches of teams can mathematically be described as a Triangular Number.

For example, when there is 9 teams, the number of matches is 36.

Notice, that this number is only divisible by 3 when k or k-1 is divisible by 3. With 5 teams, you will end up with 10 possible games. Your last week will only have 1 game or you can structure it differently.

If you want to write out the combinations of matches, you can list them by iterating through the number of teams twice. Here is some example Java code. You may run it in an online Java compiler.

    public class MyClass {

        public static void main(String args[]) {
            int TEAMS = 10; //Number of teams
            int combos = 0;

            for(int i = 1; i <= TEAMS-1; i++){
                for(int j = i+1; j <= TEAMS; j++){
                    System.out.println("Team " + i + " plays Team " + j);
                    combos ++;
                }
            }

            System.out.println("There is " + combos + " possible matches");
        }
    }

We don't just want every combination of 2 teams. We want to look at combinations of 3 teams. Mathematically, we want a Combination.

We can rewrite our Triangular number as n choose k. Our previous example becomes:

Every week that we choose has 3 teams playing. The total possible day combinations is n choose 3. In our example with 9 teams.

We have 84 possible day combinations. Many of these days have overlapping games. For example, if we have teams 1, 2, and 3 play one day, then we don't want another day with teams 1,2 and 4 because then 1 and 2 play 2 games against each other. The solution for this could be to ignore duplicated games.

I want to point out that a perfect solution does not exist. For most number of teams, there is not a solution where every day 3 teams can play together that haven't already played. For example, when we have 4 teams, our games are: 1-2, 1-3, 1-4, 2-3, 2-4, 3-4. If we took 3 of those teams the first day (1-2, 1-3, 2-3) then the second day we don't get a perfect combination (1-4, 2-4, 3-4).

No matter how you break it, you can sort for the best combinations but you will end up with many random games at the end.

I created code below to look at every possible day combination and print out days that are not duplicated.

    public class MyClass {

        public static void main(String args[]) {
            int TEAMS = 9; //Number of teams

            //Keep track of each game combination used
            boolean gamesPlayed[][] = new boolean[TEAMS+1][TEAMS+1];

            int day = 1;
            for(int i = 1; i <= TEAMS-2; i++){
                for(int j = i+1; j <= TEAMS-1; j++){
                    for(int k = TEAMS; k >= j+1; k--){

                        if(!gamesPlayed[i][j] && !gamesPlayed[i][k] && !gamesPlayed[j][k] )
                        {
                            System.out.println("Day "+ day++ + " Teams " + i + ", " + j + " & " + k + " Play");
                            gamesPlayed[i][j] = true;
                            gamesPlayed[i][k] = true;
                            gamesPlayed[j][k] = true;
                        }
                    }
                }
            }


            System.out.println("\nLeftover games");
            for(int i = 1; i <= TEAMS-1; i++){
                for(int j = i+1; j <= TEAMS; j++){
                    if(! gamesPlayed[i][j])
                        System.out.println(" Team " + i + " plays Team " + j);
                }
            }



        }
    }