International Mathematics Competition

Let $\Psi=\left\{(u, v) \in \mathbb{Z}^{3}: v \geq 0, u \geq 2 v\right\}$. Notice that the map $\pi: \Omega \rightarrow \Psi$, $\pi(x, y, z)=(x+y, z)$ is a bijection between the two sets; moreover $\pi$ projects all allowed paths of the frogs to paths inside the set $\Psi$, using only unit jump vectors. Hence, we are interested in the number of paths from $\pi(0,0,0)=(0,0)$ to $\pi(n, n, n)=(2 n, n)$ in the set $\Psi$, using only jumps $(1,0)$ and $(0,1)$. For every lattice point $(u, v) \in \Psi$, let $f(u, v)$ be the number of paths from $(0,0)$ to $(u, v)$ in $\Psi$ with $u+v$ jumps. Evidently we have $f(0,0)=1$. Extend this definition to the points with $v=-1$ and $2 v=u+1$ by setting $f(u,-1)=0, \quad f(2 v-1, v)=0$. To any point $(u, v)$ of $\Psi$ other than the origin, the path can come either from $(u-1, v)$ or from $(u, v-1)$, so $f(u, v)=f(u-1, v)+f(u, v-1)$. If we ignore the boundary condition, there is a wide family of functions that satisfy this recurrence; namely, for every integer $c,(u, v) \mapsto\binom{u+v}{v+c}$ is such a function, with defining this binomial coefficient to be 0 if $v+c$ is negative or greater than $u+v$. Along the line $2 v=u+1$ we have $\binom{u+v}{v}=\binom{3 v-1}{v}=2\binom{3 v-1}{v-1}=2\binom{u+v}{v-1}$. Hence, the function $f^{*}(u, v)=\binom{u+v}{v}-2\binom{u+v}{v-1}$ satisfies the recurrence and boundary conditions and $f(0,0)=1$. These properties uniquely define the function $f$, so $f=f^{*}$. In particular, the number of paths of the frog from $(0,0,0)$ to $(n, n, n)$ is $f(\pi(n, n, n))=f(2 n, n)=\binom{3 n}{n}-2\binom{3 n}{n-1}=\frac{\binom{3 n}{n}}{2 n+1}$.