IMC 2018, Day 2, Problem 8
Let . A frog moves along the points of by jumps of length . For every positive integer , determine the number of paths the frog can take to reach starting from in exactly jumps.
Original from the official PDF

This transcription was compared symbol by symbol with the original, but not yet by a person.
Work for at least 45 minutes before opening the solution.
Official solution
(Proposed by Fedor Petrov and Anatoly Vershik, St. Petersburg State University)
Solution. Let . Notice that the map , is a bijection between the two sets; moreover projects all allowed paths of the frogs to paths inside the set , using only unit jump vectors. Hence, we are interested in the number of paths from to in the set , using only jumps and .
For every lattice point , let be the number of paths from to in with jumps. Evidently we have . Extend this definition to the points with and by setting
Along the line we have . Hence, the function
In particular, the number of paths of the frog from to is
Remark. There exist direct proofs for the formula . For instance, we can replicate the well-known proof of the formula for the Catalan numbers using the Cycle Lemma of Dvoretzky and Motzkin (related to the petrol station replenishment problem). See https://en.wikipedia.org/wiki/Catalan_number#Sixth_proof
Transcribed from the official solutions, pages 2–3. This transcription has not been checked a second time; if in doubt, look at the original.
Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.
How did it go?
Moves you mark come back sooner in triage.