International Mathematics Competition
for University Students
2018

IMC2018: Day 2, 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)

Hint: Project \(\displaystyle \Omega\) to the plane by the map \(\displaystyle (x,y,z)\mapsto(x+y,z)\) and consider the functions \(\displaystyle \varphi\) on the lattice that satisfy \(\displaystyle \varphi(u,v)=\varphi(u-1,v)+\varphi(u,v-1)\).

  Solution