Лягушка прыгает по вершинам шестиугольника $%ABCDEF$%.Прыгать она может только в соседние вершины.Сколькими способами за $%n$% прыжков можно из вершины $%A$% попасть в вершину $%C$% ?

У меня получилось уравнение $%f(n+4)=5f(n+2) -4f(n)$%

Решение $%f(n) = 2^{n-3}((-1)^n+1)$%

Но ответ не совпадает с верным,в чем ошибка?

задан 11 Сен 22:26

изменен 11 Сен 22:26

10|600 символов нужно символов осталось
0

За n прыжков она может попасть из A в C только при чётном n. Поэтому при нечётном n ответ равен нулю, а при n=2k она может попасть в A, С или E. Ввиду симметрии, число способов попасть в С и E одинаково.

Обозначим через a(k) число способов попасть из A в A за 2k шагов, и через c(k) число способов попасть в C или E. Нас далее будет интересовать величина c(k)/2.

Ясно, что a(0)=1, c(0)=0. При k>=0 имеем a(k+1)=2a(k)+c(k), а также с(k+1)=2a(k)+3c(k). Рекуррентное уравнение для второй последовательности имеет вид c(k+2)-5c(k+1)+4c(k)=0, то есть характеристические корни равны 4 и 1. Соответственно, получится линейная комбинация их n-х степеней.

Окончательно для числа путей из A в C получится 0 при нечётном n, а при чётном будет (2^n-1)/3.

ссылка

отвечен 11 Сен 23:53

изменен 12 Сен 2:18

1

@falcao: Спасибо,значит тут опечатка?

(12 Сен 0:27) joker

@joker: нет, это я "намудрил". Дело в том, что я сложил вместе число путей в C и E, обозначив через c(k), но тогда первое рекуррентное уравнение будет a(k+1)=2a(k)+c(k). Тогда рекуррентная формула будет как у Вас, и характеристические корни там 4 и 1. То есть это будет c4^n+d. В итоге ответ получается как по ссылке.

Прошу прощения за путаницу. Чуть позже могу исправить.

(12 Сен 2:00) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×4,520
×1,300

задан
11 Сен 22:26

показан
48 раз

обновлен
12 Сен 2:18

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

по почте:

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

по RSS:

Ответы

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

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