После каждого прыжка кузнечик может оказаться либо на точке с четной координатой, либо на точке с нечетной координатой. Количество способов дойти до точки с четной координатой за 9 прыжков равно количеству способов дойти до точки с нечетной координатой за 9 прыжков (так как количество прыжков четное).

Поэтому нам нужно найти количество способов дойти до точки с четной координатой за 9 прыжков и удвоить его. Рассмотрим несколько примеров:

Если кузнечик пройдет 0, 2, 4, 6 или 8 шагов, он останется на четной координате.Если кузнечик пройдет 1, 3, 5, 7 или 9 шагов, он окажется на нечетной координате.

Мы можем использовать сочетание с повторением (формула числа сочетаний с повторением: C(n+k-1, k-1)).

Итак, количество способов дойти до точки с четной координатой за 9 прыжков равно C(9+1-1, 1) = C(9, 1) = 9.

Удвоим это количество для точек с нечетной координатой, получим 18 точек, в которых кузнечик может оказаться, сделав ровно 9 прыжков, начиная прыгать из начала координат.