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

Перебираем все варианты комбинаций, 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

if vertix = = 0

p s

count + = 1

end

end

p count

Ответ 170