Find the minimum and maximum number of matches that can be played in a double-elimination tournament with n players.

Question

A double-elimination tournament is a one in which each player eliminates only after 2 losses. In case of minimum matches, there will be n-1 losers and minimum 2 matches produce 1 loser. Hence the total number of minimum matches will be 2(n-1). Going by the same logic, maximum 3 matches produce 1 loser hence the maximum number of matches will be 3(n-1). But the text says that the answer is 2n-1. What am I missing here?

Answer 1

It’s not clear to me why you think that at most $3$ matches produce $1$ loser. A player could be eliminated after winning several games and only then losing $2$. Also, even if you had correctly derived an upper bound of $3(n-1)$, you haven’t provided any argument why this should be the least upper bound, so there’s no contradiction with there being a lower upper bound of $2n-1$.

The upper bound of $2n-1$ is only correct if each match has a loser and there are no draws/ties. If so, since each of the $n-1$ losers has exactly $2$ losses and the winner has either $0$ or $1$ loss, the total number of losses, and hence of matches, must be either $2(n-1)$ or $2(n-1)+1=2n-1$.