Also Indian TST D3 P3. iirc nobody got full marks in this

The required minimum is $k(4k^2+k-1)/2$. Construction. We denote the players $P_1$, \dots, $P_k$ and $Q_1$, \dots, $Q_k$ in general. In the first $\binom k2$ days, the players $P_1$, \dots, $P_k$ arrive in order, and when each player arrives they play everyone else. The last $\binom k2$ are done in a symmetric way. In the middle $k^2$ days we have two phases. First $Q_1$, \dots, $Q_k$ arrive in order; when $Q_i$ arrives they immediately play $P_1$, \dots, $P_{k+1-i}$. Then $P_1$, \dots, $P_k$ depart in order; before $P_i$ departs they play the rest of their matches. Proof of the bound. Let us denote the arrival and departure dates as \begin{align*} 1 &= a_1 \le a_2 \le \dots \le a_{2k} \\ \binom{2k}{2} &= b_1 \ge b_2 \ge \dots \ge b_{2k} \end{align*}in sorted order (not necessarily corresponding to players!). If a player arrives on date $a_i$ and departs on date $b_j$ the cost is $b_j - a_i + 1$, so nonetheless the organizers pay a total of \[ S = \left( \sum_j b_j \right) - \left( \sum_i a_i \right) + (2k) = \sum_n \left( b_n - a_n + 1 \right). \] Claim: We have $a_n - 1 \le \binom{n-1}{2}$ and $\binom{2k}{2} - b_n \le \binom{n-1}{2}$ for each $n = 1 , 2, \dots, k$. Proof. This is obvious: before the $n$th arrival, there were at most $n-1$ players, so at most $\binom{n-1}{2}$ days passed. The other bound is analogous. $\blacksquare$ The previous claim of course works for $n \ge k+1$ as well. But we can actually get a better bound in this case (well, the same bound for $n = k+1$, but better when $n \ge k+2$). Claim: For $n = k+1, k+2, \dots, 2k$ we have \[ (a_n - 1) + \left( \binom{2k}{2} - b_n \right) \le 2 \binom{n-1}{2} - \binom{2(n-1)-2k}{2} \] Proof. The idea of the proof is the same as before. Before the $n$th arrival, at most $\binom{n-1}{2}$ games were played; after the $n$th departure, at most $\binom{n-1}{2}$ games were played. However, when $n > k$, the sum of two binomials double-count certain games. Specifically, there are $n-1$ players corresponding to $a_1$, \dots, $a_{n-1}$ and $n-1$ players corresponding to $b_1$, \dots, $b_{n-1}$. So there are at least $2(n-1)-2k$ players overlapped; the estimate above counts their games twice, but they really should be counted at most once. This gives the correction term above. $\blacksquare$ From this, we get the estimate \begin{align*} S &= \sum_{n=1}^{2k} \left( b_n - a_n + 1 \right) \\ &\ge \sum_{n=1}^{2k} \left( \binom{2k}{2} - 2 \binom{n-1}{2} \right) + \sum_{n=k+2}^{2k} \binom{2(n-1)-2k}{2} \\ &= 2k \binom{2k}{2} - 2\sum_{n=1}^{2k} \binom{n-1}{2} + \sum_{n=k+2}^{2k} \binom{2(n-k-1)}{2} \\ &= \frac{1}{2} k (4k^2+k-1) \end{align*}after some calculation. (Finally, since the example we exhibited at the beginning satisfies all the inequalities in the earlier claims, it achieves the same value.) Remark: [Yannick Yao] The right-hand side in the second claim evaluates to $\binom{2k}{2} - (2k-n+1)^2$ which may be thought of more naturally as all the games except for the games in a ``complete bipartite graph'' between two sets of $2k-(n-1)$ players. Remark: The equality case is not unique, as it's easily possible to for example switch days 20 and 21 in the construction for $k=4$, et cetera. That's why it is so much more fruitful to define the $a$'s and $b$'s in order rather than relative to the players; one could have, say, defined $a_i$ and $b_i$ to be the arrival and departure dates of the $i$th player, but then these variables change wildly in the equality case.

Here's the solution I submitted during TST in Thailand. Also, this is my favorite problem in ISL this year.

I claim that the answer is $\frac{n(4n^2+n-1)}{2}$. We will first prove that the cost is at least this. Define $S_i$ to be the day the $i$th person comes, and $F_i$ the day the $2n+1-i$th person leaves. In particular, we must have that $S_1=S_2=1,S_3=2$, and $F_3=\binom{2n}{2}-1$, $F_2=F_1=\binom{2n}{2}$. Claim: The total cost is equal to $2n+\sum_{i=1}^{2n} F_i-\sum_{i=1}^{2n} S_i$, regardless of who the $S_i$s and $F_i$s correspond to. Proof: The total cost to house one person is equal to $F_i-S_j+1$ for some $i,j$. As all $F$s and $S$s are used exactly once, we get the desired form. Claim: For $i>0$, $F_i-S_i+1\ge \binom{2n}{2}-2\binom{i-1}{2}$, and for $i\le n$, $F_{2n+1-i}-S_{2n+1-i}+1\ge i^2$. Proof: For the first claim, note that $S_i\le \binom{i-1}{2}+1$, since only $\binom{i-1}{2}$ matches can be played among $i-1$ people. Similarly, $F_i\ge \binom{2n}{2}-\binom{i-1}{2}$. Subtracting gives the desired result. For the latter, note that between $S_{2n+1-i}$ and $F_{2n+1-i}$, there are $i$ $S$s and $F$s. Suppose the $S$s correspond to players $S_S=\{s_1,\ldots,s_i\}$, and the $F$s correspond to players $S_F=\{f_1,\ldots,f_i\}$. Then, for a given player $s_j$, if $s_j\not\in S_F$, then he must play against all players in $S_F$ in the days between $S_{2n+1-i}-F_{2n+1-i}$. On the other hand, if $s_j\in S_F$, this means that $s_j$ must play all his games (i.e. $2n$) in this range. However, we may double count games where $s_i,s_j\in S_F\cap S_S$. So, to avoid this, we divide the game count by $2$ if $s_j$ is in $S_F$. As $2n/2=n\ge i$, we can safely say that $F_{2n+1-i}-S_{2n+1-i}+1\ge i\cdot i=i^2$, as desired. Combining these two results, we get that $$2n+\sum_{i=1}^{2n} F_i-S_i=2n+\sum_{i=1}^n\binom{2n}{2}-2\binom{i-1}{2}+\sum_{i=1}^n i^2=\frac{n(4n^2+n-1)}{2}$$as desired. This result can be obtained by setting $S_i=\binom{i-1}{2}+1$, $F_i=2n-\binom{i-1}{2}$ for $1\le i\le n$ and $S_i=\left\lfloor \frac{1}{2}\left(\binom{2n}{2}-(2n+i-1)^2\right)\right\rfloor+1$, $F_i=S_i+(2n+i-1)^2-1$ for $n\le i\le 2n$. It is not hard to see that such a configuration is constructable. (Set $(S_1,\ldots, S_{2n})$ and $(F_{2n},\ldots, F_1)$ to refer to players $(1,2,3,\ldots, 2n)$ in that order.)

