There are $300$ participants to a mathematics competition. After the competition some of the contestants play some games of chess. Each two contestants play at most one game against each other. There are no three contestants, such that each of them plays against each other. Determine the maximum value of $n$ for which it is possible to satisfy the following conditions at the same time: each contestant plays at most $n$ games of chess, and for each $m$ with $1 \le m \le n$, there is a contestant playing exactly $m$ games of chess.
Problem
Source: Dutch IMO TST3 2019 p4
Tags: combinatorics, max, graph theory
28.01.2020 04:56
We claim that the answer is $\boxed{200}.$ Interpret the problem as a graph theory problem in the obvious way. First let's construct this. First let's divide the set of participants into two sets $A, B$ so that $|A| = 100$ and $|B| = 200.$ Label the people in $A$ as $a_1, a_2, \cdots, a_{100}$ and the people in $B$ as $b_1, b_2, \cdots, b_{200}.$ For each $1 \le i \le 100$, we let $a_i$ be connected to $b_1, b_2, \cdots, b_{100+i}$ and nobody else. Then it's easily seen that $a_i$ has degree $100+i$ and $b_{201-i}$ has degree $i$ for each $1 \le i \le 100$. Now we will show that $200$ is maximal. Suppose that some value $n > 200$ worked. Let $v$ be the vertex with degree $n > 200.$ Note that each of the opponent of $v$ must have degree at most $300-n$, as else $v$ would have a common opponent with one of them. As $n > 200$, this means that there are at most $300-n$ participants who have played at least $100$ games. However, as $n - 100 > 300-n$ this is a contradiction. Hence, the answer is $\boxed{200}$ as claimed. $\square$
02.02.2020 21:24
Let $G $ be a graph with $300$ vertices, represents $300$ contestants. Between any $2$ vertices, if we draw a corresponding edge if $2$ corresponding contestants have played a macth against each other. If $n_{\max}=m>=201, $ choose vertice $X $ with degree $m $, $\deg(X)=m $. From $X $, we can note that there are $m $ edges. $$X-Y_1,X-Y_2,\cdots,X-Y_{200},X-Y_{201},\cdots,X-Y_m$$. There no edges as $Y_i-Y_j $. Otherwise, it will be $\triangle XY_iY_j $. Besides $X,Y_i , $ the remaining $\text {k-vertices}$ are $Z_1,Z_2,\cdots,Z_k $, and $k=300-1 (X)-M (Y_i)$. $M>=201\implies k=< 300-1-201\implies k=<98$. If we take one vertice $Y_i $, then $Y_i $ is connected to $X $. $Y_i-Y_j $ edge does not exist. $Y_i $ is connected to $\text {maximum k Z-type vertices}\implies\deg (Y_i)=<1+k,k=< 98\implies\deg (Y_i)=< 99$. Graph $G $ consists vertices with $\text {degree} k\in\left (100,101, \cdots,200\right)$ must be vertices $\in\left (Z_1,Z_2,\cdots,Z_k\right); k=< 99$. There is $101$ different degree values $=< 99$. We have $\textbf{Z-type} $ vertices. A contradiction. We have, $m=<200$, $n_{\max}=200$. Construct a graph $G $, satisfying with $n_{\max}=200$. It have $300$ vertices into $3$ rows. In each row, it will move \[\textbf {Left}\mapsto\textbf {Right}\]$\text {Row 1}=\boxed {X} $ $\text {Row 2}=\boxed {Y_1},\boxed {Y_2},\cdots,\boxed{Y_{200}} $ $\text {Row 3}=\boxed {Z_1},\boxed {Z_2},\cdots,\boxed {Z_{99}} $ At the beginning, there is no single edge in graph $G $. Connecting $X\implies Y_1,Y_2,\cdots,Y_{200}\implies \deg (X)=200$ $Z_1\implies Y_1,Y_2\cdots,Y_{199}\deg (Z_1)=199+Z_2\to Y_1,Y_2,\cdots,Y_{198}\deg (Z_2)=198$ $(X)+(Z_1)+(Z_2)+\cdots+(Z_{99}) =\left (Y_1,Y_2,\cdots,Y_{200}\right)+\left (Y_1,Y_2,\cdots,Y_{199}\right)+\cdots+\left (Y_1,Y_2,\cdots,Y_{101}\right) =\deg (X)+\deg (Z_1)+\deg(Z_2)+\cdots+\deg (Z_{99}) =200+199+198+\cdots+101$ At this point, $\deg (X)=200,\deg (Z_1)=199,\deg (Z_2)=198,\cdots,\deg (Z_{99})=101$ If we take $\textbf {Y-type} $ vertices in $\textbf{Row 2} $ from $\textbf {Right}\mapsto\textbf {Left}$, at each $\text{Y-vertice} $, note $Y_{200}+Y_{199}+Y_{198}+\cdots+Y_{101} =X:\deg (Y_{200})+X;Z_1:\deg (Y_{199})+X,Z_1,Z_2:\deg (Y_{198})+\cdots+X,Z_1,Z_2,\cdots,Z_{99}:\deg (Y_{101}) =1+2+3+\cdots+100$ Hence, each degree's value in range of $\textbf {1-100} $ is also paired with a unique $\textbf {Y-type} $ vertice.
05.01.2023 17:57
parmenides51 wrote: There are $300$ participants to a mathematics competition. After the competition some of the contestants play some games of chess. Each two contestants play at most one game against each other. There are no three contestants, such that each of them plays against each other. Determine the maximum value of $n$ for which it is possible to satisfy the following conditions at the same time: each contestant plays at most $n$ games of chess, and for each $m$ with $1 \le m \le n$, there is a contestant playing exactly $m$ games of chess.