Double Elimination - How many rounds?

Here is my problem solving episode.

In a single elimination tournament, you need ceil(log₂(players)) rounds. (2 players, 1 round; 3-4 players, 2 rounds; 5-8 players 3 rounds, etc.) In double elimination, players get a second chance. After losing in the winners' bracket, they enter a second bracket, and the winner of that emerges as a tournament finalist. How many rounds are there in the losers' bracket?

Solution:

1. Understanding the problem:

• Unknown: Number of rounds in losers' bracket. Let's call it L.
• Let's call the winning bracket W.
  
• Data: we know that in a winning bracket, W = ceil(log₂(players))
• Figure:

  

  
  

• Separate and conquer:
  

We know that from every winners bracket with n players, there are n-1 losers.
At each stage, the number of people added to the losers bracket is half of the number of people at the stage on the winners bracket.

2. Devising a plan:

• Find a connection:

Let's use an example to find a connection. Let's say there are 8 players initially.

After round 1, 4 players go into the semi-final bracket, and 4 go into the first round of L.
After round 2, 2 players are out of L, and 2 more go in.
After round 3, 1 player goes from W to L.
After round 4, This is the winner of L.
After round 5, This is the winner of W and L.

3. Carrying out the plan:

What we learned from the previous example is that,

The number of players initially in the losers bracket, lets say N(initial) = n/2
The next would be n/4, and the next n/8 and so on.
The total number of rounds initially would be L(initial) = ceil(log₂(players)) # using the math prereqs( 2^c = b => log_2(b) = c)

so with 8 players initially, we have ceil(log₂8) = 3 initial rounds.

Now after every round, n/2^(2*round number) gets added to the losing bracket. To take this into account, we take the initial number of rounds in L, and calculate the next number of rounds by doing the same process. i.e, The extra number of rounds would be:

ceil(log₂(L(initial)))

So for our example of 8 players, ceil(log₂(L(initial))) = ceil(log₂(3)) = 2 extra rounds.

Therefore, in conclusion, the total number of rounds would be the addition of these two calculations to get:

Total L = ceil(log₂(L(initial))) + ceil(log₂(n))

4. Looking back:

Let us check this with our intuition:

for 16 players L = ceil(log₂4) + ceil(log₂16) = 2 + 4 = 6 rounds. Which is correct.

for 128 players L = ceil(log₂8) + ceil(log₂128) = 3 + 7 rounds. Which is correct.


Source: http://www.gottfriedville.net/mathprob/misc-dblelim.html
Note: even though this problem is already solved, I found it very interesting, and applied Polya's problem solving method to try and formulate it.