Assume we have a arrangement which costs minimum. We sort the players by the day they begin (if tie, consider the last day of the player). We claim that if the last player begun is $X$ and atleast one more player is yet to begin, the period when $X$ is the latest player who has begun will have matches with $X$ as one of the players. The proof is simple, we just consider a match of some other player during that period, it must be of a player who has begun before (no player must have ended his matches by now as a new player is yet to arrive.) That match can be shifted a few days ago when both of the players were present. This clearly decreases the cost, so the claim must be true. Note that the claim is also true for the endings (sort them by their endings this time). So, if there is a match between $X$ and $Y$, where $X$ arrives before $Y$, then either during the streak when $Y$ was last arrived, or when $X$ will be leaving the next. Let the players be numbered $A_1,A_2,\cdots , A_{2k}$. Number them in the order of their arrival. The value of the number of coins required when $A_i$ is last started ($i<2k$) is $a_i$ and when it is the next to end is $b_i$, then, $a_1=1,a_2=2$, $a_3=3$, $a_4=4$, and so on . $b_i$'s are a permutation of $a_i$'s. The number of coins is $\sum_{2k \geq i>j\geq 1} min(max(a_i,a_j),max(b_i,b_j))$. Lemma: $a\geq b$, $c \geq d$, then $max(a,c)+max(b,d) \geq max(a,b)+max(c,d)$ Proof: WLOG assume $a$ is the maximum. Now, do case bash for every possible inequality between a,b,c,d satisfying the above inequalities. Using this, we can swap $b_i<b_{i+1}$. If $b_i<b_{i+1}$,we can swap them to lower the sum. So, after many such swapping, it must be decreasing. So, $b_{2k}=b_{2k-1}=2$, $b_{2k-2}=3, \cdots b_1=2k$ Now it is just algebra, to sum the required sum. The sum is then found to be $k(4k^2+k-1 )/2$

I claim the answer is $\frac{4k^3+k^2-k}{2}$. Construction: Divide the players into two groups: $x_1, x_2, ..., x_k$, and $y_1, y_2, ..., y_k$. There will be four "phases". Phase 1: Have $x_1, x_2$ play first, then $x_3$ come and play both of them, then $x_4$ come and play all three of them, and so on, until $x_k$ comes and plays $x_1, ..., x_{k-1}$. Phase 2: For each $i$ (in sequential order; starting from $i=1$ and ending at $i=k$), have $y_i$ come and play $x_1, x_2, ..., x_{k+1-i}$. Note that $x_1$ leaves on the last day of this phase. Phase 3: Have $x_2$ play everyone he hasn't played yet and then leave. Repeat for $x_3, ..., x_k$. Phase 4: Have $y_1$ play everyone he hasn't played yet, then leave. Repeat for $y_2, ..., y_k$. Bound: Let $1=a_1\le a_2\le ...\le a_{2k}$ be the arrival dates, and ${2k\choose 2}=b_1\ge b_2\ge ...\ge b_{2k}$ be the departure date. The total number of coins paid is simply $\sum_{i=1}^{2k} (b_i-a_i+1)$. Note that for all $i$, $a_i-1+{2k\choose 2}-b_i$ is the number of games played before day $a_i$ plus the number of games played after day $b_i$. For $i\in [1, k]$, it is clear that this value is at most $2{i-1\choose 2}$. For $i\ge k+1$, we still have the upper bound of $2{i-1\choose 2}$, but note that some of the players are both within the first $i-1$ to arrive and also the last $i-1$ to depart, and any game between two of these players has been double-counted in ${i-1\choose 2}+{i-1\choose 2}$. Also note that there are $i-1+i-1-2k=2i-2-2k$ such players, meaning that for $i\in [k+1, 2k]$, the number of games played before day $a_i$ plus after day $b_i$ is at most $2{i-1\choose 2}-{2i-2k-2\choose 2}$. Hence, summing this up, we have $\sum_{i=1}^{2k} (a_i-1+{2k\choose 2}-b_i)\le \sum_{i=1}^{2k} 2{i-1\choose 2}-\sum_{i=k+1}^{2k} {2i-2i-2\choose 2}$. After some algebra, this inequality turns into $\sum_{i=1}^{2k} (b_i-a_i+1)\ge \frac{4k^3+k^2-k}{2}$, as desired.

