3

In a tournament with direct elimination where teams are seeded, the first seed team plays the last seed team, the second seed team, play the one before last seed team, etc. I'll use example with 16 teams which gives us the total of 8 matches. So the matches are:

 1 - 16
 2 - 15
 3 - 14
 4 - 13
 5 - 12
 6 - 11
 7 - 10
 8 -  9

The problem that I'm facing is how to put those matches in the tournament grid/bracket so that assuming that all higher seeded teams win, the final will be seed 1 vs seed 2, semi-finals will be seed 1 vs seed 4, seed 2 vs seed 3 etc. Drawing everything on paper, the example above should look like this in the first round of the tournament:

Match 1: 1 - 16
Match 2: 9 - 8
Match 3: 5 - 12
Match 4: 13 - 4
Match 5: 3 - 14
Match 6: 11 - 6
Match 7: 7 - 10
Match 8: 15 - 2

where winner of Match 1 plays winner of Match 2, winner of Match 3 plays winner of Match 4, etc. What I'm trying to figure out is a formula to calculate the match number for team x given n teams playing in the first round. I actually managed to get some kind of a sequence going but I still can't figure out how to write the formula in one line. Here's what I got for the example above:

Team 1 & Team 16 Match Number: 1
Team 2 & Team 15 Match Number: n
Team 3 & Team 14 Match Number: n/2 + 1
Team 4 & Team 13 Match Number: n/2
Team 5 & Team 12 Match Number: n/2 - n/4 + 1
Team 6 & Team 11 Match Number: n/2 + n/4
Team 7 & Team 10 Match Number: n/2 + n/4 + 1
Team 8 & Team  9 Match Number: n/2 - n/4
Results respectively in match numbers: 1, 8, 5, 4, 3, 6, 7, 2 as intended

Continuing for let's say a tournament with 32 teams the sequence still works:

Team 1 & Team 32 Match Number: 1
Team 2 & Team 31 Match Number: n
Team 3 & Team 30 Match Number: n/2 + 1
Team 4 & Team 29 Match Number: n/2
Team 5 & Team 28 Match Number: n/2 - n/4 + 1
Team 6 & Team 27 Match Number: n/2 + n/4
Team 7 & Team 26 Match Number: n/2 + n/4 + 1
Team 8 & Team 25 Match Number: n/2 - n/4
Team 9 & Team 24 Match Number: n/2 - n/4 - n/8 + 1
Team 10 & Team 23 Match Number: n/2 + n/4 + n/8
Team 11 & Team 22 Match Number: n/2 + n/4 - n/8 + 1
Team 12 & Team 21 Match Number: n/2 - n/4 + n/8
Team 13 & Team 20 Match Number: n/2 - n/4 + n/8 + 1
Team 14 & Team 19 Match Number: n/2 + n/4 - n/8
Team 15 & Team 18 Match Number: n/2 + n/4 + n/8 + 1
Team 16 & Team 17 Match Number: n/2 - n/4 - n/8
Results respectively in match numbers: 1, 16, 9, 8, 5, 12, 13, 4, 3, 14, 11, 6, 7, 10, 15, 2 as intended

Feels like I'm very close to the finish line but I can't get all the numbers in one simple formula. Any help would be greatly appreciated.

mmvsbg
  • 151

1 Answers1

2

If anyone is interested, here's a piece of code with the solution for the problem above. Keep in mind that the ordering will be slightly different as the problem described above is not symmetric. To achieve the results as stated in the problem the order of the matches has to be reversed in the second part of the schema:

int TG = 128;
Console.WriteLine("Number of games: {0}", TG);
int[] ind = new int[TG];
for (int i = 0; i <= (int)Math.Log(TG, 2); i++)
{
    for(int N = 1; N <= TG; ++N)
    {
        int myRank = (N - 1) / (int) Math.Pow(2, i) + 1;
        ind[N - 1] += ((myRank % 4)/2)*(int)Math.Pow(2, ((int)Math.Log(TG, 2) -  i - 1));
    }
}
for (int N = 1; N <= TG; ++N)
{
    Console.WriteLine("Team {0} plays game {1}", N, ind[N - 1] + 1);
}

All credits go to my brother who came up with this solution!

Shaul Behr
  • 131
mmvsbg
  • 151
  • Fabulous! I'm writing some code to do exactly this now. I was screwing up my brain trying to work out a formula, when I hit on the genius idea of Googling it, and up came your solution from 6 years ago! – Shaul Behr Dec 03 '19 at 09:41
  • Now I'm digging a little more into this code, I think there's a minor flaw in the output: the game numbers are all unique, i.e. there are 128 games in your scenario. So Team 1 plays game 1, but team 128 plays game 2. Obviously you mean to match up game 1 and game 2 as one pair, then 3 and 4 as the next pair, but it doesn't look that way from the output. Not a biggie; it's easy enough to work around, but for anyone following this answer, be aware that this is the behavior. – Shaul Behr Dec 03 '19 at 13:27