I solved this problem in Korea TST. If tournament was partitioned by "connected tournament", we can show that each of size is power of 2 by induction. The answer is $ (2^{s}t, 2^{s}-1)$, where $ t$ is odd.

edit : ($ 2^{s}t, u$) where $ u\le 2^{s}-1$, $ t\equiv 1\pmod2$

Another solution. To each round we may assign a function $ \sigma_{i}$ that maps a player to his mate in round $ i$. Then $ \sigma_{i}^{2}=I$ where $ I$ is the identity function. If we draw the graph linking playmates by edges we may assume it is connected, otherwise work with its connected components. The condition in the problem may be reformulated as $ \sigma_{i}\sigma_{j}=\sigma_{j}\sigma_{i}$ so the functions commute. Let's pick up a basis $ f_{1}, f_{2}, \ldots, f_{m}$ of these functions. It means that we have no identity $ f_{i_{1}}f_{i_{2}}\ldots f_{i_{k}}=I$ ($ I$ is the identity function) but we have such an identity if we add any other $ \sigma_{i}$. So $ \sigma_{i}$ can be written as $ f_{i_{1}}f_{i_{2}}\ldots f_{i_{j}}$. There are just $ 2^{m}-1$ such possibilities therefore $ k\leq 2^{m}-1$. Remark: if for a player $ x$ we have $ f_{i_{1}}f_{i_{2}}\ldots f_{i_{j}}(x)=x$ then we conclude $ f_{i_{1}}f_{i_{2}}\ldots f_{i_{k}}=I$. It follows from the fact that the graph is connected. Now we prove that $ 2^{m}|n$ by induction on $ m$. Indeed, $ n$ must be even. Then we can divide the vertices into pairs $ (x_{1},y_{1}), (x_{2},y_{2}), \ldots, (x_{\frac{n}{2}}, y_{\frac{n}{2}})$ such that $ f_{k}(x_{i})=y_{i}$. Assume that $ f_{i}$ maps $ x_{j}$ into $ x_{k}$ or $ y_{k}$. Then it maps $ y_{j}$ into $ y_{k}$ or $ x_{k}$. We may construct thus a function $ f_{i}'$ on $ \{1,2, \ldots, \frac{n}{2}\}$ that maps $ j$ to $ k$. These $ m-1$ functions are also independent, as $ f_{i_{1}}'f_{i_{2}}' \ldots f_{i_{j}}'=I$ would imply $ f_{i_{1}}f_{i_{2}}\ldots f_{i_{j}}=I$ or $ f_{k}f_{i_{1}}f_{i_{2}}\ldots f_{i_{j}}=I$. So $ \frac{n}{2}$ is divisible by $ 2^{m-1}$ by the induction hypothesis. Now we prove that for $ n$ divisible by $ 2^{m}$ there exists a tournament with $ 2^{m}-1$ rounds or ($ m$ independent function s). This is done by induction on $ m$. The basis is clear. Now let's consider a game on $ \frac{n}{2}$ players $ 1,2, \ldots, \frac{n}{2}$ and $ 2^{m-1}-1$ rounds. We may split the players into 2: $ i$ into $ x_{i}, y_{i}$. We may choose a round such that $ x_{i}$ plays with $ y_{i}$. Also for any round $ R$ such that $ i$ plays with $ j$ we may construct two rounds: one where $ x_{i}$ plays with $ x_{j}$ and $ y_{i}$ with $ y_{j}$ and one where $ x_{i}$ plays with $ y_{j}$ and $ y_{j}$ with $ x_{i}$. We get $ 2^{m}-1$ round on $ n$ players, proving the induction step. So the answer is $ n$ divisible by the smallest power of $ 2$ exceeding $ k$.

