Международная олимпиада 2020, Санкт-Петербург, Россия, 2020 год


Имеется $4n$ камушков массами 1, 2, 3, $\ldots$, $4n.$ Каждый из камушков покрашен в один из $n$ цветов, причём имеется по 4 камушка каждого цвета. Докажите, что камушки можно разделить на две кучи равного суммарного веса так, чтобы в каждой куче было по два камушка каждого цвета.
посмотреть в олимпиаде

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

пред. Правка 2   2
2020-12-26 10:52:48.0 #

Паросочетание - это набор попарно несмежных рёбер в графе, рассмотрим граф $4 \times n$ (матрица $4$ столбца и $n$ строк) .

Изоморфизм графа - два графа называются изоморфными, если у них одинаковое число вершин (обозначим его n) и вершины каждого из них можно занумеровать так числами от 1 до n, что в первом графе две вершины соединены ребром тогда и только тогда, когда вершины с такими же номерами во втором графе соединены.

Лемма: В любом вышеупомянутом графе произвольное полное количество паросочетании, можно свести к двум подграфам $2 \times n$ (левый и правый) не имеющих общих ребер.

Доказательство: число паросочетании в графе $4 \times n$ равно $\dfrac{4n}{2}=2n$ .

Пусть имеется произвольный набор, этот набор паросочетании можно изоморфна "перенести" в другой граф, действительно меняя в каждой строке расположение вершин (происходит перенумерация номеров строк) не меняется изначальное содержание графа.$(1)$

Рассмотрим граф $2 \times n$ в этом графе существует конечное число всевозможных расположений паросочетании, пусть их количество будет $S$, тогда для второго симметричного графа так же $S$ , тогда всего различных расположении в графе $4 \times n$ равна $S \cdot S$ применяя $(1)$ получаем что произвольное расположение паросочетании в графе $4 \times n$ есть расположение паросочетании в подгафах $2 \times n$ .

1) Пусть масса всех равна $M$

К задаче: Пусть цвета графа равны $A_{1},A_{2},A_{3},...,A_{n}$ в скобках будем размещать камни, массы которых покрашены в эти цвета ($a_{ij}$ массы)

$$\begin{equation*} A = \left( \begin{array}{cccc} a_{11} & a_{12} & \ldots & a_{14}\\ a_{21} & a_{22} & \ldots & a_{24}\\ \vdots & \vdots & \ddots & \vdots\\a_{n1} & a_{n2} & \ldots & a_{n4} \end{array} \right) \end{equation*}$$

2) Так как $1+4n=2+4n-1=3+4n-2 = ... = 2n+2n+1$ , то есть сумма крайних равна $1+4n$, если представить $A$ в виде матрицы $4 \times n$ где массы будут вершинами и соединять одну вершины только с одной другой (паросочетания) так чтобы в сумме было $1+4n$ то есть для каждой вершины существует единственная вершина в сумме дающая $4n+1$.

Применяя лемму, получаем что c каждой строки графа будут взяты по две вершины (по два цвета) в сумме которые будут давать $\dfrac{\dfrac{1+4n}{2} \cdot 4n}{2} = (1+4n ) \cdot n = \dfrac{M}{2}$.