Закл до 2015
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
На бесконечной в обе стороны полосе из клеток, пронумерованных целыми числами, лежит несколько камней (возможно, по нескольку в одной клетке). Разрешается выполнять следующие действия:
- Снять по одному камню с клеток
и 
и положить один камень в клетку 
- Снять два камня с клетки
и положить по одному камню в клетки 
Докажите, что при любой последовательности действий мы достигнем ситуации, когда указанные действия больше выполнять нельзя, и эта конечная ситуация не зависит от последовательности действий (а зависит только от начальной раскладки камней по клеткам).
Источники:
Подсказка 1
Обозначим a(i) — количество камней в i-ой клетке. Будем говорить, что набор всех a(i) образует конфигурацию. Хотелось бы придумать инвариант, который не изменяется при разрешенных операциях. Каким мог бы быть этот инвариант?
Подсказка 2
Пусть x — некоторое число. Тогда назовем весом конфигурации число, равное бесконечной сумме по всем целым i чисел, равных произведению a(i) и i-ой степени x. Можно ли выбрать x так, чтобы вес не менялся при разрешенных операциях?
Подсказка 3
Конечно! Достаточно положить x > 1 таким, чтобы он удовлетворял равенству x² = x + 1. Попробуем теперь доказать, что любая последовательность действий конечна. Наибольший номер непустой клетки не может уменьшаться. А может ли он увеличиваться бесконечно?
Подсказка 4
Конечно, нет! Он не может стать больше такого n, что n-я степень x больше веса конфигурации! Следовательно, у нас обязательно найдутся клетки, с камнями в которых операции больше не происходят. Как тогда показать, что количество операций конечно?
Подсказка 5
Верно! Применим индукцию! База очевидно, а ранее мы уже увидели, что для камней с достаточно большими номерами операции не происходят. Что тогда можно сделать?
Подсказка 6
Точно! Можно убрать камни с большими номерами и применить индукцию. Остается показать, что конечная конфигурация от последовательности действий не зависит. Для этого стоит сначала понять, как может выглядить конечная конфигурация!
Подсказка 7
Да, в ней обязательно каждая клетка содержит не более одного камня и нет двух непустых клеток подряд. А могут ли две конечные конфигурации с таким свойством иметь одинаковый вес?
Обозначим через 
количество камней в клетке с номером 
Тогда последовательность 
задает конфигурацию — расположение
камней по клеткам. Пусть 
— корень уравнения 
больший 
Назовем весом конфигурации 
число 
Покажем, что разрешенные действия не меняют веса. Действительно,
Докажем индукцией по 
— числу камней, что любая последовательность действий завершается. При 
это верно. Пусть при числе
камней, меньшем 
утверждение верно. Рассмотрим процесс, начинающийся с конфигурации 
с 
Наибольший номер
непустой клетки при разрешенных действиях не уменьшается, но и расти бесконечно он не может — он не может превысить числа
при котором 
Значит, с какого-то момента наибольший номер непустой клетки перестает изменяться, и с
камнями, попавшими в эту клетку, уже ничего не происходит. Выбросим эти камни, и применим предположение индукции к
оставшимся.
В конечной конфигурации в каждой клетке не более одного камня, и нет двух непустых клеток подряд. Докажем, что любые две
конфигурации 
и 
с такими свойствами имеют разные веса. Пусть 
— наибольший номер, при котором 
пусть,
для определенности, 
Выбросим из 
и 
все камни с номерами, большими 
(они в 
и 
совпадают). Для
оставшихся конфигураций 
и 
имеем:
Таким образом, для любой конфигурации есть только одна конечная с таким же весом; только к ней и может привести процесс.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