Sorry for not translating... This is a VERY BEAUTIFUL problem!!!! La respuesta es: Las parejas $(n,k)$ que cumplen que si $2^a \le k$ es la mayor potencia de $2$ menor o igual a $k$, entonces $2^{a+1} | n$. Demostración: Tenemos una gráfica de $n$ vértices donde las aristas son coloreadas de $k$ colores, y de cada vértice sale una arista de cada color, tal que si $AB$ es de color $i$ y $CD$ es de color $i$ y $AC$ es de color $j$ entonces $AD$ es de color $j$. Sea $P(n,k)$ la proposición que dice que existe una gráfica así con $n$ vértices y $k$ colores. Primero, muestro que $P(n,k) \Rightarrow P(n,k-1)$. Ésto es fácil, en mi torneo simplemente elimino las aristas de color $k$. Ahora muestro que $P(n,2^a) \Rightarrow 2^{a+1} | n$. Para ver ésto, vemos que el color $1$ "empareja" a los vértices. Ahora, si dos vértices están unidos por el color $2$, entonces sus parejas respectivas también están unidas por el color $2$. Entonces el color $2$ empareja a las parejas, creando cuartetas. Similarmente, el color $3$ empareja cuartetas, el color $4$ empareja octetas, etcétera. De aquí es fácil concluir. Ahora, muestro $P(2^a, 2^a-1)$ para $a \ge 1$. Lo hago inductivamente. Para $a=1$ es obvio. Ahora, supongamos que tengo mi acomodo para $a$ y crearé uno para $a+1$. Supongamos que, en mi acomodo para $a$, numero los vértices del $1$ al $2^a$. Mis colores son color $1$, color $2$, ..., color $2^a-1$. Sea $f(x,y)=0$ si no hay arista entre los vértices número $x$ y $y$, y de lo contrario sea $f(x,y)$ el valor del color de la arista $xy$. Notemos que $f(x,y)=f(y,x)$. El siguiente será mi acomodo para $a+1$. Mis vértices serán vértice $1$, ..., vértice $2^a$, vértice $1_p=1+2^a$, ..., vértice $2^a_p=2^a+2^a$. Defino una función $g : \{1,...,2^{a+1} \} \times \{1,...,2^{a+1} \} \rightarrow \{0,1,...,2^{a+1}-1\}$. $g$ cumplirá que $g(x,y)=g(y,x)$: Sea $g(x,y)=f(x,y)$ si $x,y < 2^a+1$. Sea $g(x,x+2^a) = 2^{a+1}-1$. Sea $g(x,y)=f(x,y-2^a)+2^a-1$ si $x<2^a+1$ y $y \ge 2^a+1$. Si dibujo una gráfica con esos vértices y tal que $g(x,y)=0$ si no hay arista entre $x,y$ y que si $g(x,y) \neq 0$ entonces la arista $xy$ será del color $g(x,y)$, es fácil ver que la gráfica funcionará. Entonces he completado mi inducción. Ahora... Tengo tres propiedades de $P$: (1) $P(n,k) \Rightarrow P(n,k-1)$ (2) $P(2^a, 2^a-1)$ (3) $P(n, 2^a) \Rightarrow 2^{a+1} | n$ Con éstas tres propiedades vemos que mi respuesta inicial es la correcta.

