ВсОШ 2019, 10 класс, задача 3
В межгалактической гостинице есть комнат вместимостью человек. В этих комнатах суммарно живёт человек. В гостиницу приехал -гость, для которого нужно освободить целую комнату. Для этого директор гостиницы выбирает одну комнату и переселяет всех её жителей в одну и ту же другую комнату. При каком наибольшем директор гостиницы всегда может таким образом освободить комнату независимо от текущего расселения?
(Д. Белов, А. Сафиуллина)
Ответ
Ответ.
.
Решение.
Предположим, что при постояльцах директор не может осуществить переселение. Разобьём комнаты на пары по вместимости: . Отметим, что для каждой пары комнат суммарное количество человек, живущих в двух комнатах, больше, чем вместимость большей комнаты из пары, иначе всех человек из этой пары можно было бы собрать в комнате с большей вместимостью. Таким образом, общее количество человек не меньше . Поэтому при постояльцах директор может освободить комнату. Теперь приведём пример, доказывающий, что при и более постояльцах существует расселение, в котором освободить комнату указанным образом не удастся. Упорядочим комнаты по возрастанию вместимости. Пусть в первых пятидесяти комнатах живёт по , а в комнате вместимости при живёт человек. Посчитаем количество человек, живущих в гостинице: . Рассмотрим две произвольные комнаты вместимости . Заметим, что в комнате вместимости живёт не меньше человек, а в комнате - не меньше человек. Таким образом, переселить людей из одной комнаты в другую ни для какой пары комнат не удастся, поэтому пример подходит. Если , то достаточно селить оставшихся людей поочерёдно в любые комнаты, где ещё остаются свободные места.