Problem 1939

The minimum value of $b_n - b_0$ is 1.
For convenience, we call a sequence $a_0, a_1, \dots, a_n$ satisfying the conditions of the problem a "$k$-good sequence".
First, we prove that the $k$-good sequence is unique. To do this, we strengthen the statement, proving simultaneously that the $k$-good sequence satisfies the following condition:
If $(a, b) = 1, a + b \ge k + 1$ and $1 \le a, b \le k$, then there exists a unique positive integer $i$ satisfying $a_i = a, a_{i+1} = b$. ...... (*)
We induct on $k$. When $k = 1$, if $n \ge 2$, then $1 \le 1 \le n-1$, so by (1) we know $2 \le a_i \le 1$, a contradiction. Hence $n = 1$, so this sequence can only be $1, 1$, and is therefore unique.
Next we prove (*). If $(a, b) = 1, a + b \ge k + 1$ and $a, b \le k$, then since $k = 1$ we know $a = b = 1$. Also $a_0 = a_1 = 1$, so (*) holds.
Suppose the statement holds for $k = t - 1$ ($t \ge 2$). Then for $k = t$, if $a_i = t$, then since $a_0 = a_n = 1 \ne t$, we have $1 \le i \le n-1$. By (3) we know $a_{i-1}, a_{i+1} \ne t$ (otherwise they would not be coprime), that is, $t$ cannot be adjacent to itself. So $a_{i-1}, a_{i+1} < t$. By (3) we know $a_i | a_{i-1} + a_{i+1}$, but $0 < a_{i-1} + a_{i+1} < 2t$, so combined with $a_i = t$ we know $a_{i-1} + a_{i+1} = t$.
Now remove all entries equal to $t$ from $a_0, \dots, a_n$, forming a new sequence $A_0, \dots, A_N$. Since
$t \neq 1$, we have $A_0 = A_N = 1$ and $N > 0$. We now prove: $A_0 \sim A_N$ is a $(t-1)$-good sequence.
Let $f: [0, N] \to [0, n]$ denote the original position of $A_i$ in the sequence $a_0, \dots, a_n$. Since the original $a_0, \dots, a_n$ satisfies conditions (1)(2), and all $t$'s have been removed from it, $A_0, \dots, A_N$ satisfies conditions (1)(2). It remains to prove (3).
Set $0 \le i \le N-1$. If $f(i+1) = f(i)+1$, then $(A_i, A_{i+1}) = (a_{f(i)}, a_{f(i)+1}) = 1$. Otherwise, between $a_{f(i)}$ and $a_{f(i+1)}$ a $t$ has been removed. Since $t$'s are not adjacent, only one $t$ is removed there, that is, $a_{f(i)} = A_i, a_{f(i)+1} = t, a_{f(i)+2} = A_{i+1}$.
By what was proved above, $A_i + A_{i+1} = t = a_{f(i)+1}$, and since $a$ satisfies condition (3), $(A_i, A_{i+1}) = (A_i, A_i + A_{i+1}) = (a_{f(i)}, a_{f(i)+1}) = 1$. In summary, in either case $(A_i, A_{i+1}) = 1$, which also means $(A_{i-1}, A_i) = (A_i, A_{i+1}) = 1 \quad \forall 1 \le i \le N-1$.
Next we prove $A_i | A_{i-1} + A_{i+1} \quad \forall 1 \le i \le N-1$. Since $a$ satisfies condition (3), it suffices to prove $a_{f(i)-1} \equiv A_{i-1} \mod A_i, a_{f(i)+1} \equiv A_{i+1} \mod A_i$. If $f(i+1) = f(i)+1$, this is clear. Otherwise, as discussed before, $a_{f(i)} = A_i, a_{f(i)+2} = A_{i+1}$ and $A_i + A_{i+1} = a_{f(i)+1}$, so $a_{f(i)+1} = A_i + A_{i+1} \equiv A_{i+1} \mod A_i$.
So in either case, $a_{f(i)+1} \equiv A_{i+1} \mod A_i$, and similarly $a_{f(i)-1} \equiv A_{i-1} \mod A_i$, combined with the fact that $a$ satisfies condition (3), we know $A_i | A_{i-1} + A_{i+1}$. Thus, we have proved that $A$ satisfies condition (3), and therefore $A$ is a $(t-1)$-good sequence. By the induction hypothesis, $A$ is unique and satisfies (*). Next we prove $a$ is unique. Note that given the choice of $A$, it suffices to prove that the way of inserting the $\phi(t)$ copies of $t$ into $A_0, \dots, A_N$ is unique. However, by what was proved above, two $t$'s cannot appear simultaneously between some $A_i$ and $A_{i+1}$, and if $t$ is between $A_i, A_{i+1}$, then $A_i + A_{i+1} = t$. Also $(A_i, A_{i+1}) = 1$ and $A_i, A_{i+1} \le t$, combined with (*) we know that if $t$ can be inserted both between $A_i, A_{i+1}$ and between $A_j, A_{j+1}$ ($i \neq j$), then $A_i \neq A_j$ (otherwise $A_{i+1} = A_{j+1}$, contradicting the uniqueness in (*)). Also $(A_i, t) = 1$ and $A_i \le t$, so $A_i$ can take at most $\phi(t)$ values, that is, there are at most $\phi(t)$ positions where $t$ can be inserted. Therefore the way of inserting $t$ is unique, that is, $a$ is unique. Also note that if $A_i + A_{i+1} = t$, then a $t$ must be inserted between $A_i, A_{i+1}$ (otherwise there would not be enough positions).
Next we prove that $a_0, \dots, a_n$ satisfies condition (*). Let $(a, b) = 1, a+b \ge t+1$ and $a, b \le t$. If $a, b \neq t$, then by the fact that $A$ satisfies condition (*) and $a+b \neq t$, it is easy to see that there exists a unique positive integer $i$ satisfying $a_i = a, a_{i+1} = b$. If $a=t$, then since $(t-b, b) = (t, b) = 1, (t-b)+b=t \ge t$ and $t-b, b \le t-1$ (note that $t$'s are not adjacent, so $b \neq t$), combined with the fact that $A$ satisfies condition (*), we know there exists a positive integer $i$ satisfying $A_i = t-b, A_{i+1} = b$. Since $A_i+A_{i+1} = t$, by what was proved above, $a_{f(i)+1} = t, a_{f(i)+2} = A_{i+1}$, and the existence part of (*) is proved. It remains only to prove uniqueness. If $a_i = t, a_{i+1} = b$, then $a_{i-1} = t-b$ and there exists a unique $I$ satisfying $f(I) = i-1, f(I+1) = i+1$. Hence $A_I = t-b, A_{I+1} = b$. Also since $A$ satisfies (*), there exists a unique $I$ satisfying $A_I = t-b, A_{I+1} = b$, from which we know $i$ is also unique. Uniqueness is proved. Hence $a_0, \dots, a_n$ also satisfies (*).
By mathematical induction, the $k$-good sequence is unique and satisfies (*).

Let the numerators in order be $b_0, \dots, b_n$, and the denominators in order be $c_0, \dots, c_n$. For convenience, we call $b, c$ respectively the $k$-numerator sequence and $k$-denominator sequence. We now prove: $c_0, \dots, c_n$ is a $k$-good sequence and
$c_i b_{i-1} - c_{i-1} b_i = 1 \quad \forall 1 \le i \le n$. This, combined with the uniqueness of the $k$-good sequence, shows that the numerators $b_0, \dots, b_n$ satisfy the conditions of the problem. Since $b_0 = 0, b_n = 1$, we get that the minimum value of $b_n - b_0$ is 1.
It is easy to see that $c_0, \dots, c_n$ satisfies conditions (1)(2). Next, we use mathematical induction on $k$ to prove that $c$ also satisfies (3) and $c_i b_{i-1} - c_{i-1} b_i = 1 \quad \forall 1 \le i \le n$.
First, when $k=1$ this is obviously true. If it holds for $k=t-1$, then for $k=t$, let $B_0, \dots, B_N$ and $C_0, \dots, C_N$ be respectively the $(t-1)$-numerator sequence and denominator sequence. Consider the fraction $\frac{x}{t}$ in lowest terms in $[0,1]$, and suppose it falls in the interval $(\frac{B_i}{C_i}, \frac{B_{i+1}}{C_{i+1}})$. By the induction hypothesis, it is easy to see that it suffices to prove $(t, C_i) = (t, C_{i+1}) = 1, C_i \equiv t \pmod{C_{i+1}}, C_{i+1} \equiv t \pmod{C_i}, t \nmid C_i + C_{i+1}, xC_i - B_it = B_{i+1}t - xC_{i+1} = 1$. ... ($\Delta$) Since $(x,t)=1$, let $q<t$ and $qx \equiv 1 \pmod t, p = \lfloor \frac{qx}{t} \rfloor$. Then $\frac{p}{q} < \frac{x}{t}$. By the definition of B, C and $q<t$, we know $\frac{p}{q} \le \frac{B_i}{C_i}$. Also $xq-pt = qx-t\lfloor \frac{qx}{t} \rfloor = qx$ divided by $t$ has remainder 1. Similarly, $xC_i - B_it = C_ix$ divided by $t$ has remainder (call it $r$) (note that here we use the fact that $\frac{B_i}{C_i}$ is the closest fraction to $\frac{x}{t}$). Since $rqx \equiv r \equiv C_ix \pmod t$, so $C_i \equiv rq \pmod t$. Also $C_i \le t$ and $rq > 0$, so $C_i \le rq$. From $\frac{p}{q} \le \frac{B_i}{C_i}$ we know $\frac{x}{t} - \frac{B_i}{C_i} \le \frac{x}{t} - \frac{p}{q}$. However $\frac{x}{t} - \frac{p}{q} = \frac{xq-pt}{qt} = \frac{1}{qt}$ and $\frac{x}{t} - \frac{B_i}{C_i} = \frac{xC_i - B_it}{C_it} \ge \frac{r}{rqt}$ (since $C_i \le rq$) $= \frac{1}{qt} = \frac{x}{t} - \frac{p}{q}$, so equality must hold, that is, $B_i = p, C_i = q$. Hence $(t, C_i) = (t, q) = 1, xC_i \equiv 1 \pmod t$ and $xC_i - B_it = xq-pt = 1$. Similarly we can prove $(t, C_{i+1}) = 1, xC_{i+1} \equiv -1 \pmod t$ and $B_{i+1}t - xC_{i+1} = 1$. Hence $x(C_i + C_{i+1}) \equiv 0 \pmod t$, that is, $t \nmid C_i + C_{i+1}$. ($\Delta$) is fully proved.
In summary, by mathematical induction we know $c=a$ and $c_i b_{i-1} - c_{i-1} b_i = 1 \quad \forall 1 \le i \le n$, and the proof of the whole problem is complete.