Stern-Brocot树与Farey序列

概述

单调性

每一行的分数是单调递增的。考虑归纳：

$\frac{a}{b}\le \frac{c}{d}\\ \Rightarrow ad \le bc\\ \Rightarrow ad + ab\le bc + ab\\ \Rightarrow \frac{a}{b} \le \frac{a+c}{b+d}$

同理可证 $\frac{a+c}{b+d} \le \frac{c}{d}$ 。

最简性

即序列中所有分数都是最简分数。

首先证明 $bc-ad=1$ ，仍然使用归纳法：

$bc-ad=1 \\ \Rightarrow b(a+c)-a(b+d)=1$

另一半同理。

而 $bc-ad=1$ 即意味着 $\gcd(a,c)= \gcd(b,d)=1$（裴蜀定理）

存在性

考虑 $\frac{x}{y}$ 如果在某一层没有出现过，则这一层一定有两个数 $\frac{a}{b}, \frac{c}{d}$ 满足 $\frac{a}{b} \le \frac{x}{y} \le \frac{c}{d}$ 。

也就是

$bx - ay > 0, cy - dx > 0\\ \Rightarrow bx - ay \ge 1, cy - dx \ge 1$

同乘上 $(a+b), (c+d)$ ：

$\Rightarrow \begin{cases} (c+d)(bx-ay)\ge c+d\\ (a+b)(cy-dx) \ge a+b \end{cases} \\ \Rightarrow \begin{cases} bcx-acy+bdx-ady\ge c+d\\ acy-adx+bcy-bdx\ge a+b \end{cases}\\ \Rightarrow (bc-ad)x+(bc-ad)y\ge a+b+c+d$

因为 $bc-ad=1$ ，所以 $x+y\ge a+b+c+d$ 。而因为每一次向更深的层走，$a+b+c+d$ 会增加，所以至多在 $x+y$ 层 $\frac{x}{y}$ 就会出现。

并且 $x+y$ 已经是最紧的界了，因为分数 $\frac{1}{n}$ 出现在 $n+1$ 层。

Farey 序列

参考 OI-wiki