Закл (финал) 10 класс

Предположим, что при постояльцах директор не может осуществить переселение. Разобъём комнаты на пары по вместимости: Отметим, что для каждой пары комнат суммарное количество человек, живущих в двух комнатах, больше, чем вместимость большей комнаты из пары, иначе всех человек из этой пары можно было бы собрать в комнате с большей вместимостью. Таким образом, общее количество человек не меншше Поэтому при постояльцах директор может освободить комнату.

Теперь приведём пример, доказывающий, что при и более постояльцах существует расселение, в котором освободить комнату указанньм образом не удастся.

Упорядочим комнаты по возрастанию вместимости. Пусть в первых пятидесяти комнатах живёт по а в комнате вместимости при живёт человек. Посчитаем количество человек, живущих в гостинице:

Рассмотрим две произвольные комнаты вместимости Заметим, что в комнате вместимости живёт не меньше человек, а в комнате — не меньше человек. Таким образом, переселить людей из одной комнаты в другую ни для какой пары комнат не удастся, поэтому пример подходит. Если то достаточно селить оставшихся людей поочерёдно в любые комнаты, где ещё остаются свободные места.