Европейская математическая олимпиада среди девочек (EGMO). 2017 год. Швейцария

Пусть $n \geq 1$ — целое число и $t_{1} < t_{2} < \ldots < t_{n}$ — положительные целые числа. В группе из $t_{n}+1$ человек некоторые сыграли между собой в шахматы. Два человека могли сыграть между собой не более одной партии. Докажите, что могло оказаться так, что одновременно будут выполняться два условия:
   (i) Количество игр, сыгранных каждым человеком — одно из чисел $t_{1}, t_{2}, \ldots, t_{n}$.
   (ii) Для каждого $i$, такого, что $1 \leq i \leq n$, найдётся человек, который сыграл ровно $t_{i}$ партий.

Комментарий/решение

Решение:

Переведим задачу на язык графов где люди это вершины и игры это ребра между вершинами (обозначим граф как $G(V,E)$). То есть на доказать что для любых последовательных натуральных чисел $t_1<t_2<…<t_n$ в графе на $t_n+1$ вершинах может выполнятся два условие одновремено:

$1) \forall u \in V$

$d(u) \in [t_1,t_2,…,t_n]$ где $d(v_j)$-степень вершины $v_j$.

$2) \forall j \in [1,n], \exists u \in V$ так что $d(u)=t_j$

Решим с помощью индукции для $n$.

База:

Для $n=1$, просто возьмем граф на $t_1+1$ вершинах где все вершины имеют ребро между собой тогда $\forall v_j \in V$ выполняется $d(v_j)=t_1$ что нам и нужно.

Переход: ($n \Rightarrow n+1$)

Так как по предположению индукции для любых $n$ последовательных чисел это работает тогда возьмем граф $G’=(V’,E’)$ где $|V’|=t_n-t_1+1$ и $\forall u \in V’$ выполняется $d(u) \in [t_2-t_1,t_3-t_1,…,t_n-t_1]$. Теперь добавим к нему еще граф $H$ состоящий из $t_{n+1}-t_n$ изолированных вершин, и граф $K$ из $t_1$ вершин каждая из которых имеет ребро со всеми вершина из графов $G’,H,K$. Тогда заметим что степень каждой вершины из графа $G’$ поднялась на $t_1$ то есть $\forall v \in V’ , d(v) \in [t_2,..,t_n]$. И таже степень каждой вершины в графе $H$ ровно $t_1$ и степень каждой вершины в графе $K$ ровно $t_{n+1}$ что доказывает переход.