问题:
有 5050 颗石子,任意分为若干堆,每次操作,从每堆中拿出一颗,合成新的一堆。问:是否一定会经过若干次操作后,每堆棋子数分别为 1 , 2 , 3 ,。。。, 100 ?
这个问题最初出现在 Jørgen Brandt 的文章 Cycles of partitions (1982) 里,后来因科普作家 Martin Gardner 在 1983 年 8 月的《科学美国人》上的宣传而闻名,并被命名为 Bulgarian solitaire , 1985 年 4 月的《美国数学月刊》有直觉解答。
解答,尽量直觉一点:
把石子堆按个数从小到大排成一行。比如 1, 1, 1, 3, 4。我们可视化地可以表示成下面这样:
从每一堆里取出一个石子,成为新的一堆,可以表示为将下面一行的格子挪到最右边成为新的一列:
为了更直观,我们给每个格子标了号。这个号非常有学问。最右下角是 1 ,每往上或往左都会增加 1。我们可以看到将下面一行的格子挪到最右边成为新的一列,不会破坏这个编号规则,也就是格子的数是保持不变的。
还有一个更强的不变性,编号为 1 的格子保持不动,编号为 2 的格子(以及空格)在一个长为 2 的对角线 2 斜线上循环挪动,编号为 3 的格子(以及空格)在长为 3 的对角线 3 斜线上循环挪动,以此类推。
我们再看下一步:
这一步略有不同,在操作之后石子堆的排列不满足要求了!这时候我们按照大小重排:
这个重排的后果是,格子上的数字变小了:一个 5 变成了 4。格子上数字之和在变小。这其实我们就找到了一个稳定量——格子数字之和。这个稳定量是不可能无限变小下去的。这意味着,在某一步之后,这种重排不可能再次发生。我们称这种状态是稳定态。
结论:一个状态为稳定态,当且仅当存在某个对角线,对角线右下方充满了格子,对角线左上方则没有格子。
充分性:当存在这么一条对角线时,我们可以看到将行转为列式,它仍然是这么一个状态(对应同样一条对角线),它将在这里进行循环。
必要性:如果不存在这么一条对角线,这意味着有这么一条对角线 k ,它右下方全是格子,它自己有一个空位,它的左上方对角线 k+1 又有一个格子。我们知道操作时,所有格子都在对角线上往复转动,那么必然存在一个时刻, k+1 对角线上来到了右数第二列, k 对角线上的空位来到了右数第一列。这意味着最右边的石子堆的石子数少于右数第二堆,这时候会发发生重排,也意味着这不是一个稳定态。
回到最初的问题, 5050 颗石子,显然只能堆成这么一个稳定态,即 100 堆分别是 1 , 2 ,。。。, 100。
Q. E. D.