Determining the round of a match in a knock out tournament I have a knock-out tournament with $n$ players. The players are $P1$, $P2$, ... $Pn$.
In a tournament with 8 players there are the matches $M1$ (between $P1$ and $P2$), to $M4$ (between $P7$ and $P8$) in round 1. In round 2 the matches are $M5$ and $M6$ and in round 3 is the match $M7$.
Now I need a formula to calculate the round number for a given $M$. I think this should be pretty simple, but I have no idea what to look for.
 A: Assuming that the number of players is $n$ and not $2^n$: In round 1 there are $n/2$ matches. In round 2 there are $n/4$ matches. In round $k$ there are $\frac{n}{2^k}$ matches. There are a total of $\log_2(n)$ rounds. The total number of matches is thus $$\sum_{i=1}^{\log_2(n)} \frac{n}{2^i}=n-1.$$ 
If you want to find out in which round match $j$, i.e. $M_j$, has taken place, you are looking for the minimal round $k$ ($k$ integer) such that $$\sum_{i=1}^{k} \frac{n}{2^i} \geq j.$$ 
In an optimization context one might write that the round number $R(j$) of match $j$ is given by 
\begin{equation*}
\begin{aligned}
R(j)=& {\text{minimize}}
& & k \\
& \text{subject to}
& & \sum_{i=1}^{k} \frac{n}{2^i}\geq j,\\
&& &k \in \mathbb{Z}
\end{aligned}
\end{equation*}
Luckily, we don't have to use integer-programming methods to solve the problem. The number of matches up to round $k$ is given by  $$\sum_{i=1}^{k} \frac{n}{2^i} = n-2^{-k}n.$$ We thus need to solve $$j=n-2^{-k}n$$ for $k$. Since the $k$ obtained this way needs not to be an integer, we have to round it to the next higher integer. Thus, $R(j)=\lceil k \rceil$ with $k$ satisfying $j=n-2^{-k}n$.Solving the equation for $k$ yields $k=\frac{\log(\frac{n}{n-j})}{\log 2}$. This value then needs to be rounded to the next highest integer.
