In a chess tournament there are $100$ players. On each day of the tournament, each player is designated to be ‘white’, ‘black’ or ‘idle’, and each ‘white’ player will play a game against every ‘black’ player. (You may assume that all games fixed for the day can be finished within that day.) At the end of the tournament, it was found that any two players have met exactly once. What is the minimum duration of days that the tournament lasts?
Problem
Source: Hong Kong TST - HKTST 2022 2.4
Tags: combinatorics
23.07.2024 17:14
(I wrote it by solving it in my head, probably the wrong solution, I will try again with pen and paper.) Claim:For $2n$ veritces at least $2n-1$ days are required From our induction hypothesis we know that it takes $2n-1$ days to construct the graph $K_{2n}$.Now let's take the vertices $v_i,v_j$ to show for $K_{2n+2}$. In this case we need $4n+1$ new edges.Also $2n$ vertices other than $v_i$ and $v_j $cannot match each other again.In this case, the next day let's paint $v_i $white and the remaining $ 2n+1$ vertices black and we will get $2n+1$ edges. Since $ v_j $does not create an edge with the vertices painted black the day before, let's throw $v_i $into the idle set the next day and paint $v_j$ black and paint the remaining $2n$ vertices white. In this case, we get $2n$ edge and $2$ days later we build $4n+1$ edge. So it takes $2n-1+2=2n+1$ days to construct $K_{2n+2}$Then, For $100$ vertices answer is $99$
14.09.2024 14:09
posting for storage