石子堆题目

作者: , 共 1094 字 , 共阅读 0

问题:

有 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,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.

类似文章:
在 MIT BBS 上看到一个有趣的题目
相似度: 0.092
注:此游戏很有名,有同学问我其算法,我在网上找了一下,居然没多少中文资料,这里按照以前看过的一份答案回忆整理贴出。
IBM 的 Ponder This 项目每个月会发出一个谜题,这个月的题目是加倍交换数字游戏
相似度: 0.075
前两天贴出了一个硬币游戏,希望寻找一种胜利策略。这是一个非常有意思的题目,没事做的时候可以用来锻炼思考能力。我迫不及待的想在这里公布解答,因为我已经把它解决掉了。如果有人还想继续享受思考的乐趣,请飘至原问题
数学 » 数学游戏, 概率
蚁迹寻踪及其他数学探索》提到一个游戏:
相似度: 0.053
Alice 和 Bob 两人玩一种硬币游戏。游戏在一个$ 2\times2$ 的棋盘上进行,棋盘上每个格子上都有一枚硬币。在每一回合, Alice 可以决定选择翻转某两枚或者一枚硬币,接着 Bob 可以选择将棋盘旋转 90 , 180 或者 270 度,也可以什么都不做。
利用线性代数可以给某些问题很精妙的证明,Matrix67 就给出了一个这样的例子,这也让我想起以前看见的另外一个例子,分享如下:
IT » apt, pip, python, ubuntu
正常而言,大家都是用 pip 来安装 python 的包。但有时候无意中(通常是为安装某个特定的软件,根据软件的安装提示),会使用 apt 安装 python 包。而且其实很多包都可以通过 apt 来安装的,名字就是包名再加python3-的前缀。安装后的库以及依赖项位于/usr/lib/python3/dist-packages目录下。比如 apt 安装 requests 包:
本周末,我们一行六个小探险家一同征服了顺义最高峰——舞彩浅山的降魔顶,同时也欣赏了初秋的自然风光。虽然这里位于舞彩浅山北侧,秋色与白毛峪月明涧的经典景色相比稍显逊色,仅在接近路程尾声时才见几分斑斓,但爬山的过程本身却是一次非凡的体验。