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_iq_{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 \neq 1$ and $p_n \neq 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_jq_{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 = p_j - q_j$. Then the $2(n-1)$-tuple $(p'_2, p'_3, \dots, p'_{n-1}; 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 = p_j + q_j$. Then $(1, p'_1, p'_2, \dots, p'_{n-1}; 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 = q_j - p_j$ and $p''_j = p_j - q_j$. Then two tuples $(p_1, \dots, p_{i-1}; q'_1, \dots, q'_{i-1})$ and $(p''_{i+1}, \dots, p''_n; 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 = p_j + q_j$ and $\tilde{p}''_j = \tilde{p}_j + \tilde{q}_j$. Then $(p_1, \dots, p_{i-1}, 1, \tilde{p}''_1, \dots, \tilde{p}''_{n-i}; q'_1, \dots, q'_{i-1}, 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} + \dots + 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$.