Represent the tournament by an undirected graph $G$ with $n$ vertices. After each round, update the graph by adding an edge between each pair of players who played in that round. We shall consider a partition of the graph after each round into strongly connected components(SCC). The SCC where player $P$ belongs after round $r$ is called $G_{P, r}$. Suppose that players $A$ and $B$ meet in round $r$. We shall show that $|G_{A, r-1}| = |G_{B, r-1}|$. Consider any player $P$ in $G_{A, r-1}$. Suppose that he meets $Q$ in round $r$. Now, there is a path from $P$ to $A$ in $G_{A, r-1}$. Let $X$ meet $Y$ in round $r$, $X$ have met $X'$ at some previous round $s$ and $Y$ have met $Y'$ in the same round $s$. Then, $X'$ must meet $Y'$ in the round $r$. From this fact, we see that (through a trivial breadth-first search centered at A) each player from $G_{A, r-1}$ must meet a player from $G_{B, r-1}$ in round $r$, and vice-versa. Thus, if $G_{A, r-1} \not\equiv G_{B, r-1}$, we must have \[ G_{A, r} \equiv G_{B, r} \equiv G_{A, r-1} \cup G_{B, r-1} \]Thus, $|G_{P, r}| = 2|G_{P, r-1}|$ or $|G_{P, r-1}|$ $\forall r \in [1, k]$ and any player $P$. Therefore, $|G_{P, r}|$ is always a power of $2$. But since $G_{P, k}$ has at least $k$ players and $P$ himself, $|G_{P, k}| \ge k+1$. Let $2^u$ be the smallest power of $2$ greater than $k$. Then, $2^u|G_{P, k}$ for all players $P$. Thus all SCCs have sizes divisible by $2^u$. Since the SCCs partition the graph, $2^u$ must divide $|G| = n$. Let $n = 2^uv$ and $k < 2^u$. We shall show that a tournament exists for all such $(n, k)$. First, assume that $v = 1$. Then, number the players from $0$ to $n-1$. Let player $P$ with number $p$ meet $p \wedge i$ (where $\wedge$ denotes the bitwise XOR operator) in round $i$. The tournament is well defined since $(p \wedge i) \wedge i = p$. Also, if $p \wedge i = p \wedge j$, we would have \[ p \wedge p \wedge i = p \wedge p \wedge j \implies i = j\]Thus, any $2$ players meet at most once. Also, if $a \wedge i = b, c \wedge i = d$ and $a \wedge j = c$, then, \[b \wedge j = b \wedge i \wedge i \wedge j = a \wedge i \wedge j = c \wedge i = d \]Thus, the second condition is also satisfied. For $v > 1$, considering $v$ disjoint tournaments of the $(2^u, k)$ type, we are done.

The following is essentially the solution of Iurie Boreico, except written in substantially different notation. Let $t$ be the smallest integer for which $k+1 \le 2^t$. The answer is that $n$ must be divisible by $2^t$. But in this proof we will not only show this numerical result but also essentially classify all possible $(n,k)$-tournaments. Terminology. A polarity is an involutive permutation with no fixed points (meaning all the cycles have length exactly $2$). Let $V$ be a set of $n$ players. Then an $(n,k)$-tournament is the same as a set $A \subseteq S_V$ of $k$ commuting polarities, with the additional property $(\ast)$ that $\sigma(i) \neq \tau(i)$ for any $\sigma, \tau \in A$ and $i \in V$. Construction. We begin by providing a construction for the claimed answer (and later show it is the ``only'' one): For any given integer $m$, let $G = W = ({\mathbb Z}/2)^m$ and let $G$ act on $W$ by left multiplication. Then all the $2^m-1$ non-identity elements of $G$ correspond to polarities on $W$, which commute (since $G$ is abelian) and satisfy property $(\ast)$. To apply this to the problem, let $m = t$, and take $A$ to be any subset $G - \{1\}$ with size $k$. Then take $\frac{n}{2^m}$ copies of $W$. Main Proof. Suppose now $A$ acts on $V$. Restricting to orbits (or ``connected components'') we can consider its restriction to a subset $W \subseteq V$ on which $A$ acts transitively. Because of $(\ast)$, the elements of $A$ differ on $W$ (so $A \hookrightarrow S_W$ is injective). The image generates an abelian subgroup $G$ of exponent $2$, so we write \[ A \subsetneq G = ({\mathbb Z}/2)^m \subseteq S_W \]for some $m$. By construction, the action of $G$ is faithful and transitive. Since $G$ is abelian that implies it is sharply transitive, hence equivalent to the left-regular action. So $|W|=|G|=2^m$. Now from $1 \notin A$ we get $k = |A| < |G| = 2^m$, so $m \ge t$, thus $W$ is divisible by $2^t$. Hence we have proven that $V$ is partitioned into orbits of size divisible by $2^t$, it follows that $2^t$ divides $|V|$, as desired.

