32 players are participating in a tournament. It's a knockout tournament, so it looks a lot like March Madness. You want to know how all the games went. The problem is that you only know the rankings of each team, and the brackets aren't published. You also know that #32 loses to #1, #31 loses to #2, and so on. Describe how to find out as much as you can about the brackets given just the rankings.
This one shouldn't be too difficult, but it's kind of interesting to think about.
This is is actually how the brackets for different 1vs1 tournaments are created, but instead of knowing the results you know the favorites and you place them in such a way that the high rank favorites meet in later rounds.
The main idea:
Place 1 and 2 at opposite sides of the bracket and them place the rest of the numbers so that the mini brackets on each round have the same sum at the ends it. Insert between the 2 players that have a direct match the numbers to keep the next mini-bracke ends the same sum
Let's take them in reverse order.
2 players:
1
2
4 players:
1
4
3
2
8 players:
1
8
5
4
3
6
7
2
16 players:
1
16
---
9
8
---
5
11
---
12
4
---
3
14
---
11
6
---
7
10
---
15
2
for 32 players:
1
32
---
17
16
---
9
24
---
25
8
---
5
28
---
22
11
---
12
21
---
29
4
---
3
30
---
19
14
---
11
22
---
27
6
---
7
26
---
13
10
---
15
18
---
31
2
