Question

В одной из вершин треугольника сидит лягушка. Она прыгает по вершинам треугольника, перемещаясь каждый раз в одну из соседних вершин. Сколькими способами лягушка может попасть в начальную вершину за 9 прыжков?

Answer 1

Перебираем все варианты комбинаций, 1 - прыжек вперед, 0 - прыжек назад
Получается что это те варианты, когда колво прыжков в одну сторону кратно 3

# Код на ruby 2.2.3p173
count = 0
for i in 0..2**9-1
    s = ("000000000"+i.to_s(2))[-9..-1]
    vertix = 0
    s.chars.each {|c|
        vertix = (vertix + (c == "1" ? 1 : -1)) % 3 ;
        # p [c, vertix]
    }
    if vertix == 0
        p s
        count += 1
    end
end
p count

Ответ 170

Answer 2

Для решения этой задачи можно использовать метод динамического программирования.

Пусть F(n) - количество способов, которыми лягушка может попасть в начальную вершину за n прыжков.

Заметим, что чтобы лягушка попала в начальную вершину за n прыжков, она должна на предыдущем шаге быть в одной из двух соседних вершин. Таким образом, можно составить следующее рекуррентное соотношение:

F(n) = F(n-1) + F(n-2)

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

Изначально, когда лягушка находится в начальной вершине, F(0) = 1 (единственный способ - остаться в начальной вершине).

Используя это рекуррентное соотношение, можно последовательно вычислить значения F(1), F(2), ..., F(9) и найти количество способов, которыми лягушка может попасть в начальную вершину за 9 прыжков.

F(1) = F(0) = 1 F(2) = F(1) + F(0) = 1 + 1 = 2 F(3) = F(2) + F(1) = 2 + 1 = 3 F(4) = F(3) + F(2) = 3 + 2 = 5 F(5) = F(4) + F(3) = 5 + 3 = 8 F(6) = F(5) + F(4) = 8 + 5 = 13 F(7) = F(6) + F(5) = 13 + 8 = 21 F(8) = F(7) + F(6) = 21 + 13 = 34 F(9) = F(8) + F(7) = 34 + 21 = 55

Таким образом, лягушка может попасть в начальную вершину за 9 прыжков 55 различными способами.