The 16th Japanese Mathematical Olympiad - The First Round

Generally, let $S_n$ be the number of $2n$-tuple $(p_1,p_2,\dots ,p_n;q_1,q_2,\dots ,q_n)$ of positive integers with $p_1=q_n=1$ and $p_{i+1}{q}_i-p_i{q}_{i+1}=1$ for all $i=1,2,\dots ,n-1$. We use semicolons to make the boundary simple. Let $(p_1,p_2,\dots ,p_n;q_1,q_2,\dots ,q_n)$ a tuple with the desired conditions. We first prove that there uniquely exists $i$ such that $p_i=q_i=1$. Assume that there does not exist such $i$. Then $q_1\ne 1$ and $p_n\ne 1$.

Since the sequence $p_j/q_j$ is increasing, there exists $j$ such that $$\frac{p_j}{q_j}<1<\frac{p_{j+1}}{q_{j+1}}.$$ But then $$\frac{p_{j+1}}{q_{j+1}}-\frac{p_j}{q_j}\ge \frac{1}{q_{j+1}}+\frac{1}{q_j}\ge \frac{2}{q_j{q}_{j+1}},$$ hence $p_{j+1}{q}_j-p_j{q}_{j+1}\ge 2$, a contradiction. So there exists $i$ such that $p_i=q_i=1$. Uniqueness is clear.

Now we consider the number of tuples which meets the condition for fixed $i$ such that $p_i=q_i=1$.

(1) Case $i=1$: Assume that $(1,p_2,\dots ,p_n;1,q_2,\dots ,q_n)$ meets the condition. Let $p_j^{\prime }=p_j-q_j$. Then the $2(n-1)$-tuple $(p_2^{\prime },p_3^{\prime },\dots ,p_{n-1}^{\prime };q_2,q_3,\dots ,q_n)$ meets the condition. Conversely, assume that a $2(n-1)$-tuple $(p_1,\dots ,p_{n-1};q_1,\dots ,q_{n-1})$ meets the condition. Let $p_j^{\prime }=p_j+q_j$. Then $(1,p_1^{\prime },p_2^{\prime },\dots ,p_{n-1}^{\prime };1,q_1,q_2,\dots ,q_{n-1})$ meets the condition. Since each of these two operations gives the inverse of the other, it follows that the number of $2n$-tuples with $p_1=q_1=1$ which meets the condition is equal to $S_{n-1}$.

(2) Case $1<i<n$: Assume that $(p_1,\dots ,p_{i-1},1,p_{i+1},\dots ,p_n;q_1,\dots ,q_{i-1},1,q_{i+1},\dots ,q_n)$ meets the condition. Let $q_j^{\prime }=q_j-p_j$ and $p_j^{\prime \prime }=p_j-q_j$. Then two tuples $(p_1,\dots ,p_{i-1};q_1^{\prime },\dots ,q_{i-1}^{\prime })$ and $(p_{i+1}^{\prime \prime },\dots ,p_n^{\prime \prime };q_{i+1},\dots ,q_n)$ meet the condition. Conversely, assume that a $2(i-1)$-tuple $(p_1,\dots ,p_{i-1};q_1,\dots ,q_{i-1})$ and a $2(n-i)$-tuple $({\tilde{p}}_1,\dots ,{\tilde{p}}_{n-i};{\tilde{q}}_1,\dots ,{\tilde{q}}_{n-i})$ meet the condition. Let $q_j^{\prime }=p_j+q_j$ and ${\tilde{p}}_j^{\prime \prime }={\tilde{p}}_j+{\tilde{q}}_j$. Then $(p_1,\dots ,p_{i-1},1,{\tilde{p}}_1^{\prime \prime },\dots ,{\tilde{p}}_{n-i}^{\prime \prime };q_1^{\prime },\dots ,q_{i-1}^{\prime },1,{\tilde{q}}_1,\dots ,{\tilde{q}}_{n-i})$ meets the condition. Since each of these two operations gives the inverse of the other, it follows that the number of $2n$-tuples with $p_i=q_i=1$ which meets the condition is equal to $S_{i-1}{S}_{n-i}$.

(3) Case $i=n$: Thinking similarly to the case $i=1$, the number of $2n$-tuples with $p_n=q_n=1$ which meets the condition is equal to $S_{n-1}$.

From arguments above, we obtain a recursive relation $$S_n=S_{n-1}+S_1{S}_{n-2}+\cdots +S_{n-2}{S}_1+S_{n-1}.$$ With this formula and the initial value $S_1=1$, we can compute and get $S_{10}=16796$.