|
|
 |
Условие
По кругу стоят n мальчиков и n девочек. Назовём пару из мальчика и девочки хорошей, если на одной из дуг между ними стоит поровну мальчиков и девочек (в частности, стоящие рядом мальчик и девочка образуют хорошую пару). Оказалось, что есть девочка, которая участвует ровно в 10 хороших парах. Докажите, что есть и мальчик, который участвует ровно в 10 хороших парах.
Решение
Заметим, что на любой дуге между членами хорошей пары поровну девочек и мальчиков.
Пусть D – девочка, участвующая в 10 хороших парах. Обозначим всех детей по часовой стрелке K1, K2, ..., K2n так, что K1 – это D, и продолжим нумерацию циклически (например, K0 = K2n и K2n+1 = K1). При i = 1, 2, ..., 2n обозначим через di разность между количествами девочек и мальчиков среди K1, K2, ..., Ki; в частности, d1
= 1 – 0 = 1 и d2n = 0 (поэтому можно продолжить эту последовательность, полагая d2n+1 = d1 и т. д.). Девочка D образует с Ki хорошую пару тогда и только тогда, когда di = 0 и Ki – мальчик, то есть di = 0 и di–1 = 1. Итак, найдутся ровно 10 индексов i с такими свойствами.
Рассмотрим любого мальчика M = Ks, образующего с D хорошую пару; тогда ds= 0 и ds–1 = 1. Аналогично получаем, что мальчик M образует хорошую пару с Ki ровно тогда, когда ds = di–1 и
Ki – девочка (то есть di–1 = 0 и di = 1).
Заметим, что любые два числа di и di+1 отличаются на единицу. Разобьём их на группы последовательных чисел, не меньших единицы, и группы последовательных чисел, не больших нуля. Тогда при обходе круга по часовой стрелке "переходов" из первых групп во вторые будет столько же, сколько и "переходов" из вторых групп в первые. Значит, у M столько же хороших напарниц, сколько у
D хороших напарников. Это и требовалось доказать.
Замечания
1. Это решение можно визуализировать, нарисовав "график" последовательности (di). Тогда появление хорошего напарника у D означает, что график пересекает прямую d = ½ сверху вниз, а появление хорошей напарницы у M – пересечение той же прямой снизу вверх.
2. Из решения следует, что если девочка образует хорошую пару с двумя мальчиками, то любая девочка, образующая хорошую пару с одним из этих мальчиков, образует её и с другим. Более того, все дети разбиваются на непересекающиеся группы (в каждой группе поровну мальчиков и девочек) так, что каждый мальчик образует хорошие пары со всеми девочками из своей группы и только с ними, и то же верно для любой девочки. При этом, при обходе по кругу мальчики и девочки из одной группы чередуются. Существуют решения, доказывающие этот факт напрямую (например, индукцией по числу детей).
