Всесиб 2026, отборочный этап, 9 класс, задача 5
( баллов) На банкет пришли гостей, каждый оставил в гардеробе пару галош и шляпу, все галоши и все шляпы были разного размера, скажем, от -ого до -ого, причём размеры галош и шляпы у гостя могли не совпадать. После банкета гости уходили строго по одному, каждый одевал случайную пару галош и шляпу размеров, не меньших собственных. В какой-то момент оказалось, что ни один оставшийся гость не может выбрать себе пару галош и шляпу размеров, не меньших собственных. Какое максимальное количество гостей могло при этом остаться?
Ответ
Ответ. .
Решение. Пример. Занумеруем гостей по размеру галош, пусть у первых десяти размер шляпы равен номеру галош, у вторых десяти размер шляпы на больше размера галош, а у последних десяти — на меньше. Если первыми уйдут первые десять, и каждый обуется и оденется в предметы, на размеров больше своего номера, то они унесут все шляпы размеров с по , поэтому оставшиеся гости из второго десятка не смогут найти себе подходящую шляпу, и также уведут все галоши размеров с по , поэтому оставшиеся гости из третьего десятка не смогут найти себе подходящую пару галош.
Оценка. Докажем, что, если осталось не меньше гостя, то, как минимум один из них сможет найти в гардеробе подходящие галоши и шляпу.
Рассмотрим сначала оставшихся гостей с самыми маленькими номерами, после -ого из них есть не менее оставшихся гостей с большими номерами, значит, у него не более, чем -ый размер галош, . С другой стороны, рассмотрим самых больших размеров оставшихся пар галош, перед -ой из них есть не менее оставшихся галош с меньшими номерами, значит, у неё не менее, чем -ый размер галош, . Следовательно, каждый их этих оставшихся гостей сможет найти себе подходящую пару галош.
Осталось заметить, что из этих оставшихся гостей найдётся один с размером шляпы не большим (минимальным, после него ещё гостей с большими размерами), а среди оставшихся шляпы найдётся шляпа размера не меньшего, чем (максимального, перед ней шляп меньшего размера). Вот этот гость и сможет её одеть и уйти.
Более вероятно, что оценка будет написана участниками проще. Пусть осталось не меньше гостя, тогда осталось и не меньше пары галош. Всего размеров , поэтому не меньше, чем размеров оставшихся галош совпадут с размерами ног некоторых из оставшихся гостей, обуем их в эти (их собственные!) галоши. Теперь рассмотрим этих обутых гостей, у них размеров голов, и осталась шляпа, поэтому не менее, чем размеров оставшихся шляп совпадут с размерами голов некоторых трёх из обутых оставшихся гостей. Любой из этих трёх гостей полностью экипирован и может покинуть сборище.
Заметим, что аналогичное рассуждение для оставшихся гостей уже не проходит на этапе выбора шляп. Причина в том, что этот уходящий гость может так выбрать галоши и шляпу, что оставшимся двум из рассмотренной троицы уже не удастся правильно одеться. Поэтому замечание в условии, что гости уходят строго по одному, существенно.