A league consists of $2024$ players. A round involves splitting the players into two different teams and having every member of one team play with every member of the other team. A round is called balanced if both teams have an equal number of players. A tournament consists of several rounds at the end of which any two players have played each other. The committee organised a tournament last year which consisted of $N$ rounds. Prove that the committee can organise a tournament this year with $N$ balanced rounds. Proposed by Anant Mudgal and Navilarekallu Tejaswi
Problem
Source: The 1st India-Iran Friendly Competition Problem 1
Tags: combinatorics, algorithms
13.06.2024 00:13
A non-detailed sketch of solution. Replace $k=2024$ which is even. Take the graph interpretation. Let's prove that $N\geq \lceil log_2k\rceil$. Denote the set $S_i$ such that for the sets $A_i$ and $B_i$ which are created after $i.$ partition, WLOG $|S_{i-1}\cap A_i|\geq |S_{i-1}\cap B_i|$. Define $S_i=S_{i-1}\cap A_i$. (Take the larger set after every partition.) $|S_i|\geq \lceil \frac{k}{2^i}\rceil$ Hence, $N\geq \lceil log_2k \rceil$. Let's prove that we can organise $N$ balanced tournaments where $N\geq \lceil log_2k \rceil$. Divide vertices into two sets $X$ and $Y$ with equal number of members. In a partition if we divide $X$ into $a,b$ then we also divide $Y$ into $a,b$ and we group $(a,b)$ where we get equally sized sets.$\blacksquare$ Example: $\{1,2,3,4,5,6\}\rightarrow (\{1,2,3\}),(\{4,5,6\})\rightarrow (\{1,2\},\{6\}),(\{3\},\{4,5\})\rightarrow (\{1\},\{4\},\{6\}),(\{2\},\{3\},\{5\})$ Remark by erkosfobiladol: Let $k=2^n+2m$ such that $0< m<2^{n-1}$.Choose $2^{n-1}+m$ different binary codes consisting of $n$ digits. Write $1$ after their last digits. We have $2^{n-1}+m$ different binary codes with $n+1$ digits. Take their conjugates, then we have $2^n+2m$ binary codes. In $i.$ move, construct two sets such that the codes with their $i.$ digit $1$ are in the first set, and the codes with their $i.$ digit $0$ are in the second set. These partitions satisfy the conditions given in the problem.(If $m=0,$ then consider all binary codes with $n$ digits and apply the last procedure.) Example of Remark: $11,10,01\rightarrow 111,101,011\rightarrow 111,101,011,000,010,100$ We have $(111,101,100),(011,000,010), \ (111,011,010),(101,000,100) \ (111,101,011),(000,010,100)$.
13.06.2024 10:06
anantmudgal09 wrote: A league consists of $2024$ players. A round involves splitting the players into two different teams and having every member of one team play with every member of the other team. A round is called balanced if both teams have an equal number of players. A tournament consists of several rounds at the end of which any two players have played each other. The committee organised a tournament last year which consisted of $N$ rounds. Prove that the committee can organise a tournament this year with $N$ balanced rounds. Proposed by Anant Mudgal and Navilarekallu Tejaswi We may rephrase the problem as covering edges of the complete graph $K_{2024}$ by complete bipartite subgraphs of type $K_{x, 2024-x}$ as a tournament and doing so by only using subgraphs $K_{1012, 1012}$ as a balanced tournament. Label the vertices of $K_{2024}$ by $1, 2, \dots, 2024$. Suppose we have a tournament with rounds $G_1, \dots, G_N$, each $G_i$ being the disjoint union of sets $A_i$ and $A_i^c$ inside $\{1, 2, \dots, 2024\}$. Define $$\Delta = \sum_{i=1}^{2024} \left||A_i|-|A_i^c|\right |.$$We show that while $\Delta>0$, we can find another tournament with $N$ rounds while decreasing $\Delta$; once $\Delta = 0$, we get a balanced tournament. Indeed, pick a $G_i$ and assume without loss of generality $|A_i| < |A_i^c|$; we will try to transfer a $u \in A_i^c$ to $A_i$ to form a new round. This is always possible provided every edge from $u$ to members of $A_i$ occurs in another one of the rounds. If we successfully transfer $u$, $\Delta$ decreases and we're done, so we may instead assume there is a vertex $v_u \in A_i$ such that the edge $uv_u$ is not covered in any of the rounds. This must be true for all vertices $u \in A_i^c$, else, we can transfer some vertex $u$, and $\Delta$ decreases as desired. Since $|A_i^c|>|A_i|,$ by pigeonhole principle, there exists $u, w \in A_i^c$, and $v \in A_i$ such that $v=v_u=v_w$. Thus neither of the edges $vu, vw$ are in any of the rounds. So in each of the other rounds, $v, u$ and $v, w$ are on the same side of a partition, hence $u, w$ are always on the same side in each of the other rounds. Thus, $uw$ edge is never covered in any of the rounds including $A_i$! This is a contradiction. Thus the algorithm terminates with $\Delta=0$ as desired.
13.06.2024 10:27
where are the rest of the problems?
13.06.2024 13:24
Why cant us non pdcers take it
19.06.2024 18:11
Consider the graph with players as vertices. Two vertices are connected by an edge if they have not yet played together. The graph starts out at a complete clique and must end as a null graph. At any point the graph consists of a collection of disjoint cliques. After a round a cliques is broken into two parts determined by which players play on which team. We show that $11\leq N$ and there is a balanced construction for $N=11$. Bound: By induction after $n$ rounds their must be a clique of size at least $2024\cdot 2^{-n}$, thus $11\leq n$. Construction: We prove that in one round there exists a balanced tournament that reduces the maximal clique size from $m$ to $\lceil m/2 \rceil$. Notice there must be an even number of odd cliques. If a clique has an even number of players split them equally amongst the two teams. If a cliques has an odd number of players then split them almost equally amongst the teams with an equal number of odd cliques giving their extra player to each team.