(А. Брейк) Лягушке нужно добраться до укрытия, избегая опасностей. У Лягушки есть три действия:
1. Короткий прыжок +2
2. Длинный прыжок +3
3. Избежать опасности 2n
Первые два действия увеличивают позицию Лягушки на 2 и 3 соответственно. Третье действие можно применить только тогда, когда Лягушка находится в нечетной позиции — позиция N преобразуется в позицию 2N, позволяя Лягушке избежать опасности. Лягушка была замечена на расстоянии 3. Сколько существует различных путей Лягушки к укрытию в позиции 46, каждый их которых содержит не более двух действий «Избежать опасности»?