简单的证明

给出邻项交换的传递性的证明。由于不是本人想出，不评价主观难度。

定义关系 <。当且仅当一对相邻项 (y, x) 被交换使得答案严格更优时，我们称 x < y。

考虑将每个项映射到实数上，即寻找函数 f，使得 f(x)<f(y) 是 x<y 的充要条件。

刻画 < 关系的性质。s<t 意味着 strcat(s, t) 在字典序意义下小于 strcat(t, s)

我们将 s 和 t 视为整数。这样，s<t 意味着 s*10^{len(t)}+t<t*10^{len(s)}+s。

移项。s*(10^{len(t)}-1)<t*(10^{len(s)}-1)

两边同时除以 (10^{len(t)}-1)*(10^{len(s)}-1)：

s/(10^{len(s)}-1)<t/(10^{len(t)}-1)

注意到不等式两边的不变量是分离的。取 f(x) = x/(10^{len(x)}-1)，证毕。