Let $m$ be the number of players. We take care of odd $m$ as well. We claim that the answer is $\begin{cases}\frac{k(4k^2+k-1)}{2}, & m = 2k\\ \frac{k(4k^2+7k+3)}{2}, & m = 2k+1. \end{cases}$ Let $S_1,...,S_m, E_1,...,E_m$ denote the start/endpoints of the interval (possibly overlapping) in which player $i$ stays in the game. Claim 1: There exists a tournament with the same cost having the start, endpoints appearing in the order $S_1,\dots, S_m, E_1,\dots,E_m$. Proof: By changing identities of players we may WLOG assume $S_1 \preceq S_2 \preceq \dots \preceq S_m$. Note that none of the $E_j$ can appear before any $S_i$. Now suppose for some $i< j$ we have $E_j \prec E_i $. Let $A$ be the set of numbers $a$ for which $(i,a)$ is between $S_i, S_j$ (i.e. before $j$ is introduced to the game). If $j = i+1$ then $A = \emptyset$. Define $B$ to be the set of players $i$ plays between $S_j,E_j$ (note that $j \in B$) and $C$ the set of players $i$ plays after $E_j$. Consider the following change $$S_i \quad (i,A)\quad S_j \quad \substack{(j,\mathbb N_m)\\ (i,B)} \quad E_j \quad (i,C) \quad E_i$$$$\mapsto S_i \quad (i,A)\quad S_j \quad \substack{(j,A\cup B)\\ (i,B\cup C)} \quad E_i \quad (j,C) \quad E_j.$$This swaps $E_i, E_j$ so the cost is fixed, as desired. $\blacksquare$ Claim 2: For any pair $(i,j)$ with $i < j$ such that $i+j \le m+1$, we may move it into the interval between $S_j, S_{j+1}$without increasing the cost. Likewise, for any $i+j \ge m+1$ we may move it into the interval between $E_{i-1},E_i$ without increasing the cost. Proof: We will only consider the case $i+j \le m+1$ as the other case can be dealt with analogously. Case 1: $(i,j)$ is between $[S_k,S_{k+1})$ for some $k > j$ (where we define $S_{m+1} = E_1$). Moving $(i,j)$ into the interval between $S_j, S_{j+1}$ shifts forward $S_{i+1},...,S_k$ by at least $1$ (specifically, if previously $S_j = S_{j+1}$ then now $(j,j+1)$ is the match that comes right after $(i,j)$) and keeps the other start/endpoints the same, hence $\sum E_i - \sum S_i$ does not increase. Case 2: $(i,j)$ is between $[E_{k-1},E_k)$ or $[E_{k-1},E_k]$ for some $2\le k \le i$. Choose $k$ so that $(i,j) \in [E_{k-1},E_k)$ whenever possible. If $(i,j)$ must be in an interval of the form $[E_{k-1},E_k]$ then $k = i$ and $(i,j)$ is located at $E_i$. In the former case, moving $(i,j)$ into the interval $[S_j,S_{j+1})$ sends each of $E_1,\dots E_{k-1}, S_m,\dots S_{j+1}$ forward by $1$, and the total change is $(k-1)-(m-j)\le i-1-m + j \le 0$. In the latter case, not only does each of $E_1,\dots,\dots E_{k-1},S_m,\dots,S_{j+1}$ get shifted by $1$, the position of $E_k$ does not increase as well, so the total change is at most the previous amount which is $\le 0$. We will show that we can perform the move described in claim 2 until any tournament we can obtain (without increasing the cost) another in which $S_1 = S_2 \preceq S_3 \preceq\dots \preceq S_m \preceq E_1 \preceq \dots \preceq E_{m-1}=E_m$ with $(1,2)$ at $S_1$, $(m-1,m)$ at $E_m$, and the positions $S_i,S_i+1,\dots,S_{i+1}-1$ contain the pairs $(i,j): j \le \min\{i-1,m+1-i\}$ and the positions $E_{i-1},\dots, E_i-1$ contain the pairs $(i,j): j \ge \max\{i+1,m+2-i\}$, so that these tournaments produce the desired minimum. To do this, we will first go step by step moving each $(i,j)$ with $i<j, i+j \le m+1$ into $[S_j,S_{j+1}]$. If $(i,j)$ neither a start point nor an endpoint, we still have $S_1 = S_2 \preceq \dots S_m \preceq E_1 \preceq \dots E_{m-1} = E_m$. However, if it is a start point then it must be at $S_j$, in which case we did not have to make this move. If it is an endpoint, then $(i,j) = E_i$ before we made the change, and the $E_i$'s will have to be reordered. However, this reordering does not affect those pairs that have already been "correctly placed" in the interval $[S_1, S_{j+1}]$. After we have already moved all $(i,j)$ with $i+j\le m+1$ into the "correct" places, we can sort the pairs in the interval $[S_1, S_m]$ without changing the content between each two consecutive $S_i$, such that now $S_1 = S_2 = (1,2)$ and $S_i = (i,1)$ for all $i = 3,\dots,m$. In this way, we can guarantee that no other "misplaced pairs" are at some start point. Now we take care of the $(i,j)$ with $i < j, i+j \ge m+2$. Moving them does not disturb the ordering of $S_1\preceq S_2 \prec S_3 \dots \prec S_m = E_1$. Now we can move the predescribed misplaced $(i,j)$ with $i = 2$, sort so that $E_2 = (2,m)$ and repeat for $E_3$, sort again so that $E_3 = (3,m)$ and repeat this for $i = 4,\dots,m-1$, which will produce our desired result (note that this sorting prevents the ordering of $S_1,\dots,\dots S_m,E_1,\dots,E_{i'-1}$ from being changed when we apply the moves with $i = i'$). We compute for $m = 2k$ $S_i = \begin{cases}\binom{i-1}{2}+1,&1\le i \le k+1\\ (\binom{k}{2} + 1) + \binom{k+1}{2} - \binom{j}{2} \text{ where } j = 2k+2-i, & k+2\le i \le 2k\end{cases}$ $$\binom{2k}{2} - E_{2k+1-i} = \begin{cases}\binom{i-1}{2}, & 1\le i \le k+1\\ \binom{k}{2} + \binom{k}{2} - \binom{j}{2} \text{where } j = 2k+1-i, & k+2\le i \le 2k \end{cases}$$from which we obtain $\sum E_i - \sum S_i + 2k = \boxed{\frac{k(4k^2+k-1)}{2}}$. We can also compute for $m =2k+1$ $$S_i = \begin{cases}\binom{i-1}{2} + 1, &1\le i \le k+2 \\ 1+\binom{k+1}{2} + \binom{k+1}{2} - \binom{j}{2} \text{where } j = 2k+3-i, & k+3\le i \le 2k+1 \end{cases}$$and $$\binom{2k+1}{2}-E_{2k+2-i} = \begin{cases} \binom{i-1}{2}, &1\le i \le k+2 \\ \binom{k+1}{2} + \binom{k}{2} - \binom{j}{2}\text{ where } j = 2k+2-i, & k+3 \le i \le 2k+1\end{cases}$$Therefore $$\sum E_i - \sum S_i + m = \boxed{\frac{k(4k^2+7k+3)}{2}}.$$

Just putting some thoughts here Since there are $\tbinom{2k}{2}$ games in total we need only consider that many days; Let the player arrival days in some order be $a_1 \leq a_2 \leq \ldots \leq a_{2k}$ and the departude dates (not necessarily corresponding) be $b_1 \geq b_2 \geq \ldots \geq b_{2k}$. The quantity\[\sum (b_i - a_i + 1)\]seems important...

jj_ca888 wrote: Just putting some thoughts here Since there are $\tbinom{2k}{2}$ games in total we need only consider that many days; Let the player arrival days in some order be $a_1 \leq a_2 \leq \ldots \leq a_{2k}$ and the departude dates (not necessarily corresponding) be $b_1 \geq b_2 \geq \ldots \geq b_{2k}$. The quantity\[\sum (b_i - a_i + 1)\]seems important... Partial solution. Note that there are $\tbinom{2k}{2}$ matches that take $\tbinom{2k}{2}$ days. We need only consider that many days; therefore, we are allowed to suppose that the dates of arrival are $1 = a_1 \leq a_2 \leq \ldots \leq a_{2k}$ and the dates of departure are $\tbinom{2k}{2} = b_1 \geq b_2 \geq \ldots \geq b_{2k}$. Note that arrival and departure date $a_j, b_j$, may not necessarily correspond to the same player. We with to minimize\[\sum b_i - \sum a_i + \sum 1 = \sum_{i = 1}^{2k} (b_i - a_i + 1).\]First let's do some dumb bounding; we see that there are at most $i-1$ players before the $i$th arrival on $a_i$, hence at most $\tbinom{i-1}{2}$ games could have been played by then, hence $a_i \leq 1 + \tbinom{i - 1}{2}$. Similarly, there are $i-1$ players who have not departed yet after the departure $b_i$, and they still have at most $\tbinom{i - 1}{2}$ games left to play with each other. This yields $\tbinom{2k}{2} - b_i \leq \tbinom{i-1}{2}$. Thus\[b_i - a_i + 1 \geq \binom{2k}{2} - 2\binom{i}{2}.\]This stupid bound can be improved in an obvious manner for $i \geq k + 1$; in these cases, the first $i$ and last $i$ have an overlap of $2(i - k)$. Note that these matches between overlapped players have been subtracted twice so we subtract a copy of $\tbinom{2(i - k)}{2}$ for $i \geq k + 1$. So in fact, we have\[b_i - a_i + 1 \geq \binom{2k}{2} - 2\binom{i}{2} + \binom{2(i - k)}{2}\]for $i \geq k + 1$.

Here is a different solution (I believe):

