СПбГУ 2022, отборочный этап, 10–11 классы, задача 10
( баллов) На бал пришли мальчиков и девочек, пронумерованных числами от до . Иногда мальчики и девочки танцевали (в танце участвуют пары из мальчика и девочки). После всех танцев оказалось, что для каждой девочки можно поделить всех мальчиков на две группы так, что суммарно с мальчиками из первой группы девочка танцевала столько же раз, сколько и с мальчиками из второй группы. Докажите, что для некоторого мальчик танцевал с девочкой не более половины всех своих танцев.
Ответ
Решение. Предположим, что для любого мальчик танцевал с девочкой более половины своих танцев. Тогда, суммируя по всем мальчикам, мы получим, что танцев между мальчиком и девочкой с одинаковыми номерами было больше, чем между мальчиками и девочками с разными номерами. Теперь посмотрим на ситуацию со стороны девочек. Мальчик попал в одну из двух групп мальчиков, с которыми девочка танцевала половину своих танцев. Значит, с мальчиком эта девочка танцевала не более половины всех своих танцев. Суммируя по всем , мы получим, что танцев между мальчиком и девочкой с одинаковыми номерами было НЕ больше, чем между мальчиками и девочками с разными номерами. Противоречие с доказанным ранее.