ЗАДАЧА 495 Кузнечик прыгает по вершинам правильного

УСЛОВИЕ:

Кузнечик прыгает по вершинам правильного треугольника ABC, прыгая каждый раз в одну из соседних вершин. Сколькими способами он может попасть из вершины A обратно в вершину A за 11 прыжков?

РЕШЕНИЕ:

Обозначим через an, bn, cn число способов переместиться за n прыжков в точку A, B, C соответственно, начиная из точки A. Из соображений симметрии, bn=cn, так как в любом маршруте можно поменять роли B и C.

Очевидно, что an+1=bn+cn=2bn, так как в точку A можно прийти или из B, или из C. Аналогично, bn+1=an+cn=an+bn из тех же соображений. Непосредственно ясно, что b0=0, b1=1, и при этом имеет место рекуррентное соотношение bn+2=an+1+bn+1=bn+1+2bn. Для нахождения формулы общего члена здесь имеются стандартные способы, но их можно избежать следующим образом. Попытаемся найти несколько первых членов последовательности bn (n?0), и угадать общую закономерность, которую далее станет можно доказать методом математической индукции.

Последовательность получается такая: 0,1,1,3,5,11,21,…. Здесь каждый следующий член примерно в два раза больше предыдущего, поэтому имеет смысл сравнить нашу последовательность с последовательностью степеней двойки: 1,2,4,8,16,32,64,…. Видно, что у второй последовательности каждый член примерно втрое больше. Поэтому рассмотрим утроенную последовательность 3bn, члены которой равны 0,3,3,9,15,33,63,…. Сравнивая с последовательностью степеней двойки, мы видим, что она получается из 3bn прибавлением последовательности 1,?1,1,?1,…, для которой формула общего члена равна (?1)n (напомним, что последовательности у нас нумеруются с нулевого члена). Таким образом, для нескольких первых членов последовательности верна формула 3bn=2^n?(?1)^n, то есть bn=(2^n?(?1)^n)/3. Остаётся подставить эти значения в рекуррентную формулу и убедиться в справедливости этого равенства для всех n?0, применяя метод математической индукции.

С учётом того, что an=2bn?1 при n?1, имеем окончательный ответ
an=(2^n+2?(?1)^n)/3.
При n=0 формула также даёт верное значение a0=1.
В нашем случае n=11
ВОПРОСЫ ПО РЕШЕНИЮ?
НАШЛИ ОШИБКУ?
отправить + регистрация в один клик
опубликовать + регистрация в один клик

ОТВЕТ:

682

Нужна помощь?

Опубликовать

Добавил slava191 , просмотры: ☺ 1422 ⌚ 17.01.2014. математика 10-11 класс
КОД ВСТАВКИ

РЕШЕНИЯ ПОЛЬЗОВАТЕЛЕЙ
Написать своё решение

Только зарегистрированные пользователи могут писать свои решения.

РЕШЕНИЕ ОТ slava191

Подобная задача!

Кузнечик
Кузнечик прыгает по вершинам правильного треугольника ABC, прыгая каждый раз в одну из соседних вершин. Сколькими способами он может попасть из вершины A обратно в вершину A за 12 прыжков?

Решение:
Пусть кузнечик может совершить 1 прыжок, тогда число способов вернуться в вершину A равно 0, число способов попасть на вершину B равно 1.
Пусть всего 2 прыжка. Тогда число способов попасть обратно равно 2, а число способов попасть на вершину B равно 1.
Пусть A(k) - число способов вернуться в вершину A за k прыжков, B(k) - число способов попасть на вершину B за k прыжков. Тогда получаем, что A(k+1)=B(k)+C(k)=2B(k).
Также B(k+1)=A(k)+C(k)=A(k)+B(k)
(C(k) аналогичный показатель для вершины C, очевидно, что C(k)=B(k))
Итак, имеем два рекуррентных соотношения: A(k+1)=2B(k),B(k+1)=A(k)+B(k)
A(1)=0,B(1)=1,A(2)=2,B(2)=1,A(3)=2,B(3)=3 и т.д. Получаем A(12)=1366.

Ответ: 1366.
ЕСТЬ ВОПРОСЫ?
НАШЛИ ОШИБКУ?
отправить + регистрация в один клик
опубликовать + регистрация в один клик

НАПИСАТЬ КОММЕНТАРИЙ

Мы ВКонтакте
Последние решения

vk220074590 ✎ Приведём верное написание: вЕрховье—ПГ орнамЕнт—НГ отбИрает—ЧГ кОснулся—ЧГ вырАстающий—ЧГ Слово верховье проверяем словом верх. Ответ: верховье. к задаче 26838

vk220074590 ✎ Найдем вероятность того, что неисправны оба автомата. Эти события независимые, вероятность их произведения равна произведению вероятностей этих событий: 0,05 · 0,05 = 0,0025. Событие, состоящее в том, что исправен хотя бы один автомат, противоположное. Следовательно, его вероятность равна 1 − 0,0025 = 0,9975. Ответ: 0,9975. к задаче 26837

vk220074590 ✎ Поскольку биатлонист попадает в мишени с вероятностью 0,8, он промахивается с вероятностью 1 − 0,8 = 0,2. Cобытия попасть или промахнуться при каждом выстреле независимы, вероятность произведения независимых событий равна произведению их вероятностей. Тем самым, вероятность события «попал, попал, попал, промахнулся, промахнулся» равна 0,8*0,8*0,8*0.2*0,2=0,02 Ответ:002 к задаче 26836

vk220074590 ✎ Возможность выиграть первую и вторую партию не зависят друг от друга. Вероятность произведения независимых событий равна произведению их вероятностей: 0,5 · 0,3 = 0,15. Ответ: 0,15. к задаче 26835

vk220074590 ✎ log3 (x+7) < log3 (5-x) + log3 (3-x) ОДЗ: (-7:3) log3(x+7)/(5-x)(3-x) < 0 ((x+7)/(5-x)(3-x)-1) < 0 (-x^2+9x-8)/(x^2-8x+15) < 0 x^2-9x+8=0 x1=8 x2=1 если отметить точки на координатной прямой, то с учетом ОДЗ получится интервал (-7:1] Ответ : (-7:1] к задаче 26833