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