ВсОШ 2021, 11 класс, задача 8
У каждой из девочек есть по шариков; среди этих шариков есть по шариков различных цветов. Две девочки могут обменяться, передав друг другу по шарику. Они хотят добиться того, чтобы у каждой девочки было по разноцветных шариков. Докажите, что они могут добиться этого такой серией обменов, чтобы любой шарик участвовал не более чем в одном обмене.
(И. Богданов, Ф. Петров)
Ответ
Решение.
Лемма.
Пусть - натуральное число, и у каждой из ста девочек имеется шариков, причем всего у них есть по шариков каждого из цветов. Тогда девочки могут выбрать каждая по одному из своих шариков так, чтобы все шариков были разных цветов.
Доказательство.
Будем говорить, что девочка дружит с цветом, если у нее есть шарик этого цвета. Заметим, что любые девочек дружат в совокупности хотя бы с цветами (иными словами, имеют шарики хотя бы различных цветов): иначе по принципу Дирихле среди их шариков какого-то цвета было бы более шариков. Тогда по лемме Холла можно сопоставить каждой девочке дружественный ей цвет так, чтобы все сопоставленные цвета были различны - а это нам и нужно.
Пусть теперь девочки придут на квадратное поле (для игры в большие классики), и каждая девочка выделит себе свой столбец, чтобы разложить в нем свои шарики - по одному на поле. Сначала они воспользуются леммой при , найдут у себя по шарику так, чтобы те были разного цвета, и выложат их в первой строке. Затем, применяя лемму при (к еще не выложенным шарикам), они найдут по шарику так чтобы те были разного цвета и выложат их во второй строке, и так далее. В результате в каждой строке оказываются шарики разных цветов, а в каждом столбце выложены шарики соответствующей ему девочки. Осталось заметить, что симметрия относительно диагонали этого поля приводит к тому что в каждом столбце лежат шарики разного цвета, и эта симметрия соответствует разрешенным обменам.