Solved with Alan Lee, Eric Shen, Groovy (\help), Luke Robitaille, Raymond Feng, Ryan Yang. The answer is $\frac{k(4k^2 + k - 1)}{2}$. The construction is as follows: For the first $\binom{k}{2}$, we will first pair players $(1,2)$, then $(1,3)$, then $(2,3)$, and we keep going such that whenever we finish first $\binom{i}{2}$ games, we will next do games $(1, i+1), (2,i+1), \cdots (i,i+1)$. For the next $\frac{k(k+1)}{2}$ games, we will do the following process: \[(1,k+1), (2,k+1)\ldots (k, k+1); (1,k+2), (2,k+2), \ldots (k-1, k+2), (1, k+3), \ldots (k-2, k+3) \ldots (1,2k-1), (2, 2k-1), (1,2k)\]Where when we add players $k+i$, we will take the games $(1,k+i), (2, k+i), \ldots (k-i+1, k+i)$. For the next $\frac{k(k-1)}{2}$ games, we take \[(2,2k), (3,2k-1), (3,2k), \ldots \]where we will add $(i, 2k-i+2), (i, 2k-i+1), \ldots (i, 2k)$ in that order as we range from $i = 2$ to $i = k$. Finally, for the last $\binom{k}{2}$, we will pair players $(k+1, k+2), \ldots (2k-1, 2k)$, where whenever we finish the $\binom{i}{2}$ games in this section, we will next to games $(k+1, k+i+1), (k+2,k+i+1),\ldots (k+i,k+i+1)$ I claim this works. Observe that if $a_{i}$ was the day the ith player to enter the tournament, and $b_{i}$ was the day the ith player left the tournament, then the cost for the committee is \[\sum_{i=1}^{2k} (b_{i} - a_{i} + 1)\]Thus, the sum for the following is \[k\binom{2k}{2} - 2\sum_{i=0}^{k-1}\binom{i}{2} + \sum_{i=1}^{k}i^{2}\]\[= k^{2}(2k-1) -2\binom{k}{3} + \frac{k(k+1)(2k+1)}{6} = \frac{k(k+1)(2k+1)}{6} + k^{2}(2k-1) - \frac{2k(k-1)(k-2)}{6}\]\[= \frac{k(2k^2 + 3k + 1 - 2k^2 + 6k - 4}{6} + k^2(2k-1) = \frac{k(3k-1)}{2} + k^2(2k-1) = \frac{k(4k^2 + k - 1)}{2}\]Now, we show that this is minimal. Observe that \[b_{1} - a_{n} = 0 = 1^2 - 1\]\[b_{2} - a_{n-1} = 3 = 2^2 - 1\]\[b_{i} - a_{n-i+1} = i^2 - 1\]for $0 < i \leq k$. This is because, for $i$, there are players $a_{n}, a_{n-1}, \ldots a_{n-i+1}$ that will enter. If $0 < i \leq k$, then there are at least $i^2$ games between the people who entered and the people who left. Therefore, $b_{i} - a_{n-i+1} = i^2 - 1$ for $0 < i \leq k$. Now, observe that $a_{i} \geq \binom{i-1}{2} + 1$ for $i\leq k$, since there are at most $i-1$ people who played games before the ith player showed up, so at most $\binom{i-1}{2}$ games. Similarly, $b_{i} \leq \binom{2k}{2} - \binom{2k-i}{2}$. Therefore, we have \[\sum_{i=1}^{2k} b_{i} - a_{i} + 1 = \sum_{i=1}^{k}b_{i} - a_{n-i+1}+1 + \sum_{i=k+1}^{2k} b_{i} - \sum_{i=1}^{k} a_{i} -1\]\[\geq \sum_{i=1}^{k} i^2 + \sum_{i=1}^{k} \binom{2k}{2} - \binom{i-1}{2} - \sum_{i=1}^{k} \binom{i-1}{2}\]This is the exact sum in our equality case. Therefore, we conclude that $\frac{k(4k^2 + k -1 )}{2}$ is minimal

Solved with the numerical answers for small $k$ given to me, because I never would have been able to figure out the construction or bound otherwise. The answer is $2k^3+\tfrac{k^2}{2}-\tfrac{k}{2}$. Construction: Number the players $1,\ldots,2k$. First, have the players $1, \ldots, k$ arrive in order and play everyone else already present. For instance, in the case of $k=4$, the matches are $(1,2),(1,3),(2,3),(1,4),(2,4),(3,4)$ in that order, where $(x,y)$ denotes players $x$ and $y$ playing. Then, have the players $k+1,\ldots,2k$ arrive in that order, such that when player $k+i$ arrives, they play players $1,\ldots,k+1-i$ in that order before the next player arrives. For $k=4$, the matches are $(1,5),(2,5),(3,5),(4,5),(1,6),(2,6),(3,6),(1,7),(2,7),(1,8)$. Next, have players $1, \ldots, k$ depart in that order, and before player $i$ departs have them play against players $2k+2-i, \ldots, 2k$ in that order (that is, all the players they haven't played against yet). For $k=4$, the matches are $(2,7),(3,7),(3,8),(4,6),(4,7),(4,8)$. Finally, players $k+1,\ldots, 2k$ depart in order and play everyone they haven't yet played against before leaving. For $k=4$, the matches are $(5,6),(5,7),(5,8),(6,7),(6,8),(7,8)$. In the proof of the bound, the necessary calculations will be carried out (note that this construction achieves the necessary equality cases). Proof of Bound: Number the players are $1,\ldots,2k$ in the order by which they arrive. Note that all players must arrive before any can leave. We first prove the following claim: Claim: We may assume WLOG that the players depart in the order $1,\ldots,2k$ as well. Proof: Clearly it suffices to show that if $a$ arrives before $b$ (so $a<b$) but departs after, we may swap the two such that $a$ ends up arriving when $b$ used to, and $b$ ends up arriving when $a$ used to, without changing the number of coins paid. Suppose there is a match $(a,x)$ that occurs after $b$ leaves, so the match $(b,x)$ occurs after $b$ arrives but before they leave. Then replace $(a,x)$ with $(b,x)$ and vice versa. Doing this to all matches $(a,x)$ yields the desired result. $\blacksquare$ Now let $f(n)$ denote the number of coins the committee pays to house player $n$ in the hotel. Using the assumption in the above claim, we now prove the following key bound: Claim: We have $f(i)+f(2k+1-i)\geq 2k^2-k-2+3i$ for $1 \leq i \leq k$. Proof: Note that \begin{align*} f(i)+f(2k+1-i)&=\binom{2k}{2} + \text{number of days between $2k+1-i$ arriving and $i$ departing}\\ &- \text{number of days before $i$ arrives} - \text{number of days after $2k+1-i$ arrives} \end{align*}where the second term on the RHS is inclusive. There are at most $\binom{i-1}{2}$ days before $i$ arrives, and $\binom{i-1}{2}$ days after $2k+1-i$ departs. Further, there are at least $i^2$ matches which occur between $2k+1-i$ arriving and $i$ departing, namely any $(x,y)$ such that $x \leq i$ and $2k+1-i\geq 2k+1-i$, since between these two events we must also have $2k+2-i,\ldots,2k$ arrive and $1,\ldots,i-1$ depart. Therefore, it follows that $$f(i)+f(2k+1-i)\geq \binom{2k}{2}+i^2-2\binom{i-1}{2}=2k^2-k-2+3i,$$as desired. To finish, realize that by the above bound the committee must pay $$\sum_{i=1}^{2k} f(i)\geq\sum_{i=1}^{k} (2k^2-k-2+3i)=2k^3-k^2-2k+\frac{3k(k+1)}{2}=2k^3+\frac{k^2}{2}-\frac{k}{2}$$coins to the hotel, which is the desired bound. $\blacksquare$ Remark: The consideration of $f(i)+f(2k+1-i)$ is the key step once you've found the construction (although the latter step took me significantly longer, even when I knew the bound quickly due to being told values). The reasoning for pairing up the players this way is because simply reversing the order of the matches wouldn't change the amount of coins being paid, but in a system where players are ordered by arrival time would mess up the values of $f(i)$ individually. However, such a reversal doesn't change $f(i)+f(2k+1-i)$, which combined with the fact that we're working with an even number of players suggested to me to consider that quantity.

The answer is $\frac{4k^3+k^2-k}{2}$. First, we give a construction. Also, this is going with players numbered $1$, $2$, $3$, . . . $2k$. Now, here is the construction. First, let the players $1$ through $k$ arrive with player 1 arriving first, 2 second, . . . , player $k$ arriving $k$th, and have these players each play everyone else that is there on their arrival. Then, have the polayers $k+1,k+2,...,2k$ arrive in that order, such that when player $k+x$ arrives, he plays $1,2,...,k+1-x$ in that order before the next player gets there. Finally, have players $1$ through $k$ leave in that order, where each player plays all of the players they haven't played against yet, where they start with the lowest number player and end with the highest number player. Then, let the players $k+1$ through $2k$ leave in order and play everyone left. Now we show that this satisfies the bound. Let $x_i$ be the day the $i$th player enters tournament and $y_i$ be the day $i$th player leaves, then we have that the number of coins that they has to pay is $\sum_{i=1}^{2k}(y_i-x_i+1)$. \[=k\binom{2k}{2} - 2\sum_{i=0}^{k-1}\binom{i}{2} + \sum_{i=1}^{k}i^{2}\]which is equal to the answer. Now, we show that this is minimal. In order to do this, we bound $y_i-x_i+1$. Before $x_i$, there were at max $\binom{i}{2}$ games of StarCraft, and after $y_i$, there were also at max $\binom{i}{2}$ games played. So we have for $i\leq k$: \[x_i\geq \binom{i-1}{2}+1\]and likewise, \[y_i \leq \binom{2k}{2}-\binom{2k-i}{2}\]. Also, we have \[y_{i} - x_{n-i+1} = i^2 - 1\]because for players $n,n-1,...,n-i+1$ and $0\leq i\leq k$ there are at least $i^2$ between the people who came in and those who left. Then we have \[\sum_{i=1}^{2k} y_{i} - x_{i} + 1 = \sum_{i=1}^{k}y_{i} - x_{n-i+1}+1 + \sum_{i=k+1}^{2k} y_{i} - \sum_{i=1}^{k} x_{i} -1 \geq \sum_{i=1}^{k} i^2 + \sum_{i=1}^{k} \binom{2k}{2} - \binom{i-1}{2} - \sum_{i=1}^{k} \binom{i-1}{2}\]. which is equal to the equality case.

The answer is $k(4k^2+k-1)/2$. The construction is definitely the hardest part of this problem and it's not really obvious that it yields the required bound, so I wonder why people are excluding all of the details on that.

The answer is $\frac{k}{2} \cdot (4k^2+k-1)$ Bound: For each $i \in \{1,2, \cdots 2k\}$, define $a_i$ to be the number of days in which there are $i$ people in the hotel. We see that the cost, call it $c$, is equal to $\sum_{i=1}^{2k} ia_i$. Claim: The following inequalities hold: \begin{align} a_1 + a_2 + \cdots + a_i \le 2{i \choose 2}, \quad 2 \le i \le k \\ a_{2k} + a_{2k-1} + \cdots + a_{2k-i} \ge (i+1)^2 , \quad 0 \le i \le k-1 \end{align}Proof: Before all players have entered, there can be at most $i \choose 2$ days where there are less than $i$ players and similarly for after all players have entered. This proves the first inequality. Now consider the last $i+1$ players to enter. During the period in which there are at least $2k-i$ people in the hotel, each of the last $i+1$ players to enter must play against the first $i+1$ players to leave, unless these players are themselves one of the first $i+1$ players to leave, in which case they must play against all the other players during this period, which is clearly more than $i+1$. Hence there will be at least $(i+1)^2$ games played during this period, yielding the second inequality. We now use a smoothing argument. Suppose one of the above inequalities was not an equality, say when $i=j$. If $j \le k$, decreasing $a_{j+1}$ by $1$ and increasing $a_j$ by $1$ decreases the cost, while maintaining all inequalities (if $j > k$, then we can decrease $a_j$ by 1 and increase $a_{j-1}$ by 1). Hence, at least for the bound, we may as well assume that all the inequalities in (1) and (2) are sharp. Thus we have, \begin{align} a_i = 2(i-1) \quad \text{ and } \quad a_{2k+1-i}= 2i-1 \tag{*} \end{align}We can now compute the cost. \begin{align*} c = \sum_{i=1}^{2k} ia_i &= \sum_{i=1}^{k} 2i(i-1) + (2k+1-i)(2i-1) \\ &= \sum_{i=1}^{k} \left(4{i \choose 2} + (2k+1)(2i-1) - 2i^2 + i \right) \\ &= 4{{k+1} \choose 3} + k^2(2k+1) - \frac{k(k+1)(2k+1)}{3} + \frac{k(k+1)}{2} \\ &= \frac{k}{2} \cdot (4k^2+k-1) \end{align*}after some algebra. Construction: It suffices to show that a tournament exists in which the equalities in $(*)$ hold. Number the players $1,2 \cdots 2k$. First, 2 plays against 1. Then 3 plays against 1, then against 2, and so on, with $i$ playing against $1,2,\cdots i-1$ in that order. This continues until $i=k$. After this, $k+1$ plays against players $1$ through $k$, $k+2$ plays against $1$ through $k-1$, and so on until $2k$ plays against $1$. Then $2k$ will play against all remaining players, similarly with $2k-1 \cdots k+1$. It can be checked that the equalities in $(*)$ hold, hence we are done.

Let $f_j,l_j$ be the last day of player $j$. I am asked to minimize the value of $$\sum\limits_{j=1}^{2k} (l_j-f_j+1)$$ The key idea is to sort $f_1\le f_2\le \cdots\le f_{2k}, l_{\pi(1)} \le l_{\pi(2)} \le \cdots \le l_{\pi(2k)}$ Where $f_i,l_i$ corresponds to the same player, call $i$. Let $A_j=\{2k-j+1, \cdots, 2k\}, B_j=\{\pi(1),\cdots,\pi(j)\}$ and $c_j=|A_j\cap B_j|$ Claim: $$l_{\pi(j)}-f_{2k-j+1} + 1 \ge (j-c_j)^2 + c_j (2k-1) - \binom{c_j}{2}$$ Proof: We divide the game into three types: The first type is between players in $A_j\backslash B_j$ and $B_j\backslash A_j$. $j-c_j$ players need to play against $j-c_j$ players, for a total of $(j-c_j)^2$ games. The second type counts games where at least one player is in $A_j\cap B_j$. These players need to enter and leave, so they must each play $2k-1$ games. However, this overcounts the $\binom{c_j}{2}$ games where both players are from $A_j\cap B_j$ We note $c_j = |A_j|+|B_j|-|A_j\cup B_j| \le 2j-2k$. We can see this quadratic is minimized when $c_j\in \{2j-2k, 2j-2k+1\}$. Equality can be obtained if we let $\pi=id$. We can have the following arrangement: First have players $1,\cdots,k$ play each other, with player $j$ entering only after player $j-1$ has played against $1,\cdots,j-2$ in this order. Then for $k+1\le j\le 2k$, have it play players $1$ to $2k+1-j$. Then for $2\le j\le k$, have it play players $2k$ to $2k+2-j$ in descending order of label. Finally, have player $j$ play against $j+1,\cdots,2k$ and leave for $k+1\le j\le 2k$. This yields an answer of $(1^2+\cdots+k^2)+(1^2+\cdots+(k-1)^2) + (2+4+\cdots+2k)(2k-1) - \binom 22 - \binom 42 - \cdots - \binom{2k}{2} = k(k+1)(2k-1) - \frac 12 (2^2+4^2+6^2+\cdots+(2k)^2) + 1+\cdots+k = 2(1+\cdots+k^2)-k^2+k(k+1)(2k-1) - 2(1+\cdots+k^2)+\frac{k(k+1)}{2}$ $=\frac{k(2k+2)(2k-1)-2k^2+k(k+1)}{2} = \frac{k(4k^2+k-1)}{2}$

We claim that the answer is $\frac{k(4k^2+k-1)}{2}.$ This is achievable through the following steps: let the players be $P_1,P_2,\dots,P_{2k}.$ $P_1$ through $P_k$ arrive in order, each facing the ones already arrived. Then, $P_{k+1}$ and $P_{2k}$ arrive in order, $P_{k+i}$ facing $P_1,P_2,\dots,P_{k+1-i}$. Then, in order, each of $P_2$ to $P_k$ faces the ones they haven't already faced and then leaves. Finally, in order, $P_{k+1}$ through $P_{2k}$ leaves before fighting all the players still there. Let $1=a_1=a_2\le a_3\le \dots \le a_{2k}$ be the arrival dates, in order. Let $d_{2k}\le d_{2k-1}\le \dots = d_2=d_1= \binom{2k}{2}$ be the departure dates, in order. Then, our cost is $(d_1-a_1)+(d_2-a_2)+\dots+(d_{2k}-a_{2k})+2k.$ Note that $a_i\ge \binom{i-1}{2}+1$ and $d_i\le \binom{2k}{2}-\binom{i-1}{2}$ so \[(d_1-a_1+1)+(d_2-a_2+1)+\dots+(d_k-a_k+1)\ge \frac{k}{3}(5k^2-2)\]Now, between the $n$th person arriving and the $2k+1-n$th person departing, note that there are $(2k+1-n)^2$ people departing, so those must face everyone who arrives at the same time as, or later than the $n$th arrival, and there are $2k+1-n$ of them, so $d_{n}-a{n}+1\ge (2k+1-n)^2.$ Thus, \[(d_{k+1}-a{k+1}+1)+\dots+(d_{2k}-a_{2k}+1)\le \frac{k}{6}(2k^2+3k+1).\]Summing gives result.

The answer is $2k^3 + \tfrac{1}{2}k^2 - \tfrac{1}{2}k$. Let $x_1 \leq x_2 \leq \cdots \leq x_{2k}$ be the arrival times, in increasing order. Let $y_{2k} \leq y_{2k-1} \leq \cdots \leq y_1$ be the leaving times. We seek a lower bound and corresponding construction for \[\sum_{i = 1}^{2k}(y_i - x_i + 1).\] We first introduce a bound (that will be effective for $i \leq k$) on $y_i - x_i + 1$, motivated by the first few matches. Bound 1: $y_i - x_i + 1 \geq k(2k-1) - 2\tbinom{i-1}{2}$. Proof. Since there could only have been $i-1$ players before day $x_i$, we have $x_i \leq \tbinom{i-1}{2} + 1$. Similarly, $k(2k-1) - y_i \leq \tbinom{i-1}{2}$. Summing gives the desired bound. $\square$ Next, we introduce another bound (that will be effective for $2k-i \geq k+1$), motivated by the mid-game matches. Bound 2: $y_{2k-i} - x_{2k-i} + 1 \geq (i+1)^2$. Proof. Let $X$ be the set of contestants arriving on day $x_{2k-i}$ or later, and $Y$ be the set of contestants leaving on $y_{2k-i}$ or earlier. Let $X \cap Y = Z$ and let $j = |Z|$. Since between day $x_{2k-i}$ and day $y_{2k-i}$, all matches containing at least contestant in $Z$ must be played and all matches between $X \setminus Z$ and $Y \setminus Z$ must be played. Thus, \[y_{2k-i} - x_{2k-i} + 1 \geq (i+1-j)^2 + j(2k) - \binom{j}{2} \geq (i+1)^2,\]where the last inequality is due to $j \leq i+1 \leq k$. $\square$ Using these two bounds, we find our final bound: \[\sum_{i = 1}^{2k}(y_i - x_i + 1) \geq \sum_{i=1}^k(k(2k-1)-2\tbinom{i-1}{2}) + \sum_{i = 0}^{k-1}(i+1)^2 = 2k^3 + \tfrac{1}{2}k^2 - \tfrac{1}{2}k.\] The construction can be done inductively. Here is an overview. The first $\tbinom{k}{2}$ days see players $1$ through $k$ playing each other in order, with a new player joining as soon as all games between existing players have exhausted. In order, player $k+i$ arrives and plays players $1$ through $2k+1-i$ for $1 \leq i \leq k$. Then, in order, player $i+1$ plays players $2k+1-i$ through $2k$ and leaves for $1 \leq i \leq k-1$. The last $\tbinom{k}{2}$ days are constructed symmetrically to the first $\tbinom{k}{2}$.

What a strange problem. Let $a_i$ denote the $i$th arrival date from the start, and let $d_i$ be the $i$th arrival from the end. Then the cost is $\sum d_i-a_i+1$. I claim that we have $d_i-a_i+1 \ge {{2k}\choose{2}}-2{{i-1}\choose{2}}+{{2i-2-2k}\choose{2}}$. This is because there are ${2k}\choose{2}$ total games, and at most ${i-1}\choose{2}$ matches have occurred before or after $a_i$ and $d_i$. However, if $i>k+1$, then there are at least $2i-2-2k$ overlap between the sets of people who arrived before $a_i$ and left after $d_i$, so we have to add this back in. This gives us a bound of $$\sum_{i=1}^{2k} {{2k}\choose{2}}-2{{i-1}\choose{2}}+{{2i-2-2k}\choose{2}}$$$$=2k{{2k}\choose{2}}-2{{2k}\choose{3}}+\sum_{i=0}^{k-1} i(2i-1)$$$$=2k{{2k}\choose{2}}-2{{2k}\choose{3}}+\frac{k(k-1)(2k-1)}{3}-\frac{k(k-1)}{2}$$$$=2k^3+\frac{k^2}{2}-\frac{k}{2}$$. Now it suffices to find a construction that achieves $d_i-a_i+1={{2k}\choose{2}}-2{{i-1}\choose{2}}+{{2i-2-2k}\choose{2}}$. This proceeds in four phases. First, allow the first $k$ players to join, and after each one joins, have them play everyone else. Similarly, the fourth phase will be the players $k+1$ through $2k$ playing everyone else, and then leaving. This achieves equality in for $i$ between $1$ and $k$. The second phase consists of players $k+1$ through $2k$ joining, and as each player $k+i$ joins, they play all players from $1$ through $k+1-i$. The third phase consists of the players $1$ through $k$ leaving in order, and playing the rest of their matches before doing so. Remark: the hard part of the construction (the middle $k^2$ matches) is equivalent to placing the numbers $1$ through $k^2$ in a $k$ by $k$ square, and we are trying to minimize the sum of the biggest element of each row minus the smallest element of each column. I'm not sure how helpful this interpretation is, but it is certainly interesting.

didn't solve, but after playing minecraft bedwars i am ready to recreate the solution. Assume that the arrival times for players are $a_1\le \dots \le a_{2k}$. Furthermore assume the departure times are $b_1\ge \dots \ge b_{2k}$. The advantage of doing this is that we really just need the sum $(b_1+\dots+b_{2k})-(a_1+\dots+a_{2k})$ to be minimal, and we can find upper bounds on $a_i$ (similarly for $b_i$). We can actually get the upper bound $a_i-1\le \binom{i-1}{2}$. (This is pretty easy, most of the things from here on are very motivated by just playing around.) Similarly we get the lower bound $b_i\ge \binom{2k}{2}-\binom{i-1}{2}$. Construction is also easy to find from here as we probably expect construction to be symmetric so it makes sense to have two $k$-cliques and then easy experimentation gives the rest. Now the point is that (we can get this from the construction) for $i>k$ this bound is extremely suboptimal. (If it held for all, in fact, we'd even get a straight up $2k$-cliqueish construction!) So we should be able to make this a little better. In fact, $b_i-a_i$ shouldn't be negative at all, which gives some nice motivation. That means we need to figure out the overcount here. (HOLY SMOKES. THIS TOOK ME LIKE 30 MINUTES TO FIGURE OUT.) For the sake of me-being-really-stupid-and-needing-visuals, we show this as follows: before $a_i$, games only come from \[a_1,a_2,a_3,\dots,a_{i-1}\]and after $b_i$, games only come from \[b_{i-1},b_{i-2},b_{i-3},\dots,b_1.\]But now the issue is the following: if all of these players play, then some players will play twice! (I think I got something like this when solving, and thought nothing of it. Oops.) So what's the "final pool" of games we could take from? Well, it would be $2\binom{i-1}{2}$. However we know that there are really $2i-2$ values here, which means that at least $2i-2-2k$ people appear twice. That means we need to subtract $\binom{2i-2-2k}{2}$. Okay, so we need to show that our double $k$-clique construction actually fits the bill here. Luckily, intuition tells us it probably works, especially since $134$ is indeed the answer after spamming sums. Yay symmetry! The full result is \[\sum_{i=1}^{2k}\left(\binom{2k}{2}-2\binom{i-1}{2}+\binom{2i-2-2k}{2}\right)\]which is \[2k\binom{2k}{2}-2\binom{2k}{3}+\sum_{i=1}^{k-1} (2i^2-i)\]which is \[2k^2(2k-1)-\frac{2k(2k-1)(2k-2)}{3}+\frac{(k-1)(k)(2k-1)}{3}-\frac{k(k-1)}{2}\]which is \[\frac{1}{6}\left(12k^2(2k-1)-4k(2k-1)(2k-2)+2k(k-1)(2k-1)-3k(k-1)\right)\]which is \[\frac{1}{6}\left(24k^3-12k^2-16k^3+24k^2-8k+4k^3-6k^2+2k-3k^2+3\right)\]which is \[\frac{1}{6}\left(12k^3+3k^2-3k\right)\]which is \[\frac{1}{2}\left(4k^3+k^2-k\right)\]and we are done.

Answer: $\frac{k(4k^2 + k - 1)}{2}$. Firstly, we'll prove that the minimum cost is at least $\frac{k(4k^2 + k - 1)}{2}$. Let $a_1 \le a_2 \le \dots \le a_{2k}$ be the arrivals of the players and let $b_{2k} \le b_{2k-1} \le \dots b_1$ be the departures of the players. Since there are exactly $i-1$ players arrived before $i$th players arrives, so there are at most $\binom{i-1}{2}$ matches before $a_i$th day, which means $a_i \le \binom{i-1}{2} + 1$ for all $i$. Similarly we get $b_i \ge \binom{2k}{2} - \binom{i-1}{2}$. Hence $b_i - a_i + 1 \le \binom{2k}{2} -2\binom{i-1}{2}$ for all $i$ (1). Now we'll improve the bound for $i-1 > k$. List the $i-1$ players who arrived first and list the $i-1$ players who departed last. Then at least $2(i-1) - 2k$ players appeared in both lists. The matches between these players counted twice in (1), hence $b_i - a_i + 1 \le \binom{2k}{2} -2\binom{i-1}{2} + \binom{2(i-1) - 2k}{2} = (2k-(i-1))^2$. Now summing these inequalities, we get $\sum_{i=1}^{2k} b_i - a_i + 1 \le \sum_{i=1}^{k+1} \binom{2k}{2} -2\binom{i-1}{2} + \sum_{i=k+2}^{2k} (2k-(i-1))^2 = \frac{k(4k^2 + k - 1)}{2}$. Now we'll construct an optimal tournament. Let $1, 2, \dots, 2k$ be the players. Then the following construction satisfies the condition: $(1,2), (1,3), (2,3), (1,4), (2,4), (3,4), \dots (1,k), (2,k) \dots (k-1, k), (1, k+1), (2, k+1), \dots (k, k+1), (1, k+2), (2, k+2), \dots, (k-1, k+2), \dots (1, 2k-1), (2, 2k-1), (1, 2k), (2, 2k), (3, 2k-1), (3, 2k), (4, 2k-2), (4, 2k-1), (4, 2k) \dots (k, k+2), (k, k+3), \dots, (k, 2k), (k+1, k+2), (k+1, k+3), \dots (k+1, 2k), (k+2, k+3), (k+2, k+4), \dots, (k+2, 2k), \dots (2k-1, 2k)$. In the above construction, we see that $a_i = \binom{i-1}{2} + 1$ for $1 \le i \le k$, $a_i = (i-k-1)(k+1) - \frac{(i-k)(i-k-1)}{2} + \binom{k}{2} + 1$ for $k + 1 \le i \le 2k$ and $b_i = \binom{2k}{2} - \binom{i-1}{2}$ for $1 \le i \le k$, $b_i = \binom{k}{2} + \frac{k(k+1)}{2} + \frac{(2k-i)(2k-i+1)}{2}$ for $k + 1 \le i \le 2k$. Therefore we get $\sum_{i=1}^{2k} b_i - a_i + 1 = \frac{k(4k^2 + k - 1)}{2}$. Hence we're done. $\blacksquare$

The answer is $\dfrac{k(4k^2+k-1)}{2},$ with construction being separating the players into group $A$ of $k$ players and $B$ players, and getting the first $A$ players to play each other with each successive player playing everyone already arrived. Index players in $A$ from $1$ to $k.$ Then each player in group $B$ plays the first $k,k-1,k-2$ etc. players in $A$ until player $B_k$ plays $A_1.$ Then $B_k$ plays $A_2,$ $B_k$ and $B_{k-1}$ play $A_2,$ $B_k$ till $B_{k-3}$ play $A_3$ until all $A$ players are gone. Then the remaining $B$ player eliminate one player each time successively, like the reverse of what group $A$ has done. For the bound, label $a_n$ and $b_n$ as the times when the $n$th player arrives and the $n$th player leaves, where the player that arrives on $a_n$ does not have to be the same as the one leaves on $b_n,$ and observe the upper bound must be the sums of all $b_n-a_n.$ Observe $b_{2k}-a_{2k}=1$ as a player can be eliminated on the same day while the other arrives. In fact, $b_{i}-a_i=(2k-i+1)^2$ for $k+1 \le i \le 2k,$ as there are $2k-i+1 \le k$ players arriving between $a_i$ and $b_i$ and $k$ need to be eliminated. Each eliminated player must play against at least $2k-i+1$ players, as if they were already in the hotel they must play $2k-i+1$ games, while if they were not in the hotel before $a_i$ then they have to play $k$ players. Then for $a_i$ where $1 \le i \le k,$ the bound is $\binom{2k}{2}-2\binom{i-1}{2}$ as the optimal case is when the first and last $i-1$ players all play each other. Summing, we have \[k \cdot \binom{2k}{2} - \sum_{i=1}^{k-2} (i)(i+1) + \sum_{i=1}^k k^2\]which is also \[k^2(2k-1)-\dfrac{(k-1)(k-2)}{2}+(k-1)^2+k^2\]and expanding yields the bound as desired.

local brainrot go brrrrrrrrrr. Don't think anyone has noted this but the naive example of $12, 13, 14, 23, 24, 34$ actually has equality hold for $k = 1, 2$ which is pretty unpleasant. We claim the answer is $S_k = \frac{k(4k^2 + k - 1)}{2}$. We will bound the answer which will also serve as our construction. Represent the $\binom{2k}{2}$ days as the interval $[0, \binom{2k}{2}]$. Let the players be $p_1, p_2, \dots, p_{2k}$. For each $i = 1, 2, \dots, 2k$, we define $T_i = [s_i, t_i + 1)$ as the interval of positions from the morning of the starting day $s_i$ and night of ending day $t_i$ of each player $p_i$ (think of it as a bucket). Claim: All these intervals $T_i$ must intersect. Proof. Any two intervals intersect, so this can be proven inductively. $\blacksquare$ We then order $s_i$ from smallest to largest and $t_i$ from largest to smallest, breaking ties arbitrarily. For each $p_i$, we define $a_i, b_i$ as the position of $s_i, t_i$ in the ordering, so $\{a_1, a_2, \dots, a_{2k}\} = \{1, 2, \dots, 2k\}$. We now consider fixing the intervals and instead placing game matches $g_1, g_2, \dots, g_{\binom{2k}{2}}$ between these intervals, with the game between $a, b$ in $I_a \cap I_b$. The number of payment needed is then the sum of the number of games in each interval. Summing over games, we consider how much intervals a game must lie in. Claim: For two intervals $I_{i} = [s_i, t_i+1)$ and $I_j = [s_j, t_j+1)$, we get that the game between $i$ and $j$ is contained in at least \[ \min(\max(a_i, a_j), \max(b_i, b_j)) \]intervals, and equality can hold. Proof. Let all the intervals intersect at time $o$ which is nonintegral, so we can assume that $s_i < o < t_i$ for all $i$. If the game between $i$ and $j$ lies in $[\max(s_i, s_j), o]$, then it lies in at least $\max(a_i, a_j)$ with equality at the least possible time (with some casework to show that breaking ties doesn't matter since a player who played later must be among $p_i, p_j$). Similarly, a game in $(o, \min(t_i, t_j))$ lies in at least $\max(b_i, b_j)$ intervals. $\blacksquare$ The number of games is at least \[ \sum_{1 \le i < j \le 2k} \min(\max(a_i, a_j), \max(b_i, b_j)) \]which has equality when taking the game between $i$ and $j$ according to above. We finish by the following claim: Claim: Let $a_1, a_2, \dots, a_n$ and $b_1, b_2, \dots, b_n$ be permutations of $\{1, \dots, n\}$. Then \[ \sum_{1 \le i < j \le 2k} \min(\max(a_i, a_j), \max(b_i, b_j)) \ge S_k \]where equality holds (at least) whenever $a_i + b_i = n+1$ for all $i$. Proof. We define $f(a_i) = b_i, f(i) = t_i$, and reorder the sum so it is equivalent to lower bound \[ \sum_{1 \le i < j \le 2k} \min(j, \max(t_i, t_j)) \ge S_k. \]If $t_i < t_{i+1}$ for $i < {i+1}$, then swapping $t_i, t_{i+1}$ decreases the size because for fixed $k \not\in \{i, i+1\}$, since we have that \begin{align*} &\min(\max(k, i+1), \max(t_k, t_{i+1})) + \min(\max(k, i), \max(t_k, t_i)) \ge \\ &\min(\max(k, i+1), \max(t_k, t_i)) + \min(\max(k, i), \max(t_k, t_{i+1})) \end{align*}as equality holds if $k > i+1$, and if $k < i$ this becomes \begin{align*} &\min(i+1, \max(t_k, t_{i+1})) + \min(i, \max(t_k, t_i)) \ge \\ &\min(i+1, \max(t_k, t_i)) + \min(i, \max(t_k, t_{i+1})) \end{align*}which holds since $\max(t_k, t_{i+1}) \ge \max(t_k, t_{i})$. As such, equality is tight when $f(a_i) = n=1 - a_i$, so we want to compute \[ S_k = \sum_{1 \le i < j \le 2k} \min(j, n+1-i) \]which means that by considering this as a grid that \[ 2S_k + k(k+1) = (2k+1)\cdot(2k^2) \]and solving for $S_k$ gives the claim. $\blacksquare$