В вольере 33 собаки. За соревнования жюри хочет вы- ставить им единицы и двойки (каждой по оценке), причём так, чтобы у любых двух собак, соседних в списке приюта, была на двоих хотя бы одна двойка (т.е. нельзя ста- вить две единицы подряд). Сколькими способами жюри сможет это сделать? Решите эту задачу, чтобы не пришлось проверять экспериментально.

задан 15 Окт '17 10:10

изменен 15 Окт '17 10:10

"Решите эту задачу, чтобы не пришлось проверять экспериментально" - !!!

(15 Окт '17 12:07) EdwardTurJ

Это задача о количестве двоичных последовательностей, в которых не встречаются цифры 11 подряд. Если x(n) -- количество таких последовательностей длиной n, то x(1)=2, x(2)=3. Далее справедливо рекуррентное соотношение для чисел Фибоначчи, так как последовательность длиной n>=3 оканчивается либо на 2, либо на 21, откуда следует формула x(n)=x(n-1)+x(n-2). В итоге имеем x(n)=F_{n+2}.

(15 Окт '17 12:36) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,103
×398
×295
×148
×37

задан
15 Окт '17 10:10

показан
267 раз

обновлен
15 Окт '17 12:36

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru