19.18 Инварианты и полуинварианты

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

Разобьём весь коридор на такие тройки. Количество “занятых” троек не превосходит числа пианистов, и “занятые” тройки не освобождаются, следовательно, пианисты никогда не покидают некоторую ограниченную часть коридора. С другой стороны, сумма квадратов номеров комнат, в которых живут пианисты (с учетом кратности) при каждом переселении возрастает, поскольку . Значит, когда-нибудь переселения прекратятся.