### International Mathematics Competition for University Students

July 22 – 28 2018, Blagoevgrad, Bulgaria

Home

Results
Individuals
Teams
Leaders

Official IMC site

### Problem 8

Problem 8. Let $\displaystyle \Omega=\{(x,y,z)\in \mathbb{Z}^3: y+1\ge x\ge y\ge z\ge 0\}$. A frog moves along the points of $\displaystyle \Omega$ by jumps of length $\displaystyle 1$. For every positive integer $\displaystyle n$, determine the number of paths the frog can take to reach $\displaystyle (n,n,n)$ starting from $\displaystyle (0,0,0)$ in exactly $\displaystyle 3n$ jumps.

(Proposed by Fedor Petrov and Anatoly Vershik, St. Petersburg State University)

Solution. Let $\displaystyle \Psi=\{(u,v)\in \mathbb{Z}^3: v\ge0, u\ge 2v \}$. Notice that the map $\displaystyle \pi:\Omega\to\Psi$, $\displaystyle \pi(x,y,z)=(x+y,z)$ is a bijection between the two sets; moreover $\displaystyle \pi$ projects all allowed paths of the frogs to paths inside the set $\displaystyle \Psi$, using only unit jump vectors. Hence, we are interested in the number of paths from $\displaystyle \pi(0,0,0)=(0,0)$ to $\displaystyle \pi(n,n,n)=(2n,n)$ in the set $\displaystyle \Psi$, using only jumps $\displaystyle {(1,0)}$ and $\displaystyle {(0,1)}$.

For every lattice point $\displaystyle (u,v)\in\Psi$, let $\displaystyle f(u,v)$ be the number of paths from $\displaystyle (0,0)$ to $\displaystyle (u,v)$ in $\displaystyle \Psi$ with $\displaystyle {u+v}$ jumps. Evidently we have $\displaystyle f(0,0)=1$. Extend this definition to the points with $\displaystyle v=-1$ and $\displaystyle 2v=u+1$ by setting

$\displaystyle f(u,-1)=0, \quad f(2v-1,v)=0. \tag3$

To any point $\displaystyle (u,v)$ of $\displaystyle \Psi$ other than the origin, the path can come either from $\displaystyle (u-1,v)$ or from $\displaystyle (u,v-1)$, so

$\displaystyle f(u,v)=f(u-1,v)+f(u,v-1) \quad\text{for $$\displaystyle (u,v)\in\Psi\setminus\{(0,0)\}$.} \tag4$$

If we ignore the boundary condition (3), there is a wide family of functions that satisfy (4); namely, for every integer $\displaystyle c$, $\displaystyle (u,v)\mapsto\binom{u+v}{v+c}$ is such a function, with defining this binomial coefficient to be $\displaystyle 0$ if $\displaystyle v+c$ is negative or greater than $\displaystyle u+v$.

Along the line $\displaystyle 2v=u+1$ we have $\displaystyle \binom{u+v}{v} = \binom{3v-1}{v} = 2\binom{3v-1}{v-1} = 2\binom{u+v}{v-1}$. Hence, the function

$\displaystyle f^*(u,v) = \binom{u+v}{v} -2\binom{u+v}{v-1}$

satisfies (3), (4) and $\displaystyle f(0,0)=1$. These properties uniquely define the function $\displaystyle f$, so $\displaystyle f=f^*$.

In particular, the number of paths of the frog from $\displaystyle (0,0,0)$ to $\displaystyle (n,n,n)$ is

$\displaystyle f(\pi(n,n,n)) = f(2n,n) = \binom{3n}{n} - 2\binom{3n}{n-1} = \dfrac{\dbinom{3n}{n}}{2n+1}.$

Remark. There exist direct proofs for the formula $\displaystyle \binom{3n}{n}/(2n+1)$. 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