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

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

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

Паросочетание - это набор попарно несмежных рёбер в графе, рассмотрим граф $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}$.

Задача вполне просто решается без графов.

Разобьём множество камушков на пары с суммами масс $4n+1$. Обозначим как $(a,b)$ пару, цвета камней которой $a,b$(или одну из них, если таких несколько). Задача сводится к тому, чтобы записать пары в строку следующим образом: $(c_1,c_2)(c_2,c_3)...(c_{4n-1},c_{4n})(c_{4n},c_1)$, ведь закинув четные по счёту пары камней в одну кучу, а нечётные в другую, получим что в кучках очевидно равное камушков одинакового цвета и равная масса.

Начнём с любой пары $(a_1,a_2)$. Теперь пусть мы уже выписали $(a_1,a_2)\dots(a_{k-1},a_k)$. Заметим, что цвет $a_k$ был выписан, либо 1, либо 3 раза. То есть, кроме выписанных остался по крайней мере 1 камушек цвета $a_k$, и следовательно пара, содержащая его. Таким образом мы можем выписать все пары - что требовалось доказать

То же решение можно провести с графами. Рассмотрим псевдограф из $n$ вершин. Будем проводить ребро $(i,j)$, если существуют два камушка с суммой масс $4n+1$ цветов $i,j$. Степень каждой вершины $4$ - чётна, тогда граф содержит эйлеров цикл. Можно убедится, что отсюда следует задача(например, можно записать в строку, как показано в решении выше)

рассмотрим $2n$ пар вида $(i,4n+1-i)$, сумма каждой из этих пар равна $4n+1$. Составьте граф из $n$ вершин, каждая вершина которого соответствует цвету, и для каждой пары нарисуйте ребро между цветами двух чисел пары. Это приводит к графу из $n$ вершин, где каждая вершина имеет степень $4$ (однако допускается наличие нескольких ребер и петель). Достаточно показать, что в этом графе есть подграф, где каждая вершина имеет степень $2$, мы просто возьмем соответствующие $n$ пары подграфа в одну стопку и остальные $n$ пары в другую стопку. Кроме того, мы можем предположить, что WLOG связен, поскольку мы можем обрабатывать каждый компонент связности отдельно и «добавлять» подграфы, полученные для каждого компонента связности, чтобы получить подграф для нашего исходного графа. Поскольку граф связен и каждая вершина имеет четную степень, он имеет эйлеров цикл и число ребер четное. Теперь просто возьмем чередующиеся ребра эйлерова цикла. Если в вершине $v$ нет петель, за ребром типа $av$ должно следовать ребро типа $vb$ ($a,b$ не обязательно должны быть разными), и мы видим, что полученное подграф будет иметь $v$ степени $2$. Если в нем один цикл, за $av$ должен следовать $vv$, а затем $vb$ для некоторого $b$. Мы снова видим, что полученный подграф имеет $v$ степени $2$. Если в подграфе есть $2$ петли, то $v$ — изолированная компонента связности и в подграфе есть одна $vv$ петля. Итак, мы видим, что процесс приводит к подграфу, в котором каждая вершина имеет степень $2$, чего мы и хотели. Итак, мы закончили.