Рекурренты в комбинаторике и числа Фибоначчи f(n)
Ошибка.
Попробуйте повторить позже
Некоторые клетки доски 
красятся в красный цвет так, чтобы ни одна красная клетка не имела соседей по стороне того же цвета.
Обозначим через 
количество таких раскрасок с четным числом красных клеток, через 
— с нечетным числом. Чему может быть
равно 
Подсказка 1
Глобально мы хотим выразить A_(n) через члены последовательностей A и B с меньшими индексами. Аналогично мы хотим поступить с B_(n) в надежде, что разность этих выражений будет красивым числом.
Подсказка 2
Как это сделать? Пусть закрашено четное число клеток. Давайте посмотрим на крайний столбец доски 2×n. Как выразить A_(n) через члены A и B с меньшими индексами, если клетки этого столбца не закрашены?
Подсказка 3
Если же закрашена одна клетка, то тогда придется рассмотреть случаи, как закрашены клетки в предпоследнем столбце и так дальше.
Разделим доски на два типа: обычные 
— доски 
и 
— доски 
с удаленной угловой клеткой. Дополнительно
найдем 
и 
— количества правильных раскрасок 
в четное и нечетное число цветов. Клетки будем нумеровать
буквой 
или 
соответствующей строке и числами от 
до 
— столбцы. Множество таких раскрасок разбивается на
три подмножества: 
закрашена, 
закрашена и ни одна из клеток 
не закрашена. Если закрашена 
то
и 
не закрашены. Среди остальных клеток правильным образом должно быть закрашено нечетное количество,
таким образом, в первом и втором случаях число раскрасок равно 
Если же обе клетки 
не закрашены,
то остальные должны быть раскрашены в четное количество, то есть в 
Таким образом, 
Аналогично
Пусть 
и 
Тогда 
Ясно, что 
и 
Находим
последовательно первые несколько членов 
и 
и 
Далее последовательности периодичны.
Таким образом, 
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