For each $n$, we write $n = 2^i * n_1$ where $n_1$ is odd, then $k$ can be from $1$ to $2^i-1$ (when $n$ odd, then there is no $k$). We will proceed via induction on the number $i$. The base case when $n$ is odd or $2\pmod{4}$ is easy to see. Suppose the maximum $k$ value is $2^t-1$ for $n = 2^{t}n_1$, we prove that the maximum $k$ value for $2n = 2^{t+1}n_1$ is $2^{t+1}-1$. Let the players be $1, 2, \cdots, 2n$ and WLOG in the first round $1$ meets $2$, $3$ meets $4$, and so on. Suppose $A$ and $B$ are two players that meet in the same round, then whenever $A$ meets $C$, $B$ has to meet whoever $C$ met the first time. So we can think of each of the pairs of players $(1, 2)$, $(3, 4) \cdots $ as single players for the case $n$. So after the first round, we can make at most $2^t-1$ rounds. However, for each of the round, we can add at most one more round (for example, in a round with the "player" $x$ of $(1,2)$ and player $y$ of $(3,4)$ that was paired in the $n$ case, we can make $1$ meet $3$ and $2$ meet $4$ or $1$ meet $4$ and $2$ meet $3$). We can only add at most one round ano two players can meet a second time. For example, \begin{tabular}{ c c c c } A1 & A5 & A3 & A7 \\ A2 & A6 & A8 & A4 \\ \end{tabular}gives us the two $2n = 16$ round: \begin{tabular}{ c c c c c c c c } 1 & 9 & 5 & 13 & 3 & 11 & 7 & 15 \\ 2 & 10 & 6 & 14 & 8 & 16 & 4 & 12\\ \end{tabular}and \begin{tabular}{ c c c c c c c c } 1 & 9 & 5 & 13 & 3 & 11 & 7 & 15 \\ 10 & 2 & 14 & 6 & 16 & 8 & 12 & 4\\ \end{tabular}Thus we have proven that for $2n$, the maximum $k$ value can be at most $1+2(2^t-1) = 2^{t+1}-1$.

@above: Can you assume that each player meets only 1 player per round even though the problem doesn't specifically say?

I claim that the answer is all pairs such that $k\le 2^{\nu_2(n)}-1$. Of course, it suffices to show that, for a given $n$, the largest value of $k$ is $2^{\nu_2(n)}-1$, since smaller tournaments are constructible by just ignoring later round. Now, consider a graph on $n$ vertices corresponding to the $n$ players, and add an edge between two players during the round they meet. After a certain number of rounds, our graph will have a number of connected components. Claim: Two players, $A$ and $B$, can only meet each other on the subsequent round if their connected components are the same size Proof: Call their connected components $C_A$ and $C_B$. If they do meet each other, consider another player, $D\in C_A$, and the path between $A$ and $D$ going along $C_A$, call it $A=A_0\to A_1\to\ldots \to A_k=D$. Then, we construct a path in $C_B$ in a similar manner. Namely, define $B=B_0$, and $B_i$ is the player that $B_{i-1}$ met during the round in which $A_i$ and $A_{i-1}$ met. Note that, by condition ii, we have that $B_1$ and $A_1$ must meet, then $B_2$ and $A_2$ meet, etc. So, $D$ and $B_k$ meet on this round. As $D$ was arbitrary, all players in $C_A$ meet players in $C_B$. However, similar logic gives all players in $C_B$ meet players in $C_A$, so they must have the same magnitude for this to occur, as desired. So, at any given time, all connected components have sizes which are powers of 2. Note that, given a connected component of size $2^k$, it has at most $2^{k-1}(2^k-1)$ edges, and since it formed $2^{k-1}$ edges every round, it lasted for at most $2^k-1$ rounds. In the final state of the board, the minimum size of a connected component cannot exceed $2^{\nu_2(n)}$, or else we will have $2^{\nu_2(n)+1}|n$, so at most $2^{\nu_2(n)}-1$ rounds can occur. This is easily constructible.

