|
|
 |
Условие
По одной стороне бесконечного коридора расположено бесконечное количество комнат, занумерованных числами от минус бесконечности до плюс бесконечности. В комнатах живут 9 пианистов (в одной комнате могут жить несколько пианистов), кроме того, в каждой комнате находится по роялю. Каждый день какие-то два пианиста, живущие в соседних комнатах (k-й и (k+1)-й), приходят к выводу, что они мешают друг другу, и переселяются соответственно в (k–1)-ю и (k+2)-ю комнаты. Докажите, что через конечное число дней эти переселения прекратятся. (Пианисты, живущие в одной комнате, друг другу не мешают.)
Решение
Рассмотрим произвольные три подряд идущие комнаты (с номерами n, n + 1, n + 2). Если в одной из них когда-нибудь окажется пианист, то эта тройка комнат уже никогда не опустеет: чтобы покинуть эту тройку, пианист должен переселиться из n-й комнаты в (n–1)-ю (или из (n+2)-й в (n+3)-ю, что симметрично), но тогда кто-то переселяется из (n+1)-й в (n+2)-ю, и на этом шаге рассматриваемая тройка комнат непуста.
Разобьём весь коридор на такие тройки. Количество "занятых" троек не превосходит 9, и "занятые" тройки не освобождаются, следовательно, пианисты никогда не покидают некоторую ограниченную часть коридора.
С другой стороны, сумма квадратов номеров комнат, в которых живут пианисты (с учетом кратности) при каждом переселении возрастает, поскольку k² + (k + 1)² < (k – 1)² + (k + 2)². Значит, когда-нибудь переселения прекратятся.
Замечания
Идеология. Интуитивно утверждение задачи довольно понятно: распределение пианистов становится все более "разреженным". Когда оно станет совсем "разреженным", переселения должны прекратиться, потому что соседствующих пианистов не останется. Нужно только придать этим рассуждениям строгую форму.
12 баллов.
