马孔多不下雪

从两个分数$(\frac{0}{1},\frac{1}{0})$出发,在相邻两个分数$\frac{m}{n},\frac{m’}{n’}$之间插入$\frac{m+m’}{n+n’}$,便可以构造出满足$m\perp n$的全部非负分数$\frac{m}{n}$的集合。

例如:

$\frac{0}{1},\frac{1}{1},\frac{1}{0}$

$\frac{0}{1},\frac{1}{2},\frac{1}{1},\frac{2}{1},\frac{1}{0}$

$\frac{0}{1},\frac{1}{3},\frac{1}{2},\frac{2}{3},\frac{1}{1},\frac{3}{2},\frac{2}{1},\frac{3}{1},\frac{1}{0}$

画成树状便是$SBT$。

约定与命名

用字母$L$和$R$表示从某一子树向左或向右走一步,这样每一个位置都有一串$LR$字符唯一对应。

比如:$LRRL:\frac{1}{1}->\frac{1}{2}->\frac{2}{3}->\frac{3}{4}->\frac{5}{7}$。

并将$\frac{1}{1}$记作$I$。

问题

  • 甲:对于$\forall m,n\in N^+,m\prod n$,则与$\frac{m}{n}$对应字符串$S$是什么?
  • 乙:甲的逆命题:对于给定字符串$S$,则与它对应的分数是什么?

求解

对乙:

不妨令$f(s)=$与$s$对应的分数,比如$f(LRRL)=\frac{5}{7}$

可以发现在计算过程中需要保持两个分数共计$4$个变量,那么最好的方式就是构造$2\times2$矩阵:
$$
M(S)=\left[ \begin{matrix} n & n’ \ m & m’ \end{matrix} \right]
$$
显然
$$
M(I)=\left[
\begin{matrix}
1 & 0 \
0 & 1
\end{matrix}
\right]
$$
则向左一步就是用$n+n’$替换$n’$,$m+m’$替换$m’$。(记住$\frac{m}{n},\frac{m+m’}{n+n’},\frac{m’}{n’}$)


$$
M(SL)=\left[ \begin{matrix} n & n+n’ \ m & m+m’ \end{matrix} \right]=\left[ \begin{matrix} n & n’ \ m & m’ \end{matrix} \right]\left[ \begin{matrix} 1 & 1 \ 0 & 1 \end{matrix} \right]=M(S)\left[ \begin{matrix} 1 & 1 \ 0 & 1 \end{matrix} \right]
$$

透过$2\times2$矩阵乘法
$$
\left[\begin{matrix}a&b\c&d\end{matrix}\right]\left[\begin{matrix}w&x\y&z\end{matrix}\right]=\left[\begin{matrix}aw+by&ax+bz\cw+dy&cx+dz\end{matrix}\right]
$$

便有上述结论

同理
$$
M(SR)=\left[ \begin{matrix} n+n’ & n \ m+m’ & m \end{matrix} \right]=M(S)\left[ \begin{matrix} 1 & 0 \ 1 & 1 \end{matrix} \right]
$$
不妨令
$$
L=\left[ \begin{matrix} 1 & 1 \ 0 & 1 \end{matrix} \right],R=\left[ \begin{matrix} 1 & 0 \ 1 & 1 \end{matrix} \right]
$$
则$M(S)=S$,例如
$$
M(LRRL)=LRRL=\left[ \begin{matrix} 1 & 1 \ 0 & 1 \end{matrix} \right]\left[ \begin{matrix} 1 & 0 \ 1 & 1 \end{matrix} \right]\left[ \begin{matrix} 1 & 0 \ 1 & 1 \end{matrix} \right]\left[ \begin{matrix} 1 & 1 \ 0 & 1 \end{matrix} \right]=\left[ \begin{matrix} 3 & 4 \ 2 & 3 \end{matrix} \right]
$$
故$f(S)=f(M(S))=\frac{m+m’}{n+n’}$

对甲:

这棵树去除$\frac{1}{0},\frac{0}{1}$后就是一棵标准的二叉搜索树(Binary Search Tree,BST),直接跑一个二叉查询即可。

1
2
3
4
S=I
while(m / n != f(s))
if(m / n < f(s)) S += L
else S += R

参考文献

Ronald L. Graham, 《具体数学》(2017),96-101


 评论