In graph theory terms: such a tournament is a set of mutually edge-disjoint perfect matchings $P_1, \dots, P_k$ on $n$ vertices where the edges in any distinct $P_i, P_j$ satisfy condition (ii). We claim the answer is all pairs $(n, k)$ where $k \in \{1, 2, \dots, 2^{\nu_2(n)}-1\}$. First we'll upper bound $k$. Some definitions: for some rounds $P_1, \dots, P_m$, consider the graph on $n$ vertices containing all of their edges, $G = \bigcup_{i=1}^m P_i$. We call the connected components of $G$ blobs. For a round $P_i$ and a vertex $v$, let $N(v, P_i)$ denote the neighbor of $v$ under the perfect matching $P_i$. Lemma: All blobs of $G = \bigcup_{i=1}^m P_i$ have sizes which are powers of $2$. Proof: We on induct on $m$, with $m=1$ trivial: all blobs have size $2$. Now suppose the claim holds for $m-1$; we'll examine the interactions that occur when we union $P_m$ with $G' = P_1 \cup \dots \cup P_{m-1}$. Suppose $B$ is a blob in $G'$, and some edge $v_1v_2$ from $P_m$ is contained in $B$. We will repeatedly use condition (ii) to show that $P_m$ actually induces a perfect matching on $B$. Indeed, as we apply (ii) to rounds $P_i, P_m$ for $i=1, \dots, m-1$, we find that $P_m$ must pair $N(v_1, P_i)$ with $N(v_2, P_i)$ for each $i$. In terms of $G'$, this means that all neighbors of $v_1$ in $G'$ satisfy $N(v_1, P_m) \in G'$. Since $G'$ is connected, we can repeat the argument until we find that $N(v, P_m) \in G'$ for any $v \in G'$, as desired. Now suppose $B_1, B_2$ are blobs in $G'$, and some edge $v_1v_2$ from $P_m$ connects $B_1$ to $B_2$. Similarly as in the previous step, we'll use condition (ii) to show that $|B_1|=|B_2|$ and that $P_m$ induces a perfect matching between $B_1$ and $B_2$. Indeed, applying (ii) to $P_i, P_m$ for each $i=1, \dots, m-1$ shows that $P_m$ pairs $N(v_1, P_i)$ with a vertex in $B_2$, and since $B_1$ is connected we can repeat this argument until we find that all $v \in B_1$ are paired to vertices in $B_2$ under $P_m$. Similarly, all $v \in B_1$ are paired to vertices in $B_2$ under $P_m$, and thus our claim holds. Combining the two previous points, we see that all blobs in $P_m \cup G'$ either have the same size as a blob in $G'$, or twice the size of blob in $G'$. This completes the induction and the lemma is proved. $\Box$ Returning to our task of upper bounding the number of rounds $k$, suppose for contradiction's sake that there exist $r$ rounds $P_1, \dots, P_r$ where $r \ge 2^{\nu_2(n)}$. Consider $G = P_1 \cup \dots \cup P_r$. Each vertex of $G$ has degree $r$, meaning that each blob has size at least $r+1$. But the lemma implies blobs have size powers of two, i.e. each blob has size divisible by $2^{\nu_2(n)+1}$ and thus $2^{\nu_2(n)+1} \mid n$. This is a contradiction. To finish the problem it suffices to show that $k=2^{\nu_2(n)}-1$ rounds do exist; for any smaller $k$ we can simply remove some rounds. First check that it is possible when $n$ is a power of two, which is straightforward by induction. Then for general $n$, partition the $n$ vertices into groups with $2^{\nu_2(n)}$ vertices each. For each group we can find $2^{\nu_2(n)}-1$ working perfect matchings; to form a perfect matching on the whole graph, just pick one that works on each of the groups and collate them. We can do this $2^{\nu_2(n)}-1$ times, and it's easy to see that this works, so the construction is complete and we are done with this problem.

