В одной из вершин треугольника сидит лягушка. Она прыгает по вершинам треугольника,...

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