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

$n \geq 1$ — бүтiн және $t_{1}   (i) Әр адамның ойындарының саны келесi сандарының бiрi: $t_{1}, t_{2}, \ldots, t_{n}$.
   (ii) Кез келген $i$ саны үш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}$ что доказывает переход.