Solved with nukelauncher. Take the obvious graph theory interpretation, where each round is now a perfect matching. Note that if and $(n,k)$ tournament exists, then so does a $(tn,\ell)$ tournament for any $t\in\mathbb{N}$ and $\ell\le k$, simply by having $t$ disjoint copies of the $(n,k)$ tournament with $k-\ell$ of the rounds removed. Claim: A $(2^p,2^p-1)$ tournament always exists for $p\ge 1$. Proof: View the vertices as elements of $\mathbb{F}_2^p$, and for each $a\in\mathbb{F}_2^p$ that is nonzero, consider the matching given by $x\leftrightarrow x+a$ (which is involutive since $x+2a=x$). If $x\leftrightarrow x+a$, $y\leftrightarrow y+a$, and $y=x+b$, then we also have $y+a=(x+a)+b$, so the condition (ii) is satisfied. This completes the construction. $\blacksquare$ Combined with the above observations, we see that an $(n,k)$ tournament always exists when $k\le 2^{v_2(n)}-1$. We now show that the existence of an $(n,k)$ tournament implies that $k\le 2^{v_2(n)}-1$. Indeed, we have the following main claim. Claim: The connected components of an $(n,k)$ tournament (where the edges of the graphs include all the $k$ matchings) all have size a power of $2$. Proof: We proceed with induction on $k$, with $k=1$ trivial, since the graph is just a perfect matching, and every connected component has size $2$. Now suppose that the statement is true for $k-1$, and consider an $(n,k)$ tournament. Not including the last matching $M$, we see that all connected components have size a power of $2$. Suppose two of the connected components are $\{A_1,\ldots,A_a\}$ and $\{B_1,\ldots,B_b\}$, and suppose that $A_1B_1$ is an edge in $M$. Now, for any $B_i$ connected to $B_1$ say by the $\ell$th matching ($\ell<k$), then (ii) implies that $B_i$ must be connected to some $A_j$ by $M$. Iterating this, we see that each $B_i$ is connected to some $A_j$ through $M$ (this works since $\{B_1,\ldots,B_b\}$ is connected by matchings $1,\ldots,k-1$), and vice versa. Thus $M$ actually exactly pairs up $\{A_1,\ldots,A_a\}$ and $\{B_1,\ldots,B_b\}$, so $a=b$ and there are no further edges from any of these two to any other connected components from edges from matchings $1,\ldots,k-1$. We've shown that if any two connected components meet through $M$, then they must have the same size. Thus, adding in matching $k$ can only double the size of connected components (or leave them the same if no edge from $M$ ventures out of the connected component). This proves the claim. $\blacksquare$ Clearly our tournament must have a connected component of size $2^r$ where $r\le v_2(n)$ (by taking mod $2^{v_2(n)+1}$. Then, we must have \[k\cdot 2^{r-1}\le\binom{2^r}{2},\]so $k\le 2^r-1$, as desired.

