Question 59
Let $p$ be a prime number. Martin the frog is at position $0$ on the real line. Every second, Martin makes a move: he may stay where he is, jump by $1$ to the right on the line, or jump by $1$ to the left. Martin wants to be back at his initial position after $p-1$ moves: he denotes by $s_{p}$ the number of sequences of $p-1$ moves allowing him to return to his initial position. What is the remainder of $s_{p}$ modulo $p$?
For example, for $p=3$, $s_{p}=3$ since Martin can choose to stay where he is twice, to jump right then left, or to jump left then right.
For example, for $p=3$, $s_{p}=3$ since Martin can choose to stay where he is twice, to jump right then left, or to jump left then right.