Задача 786
Бильярд

Диаграмма ниже показывает бильярдный стол особой четырехугольной формы. Четыре угла $A, B, C, D$ равны $120^\circ, 90^\circ, 60^\circ, 90^\circ$ соответственно, а длины $AB$ и $AD$ равны между собой.

Диаграмма слева показывает траекторию бесконечного малого бильярдного шара, начавшего движение из точки $A$, дважды отбившегося от бортов стола и вернувшегося обратно в точку $A$. Диаграмма справа показывает другую такую траекторию, но на этот раз шар отбился от бортов восемь раз:

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

Пусть $B(N)$ будет количеством возможных траекторий шара, начавшего движение из точки $A$, отбившегося не более $N$ раз от бортов и вернувшегося обратно в точку $A$.

Например, $B(10) = 6$, $B(100) = 478$, $B(1000) = 45790$.

Найдите $B(10^9)$.

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net