допускает довольно широкое обобщение, также имхо красивое и интересное.
20 сортов пирожных по 10 пирожных каждого сорта упакованы в 20 ящиков по 10 пирожных в каждом. Доказать, что при любой такой раскладке всегда можно выбрать 20 пирожных двадцати различных сортов, выбрав по одному пирожному из каждого ящика.
Решение.
[Spoiler (click to open)]Действуем индукцией по числу К пирожных каждого сорта. Если К = 2 то это предыдущая задача(ну или - решается также).
Пусть теперь К > 2
Покажем, что если распределение пирожных таково, что искомый выбор возможен, то переложив местами любые 2 пирожных получим распределение, в котором также можно выбрать искомую "линию" - по одному пирожному каждого сорта взяв одно пирожное из каждого ящика.
Т к одно такое распределение всегда есть, и любое можно получить из любого другого последовательными перекладываниями, задача будет решена.
Итак, имеем укладку, в которой можно выбрать "линию". Убрав эту линию, получаем ту же задачу, но для К-1. В которой опять можно выбрать линию по предположению индукции! И т д - т е получаем для нашей раскладки набор из К линий! Теперь поменяв местами 2 пирожных видим, что мы задели максимум 2 линии - а их у нас больше двух! Т е остаётся нетронутая линия! Всё.
Восклицательные знаки - мой восторг :-)
Journal information