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