Процессы и алгоритмы
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
Есть бесконечно много комнат в ряд, в некоторых живут пианисты (всего их конечное число, в комнате может жить несколько пианистов). Каждый день одна пара пианистов в соседних комнатах решает, что они мешают друг другу играть, и разъезжается — левый пианист в соседнюю комнату слева, а правый пианист — в соседнюю комнату справа. Докажите, что через некоторое время переселения прекратятся.
Рассмотрим произвольные три подряд идущие комнаты (с номерами 
). Если в одной из них когда-нибудь окажется
пианист, то эта тройка комнат уже никогда не опустеет: чтобы покинуть эту тройку, пианист должен переселиться из 
-й комнаты в
-ю (или из 
-й в 
-ю, что рассматривается аналогично), но тогда кто-то переселяется из 
-й в 
-ю, и
на этом шаге рассматриваемая тройка комнат непуста. Разобьём весь коридор на тройки (например, тройки вида (
) для целых 
). Количество «занятых» троек не превосходит количества пианистов, и «занятые» тройки не
освобождаются, следовательно, пианисты никогда не покидают некоторую ограниченную часть коридора. С другой стороны,
сумма квадратов номеров комнат, в которых живут пианисты (с учетом кратности) при каждом переселении возрастает,
поскольку
Но в силу ограниченности той части коридора, где находятся пианисты, сумма квадратов номеров не может возрастать бесконечно. Значит, когда-нибудь переселения прекратятся.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
