13. [30] Given positive integers $a$ and $b$ such that $a>b$, define a sequence of ordered pairs $\left(a_{l}, b_{l}\right)$ for nonnegative integers $l$ by $a_{0}=a, b_{0}=b$, and $\left(a_{l+1}, b_{l+1}\right)=\left(b_{l}, a_{l} \bmod b_{l}\right)$, where, for all positive integers $x$ and $y, x \bmod y$ is defined to be the remainder left by $x$ upon division by $y$. Define $f(a, b)$ to be the smallest positive integer $j$ such that $b_{j}=0$. Given a positive integer $n$, define $g(n)$ to be $\max _{1 \leq k \leq n-1} f(n, k)$.
(a) $[\mathbf{1 5}]$ Given a positive integer $m$, what is the smallest positive integer $n_{m}$ such that $g\left(n_{m}\right)=m$ ?
(b) $[\mathbf{1 5}]$ What is the second smallest?
Solution:
(a) The answer is $F_{m+1}$, where $F_{1}=1, F_{2}=2$, and $F_{i+1}=F_{i}+F_{i-1}$ for all $i \geq 2$.
We consider a reverse sequence as follows: starting at $p_{0}=\left(k_{0}, 0\right)$ for some positive integer $k_{0}$, at each step we can take a pair $p_{i}=\left(r_{i}, s_{i}\right)$ to any pair $p_{i+1}=\left(s_{i}+k_{i+1} r_{i}, r_{i}\right)=\left(r_{i+1}, s_{i+1}\right)$ for some positive integer $k_{i+1}$. It is clear that any such sequence is the reverse of a legal sequence. Thus, $n_{m}$ is equal to the smallest possible value of the first integer in a possible $p_{m}$ of a reverse sequence. The pair $p_{m}$ is uniquely determined by the choice of $k_{0}, k_{1}, \ldots, k_{m}$, and lowering any $k_{i}$ lowers the first number of $p_{m}$. Thus, the minimum possible value occurs when all $k_{i}$ are equal to 1. In this case, $p_{0}=(1,0), p_{1}=(2,1)$, and $p_{i+1}=\left(r_{i}+s_{i}, r_{i}\right)$. It is apparent that $p_{i}=\left(F_{i+1}, F_{i}\right)$, so the minimum is $F_{m+1}$.
(b) The answer is $L_{m+1}$, where $L_{1}=1, L_{2}=3$, and $L_{i+1}=L_{i}+L_{i-1}$.
The only integer $n$ satisfying $g(n)=1$ is 2 , as it is the only positive integer $n>1$ such that all integers $1 \leq ij$, we have $r_{i}=F_{i+2}-F_{i-j-1} F_{j-1}$. Thus, to minimize $r_{m}=F_{m+2}-F_{m-j-1} F_{j-1}$, we must maximize $F_{m-j-1} F_{j-1}$.
We claim that $F_{m-j-1} F_{j-1} \leq F_{m-2}$ for $1 \leq j \leq m$.
Proof of claim. It is easy to see (and in fact well-known) that for all positive integers $n, F_{n}$ counts the number of distinct ways to tile a $1 \times n$ board with $1 \times 1$ squares and $1 \times 2$ dominoes. Thus $F_{m-j-1} F_{j-1}$ counts the number of ways to tile a $1 \times m-2$ board with $1 \times 1$ squares and $1 \times 2$ dominoes such that the $j-1$ th and $j$ th square are not both covered by the same domino, which is at most the number of ways to tile a $1 \times m-2$ board, as desired.
Since this minimum is reached by letting $j=1$, we may conclude that the answer is indeed $L_{m+1}$.