Let $m$ be the unique integer such that $2^{m-1} - 1 < k \le 2^m - 1$. The answer is all $(n,k)$ such that $2^m | n$. First I will show necessity. Consider a graph with vertices as the players. Each round, we consider a matching of a new color, (say color $c_r$ in the $r$'th round) such that condition (ii) is satisfied. I claim that the size of every connected component throughout the tournament is always a power of $2$. It is clearly true initially, since every connected component has size $1$. Consider what happens in a round. Pick a connected component, call it $C_1$. If there is no match between $C_1$ and some other connected component, then clearly it does not change and so remains a power of $2$. So suppose there is a match between $C_1$ and $C_2$. I claim that this implies that every match of the people in $C_1$ and $C_2$ is going to be with a person in the other one, and $|C_1| = |C_2|$, which indeed means that the size is still a power of $2$. To see this, start from some vertex $A_1$ in $C_1$ and suppose it plays with $B_1$ from $C_2$, then since $C_1$ is connected, we can find another vertex, say $A_2$ connected to $A_1$ by say a color $c_r$. Consider the vertex $B_2$ that is connected to $B_1$ with color $c_r$ too, then clearly $A_2, B_2$ must play with each other. Repeating this, we keep obtaining a new vertex connected to some previous $A_i$'s and this is matched up with something in $C_2$. Since this covers all vertices of $C_1, C_2$, there can't be any match between $C_1$ and $C_3$, say. Also because it matches $C_1$ and $C_2$, we have $|C_1| = |C_2|$, as claimed. Suppose at the end of $k$ rounds, the size of the smallest connected component is $2^x$. This means that there can have been at most $2^x - 1$ rounds. Also since all cc's were powers of $2$ and smallest is $2^x$, we have that $2^x | n$, as claimed. For a construction, just inductively do it by greedily first creating all possible games in a connected component, and then merge two of them, this can easily be seen to work, so we are done. $\blacksquare$

Note that if there is an $(n,k)$-tournament, then there is an $(an,k)$ tournament for all $a$ because we can copy the tournament multiple times. Furthermore, if there is a $(n,k)$ tournament then there is an $(n,k')$ tournament because we can remove any rounds without violating any rules. It is easy to get the $(2^i,2^i-1)$ construction, so we focus on the proof of the bound $k\le 2^{\nu_2(n)}-1$. We start with an empty graph, and we draw vertices between people who play. Suppose we are to draw an edge between some $A$ and $B$. WLOG suppose the connected component of $A$ is at least the size of the connected component of $B$. Let $C$ be any element in the connected component of $A$, then let there be a path $A\to A_1\to A_2\to \dots \to A_i \to C$. Suppose $B$ played against some $B_1$ then $A_1$ must've played against $B_1$ in the same round that $A$ plays against $B$. Similarly, there is a player $B_2$ that plays $B_1$ and such that $B_2$ plays against $A_2$ in the same round that $A$ plays against $B$. By induction, there exists a player in $B$'s connected component, $D$, that plays against $C$ at the same time that $A$ plays against $B$. However, we have established an injective function from the connected component of $A$ to that of $B$, so the sizes of the connected components are actually equal. Inductively, we can clearly tell that the size of each connected component must always be a power of $2$. Let $n=2^a\cdot b$ where $b$ is odd. At the end of the game, all connected components are at most size $2^a$ and so each connected component has at most $2^{a-1}(2^a-1)$ edges. The entire graph, therefore, has at most $2^{a-1}b(2^a-1)$. Each round, exactly $2^{a-1}b$ edges are formed so at most $2^a-1$ rounds are played.

Consider a graph on $n$ vertices and connect two vertices on the $i$th round if they play each other. I will first prove every connected component has $2^n$ vertices for some $n$. To prove this I will do induction. Suppose that it holds true for the $k-1$th round, now suppose on the $k$th round a player in a connected component with $2^i$ vertices plays a player in a connected component with $2^j$ vertices. Suppose $j>i$ now consider a spanning tree in the component with $2^j$ vertices. Start at the vertice $A$ that connects to a vertice in the other component, clearly as we move along the spanning tree we get that every vertice in the component with $2^j$ vertices connects to a vertice in the component with $2^i$ vertices. This implies that in one move at least one player plays two people which is not possible. Clearly we can see that for a graph with $2^n$ vertices we can preform $2^n-1$ moves before we get a complete graph. Now suppose we preform $2^{\nu_2(n)}$ moves, thus from the complete graph taking $2^{\nu_2(n)}-1$ moves to form the graph if it works must be made of connected components all of which are powers of $2$ larger than $2^{\nu_2(n)}$ which is a contradicition. Clearly all values from $1$ to $2^{\nu_2(n)}-1$ work.