大家都知道正常的Nim游戏是取完最后一个赢. 必胜态是各堆石子异或值不为0. 现在来看看几个有意思的变种.

变种1: 取到最后一个石子的人输.
首先明确奇数个1是必败态, 偶数个1是必胜态. 这与正常的Nim不一致.
若只有一堆的个数大于1, 那么现在可以控制全场的1个数的奇偶性, 所以是必胜的. 这与正常的Nim一致.
若不止一堆的个数大于1, 由于不能转移到全是1的状态, (可能可以转移到仅有一堆大于1的状态, 但此状态与正常Nim一致), 所有当前可以转移到的状态的胜负性都是与正常的Nim一致的, 所以当前状态的胜负性与正常的Nim也是一致的.
综上, 除了全是1的状态胜负性跟正常的Nim不一致, 其余的状态胜负性与正常的Nim一致.

变种2: 只能从最左或最右的一堆中取, 取到最后一个的赢.
对于 [L,X,R] 状态, 若其是必败状态, 那么|L-R|<=1.
证明: 设[L,X,R]是必败态且R<L-1, 那么, 对于任何的1<=L’<L, [L',X,R]是必胜态. 那么对于每个L’, 都存在R’<R使得[L',X,R']是必败态, 显然不会出现[a,X,b]和[a',X,b]同为必败态的情况, 但L’有L-1个取值, R’却没有L-1个取值, 所以对于任意必败态[L,X,R], 都有|L-R|1则是必胜态, 否则, 由[X]的胜负性以及L-R的值可以推导出[L,X,R]的胜负性.

我们又要开始讨论有关素数的问题了. 各位大牛在考试中肯定有很多时间剩余,  在考场里闲着无聊怎么办呢? 在草稿纸上写写画画? 于是你就开始写素数数列:

2, 3, 5, 7, 11, 13, 17,19, 23, 29, 31, …

写了几项后决心利用考试剩余的时间解决几个世纪以来的各种素数生成问题. 素数数列有什么规律呢? 从等差数列开始算吧. 看一看素数数列的各项与其后一项之间的差:

1, 2, 2, 4, 2, 4, 2, 4, …

你相信素数数列不会是这么简单, 觉得它有可能是n-阶等差数列, 于是你无聊地再把差数列又减了一次:

1, 0, 2, -2, 2, 2, 2, 2, 4, …

啊? 竟然出现了最讨厌的负数?! 恼怒的你决定把所有的负数全都取绝对值, 再把数列减一次:

1, 2, 0, 0, 0, 0, 0, 2, …

就当你准备再减一次的时候, 你发现了一件怪事: 为什么每个数列的第一项都是1? 惊奇不已的你准备放弃解决几个世纪以来的素数难题, 转而研究这个问题. 在考试结束之时, 你已经列了几百个数列了, 它们都是以1打头的, 于是你猜想每一个这样的数列都是以1打头的.

Read more…

我们经常跟素数打交道, 我们知道素数的各种验证算法, 但是是否存在素数的生成算法呢?

事实上, 我们有许多可以生成素数的算法, 但是, 由于这些算法的效率极低, 我们基本上不会使用这些算法.

方法一: 素数编码

设 p_n 是第n个素数, Sierpinski 先生曾经定义了这样一个常量:

若定义[x]为一取下整函数, 即[x]表示不大于x的最大整数. 那么我们有:

对于这一类方法, 当把相关常量计算出来时才有实际价值, 这似乎不太可能.

方法二: 利用 Wilson 原理

Willans 先生这样定义了函数 pi(x) :

那么, 对于大于2的任意整数n, 我们有:

这个方法虽然比前一个更具体, 但是, 其中涉及到了很大的数, 要应用到实际运算中还有一定的困难.

关于素数还有很多精彩的算法, 比如验证素数的 Miller-Rabin 测试, 以及应用素数性质的 RSA 加密算法, 但有关生成素数的真正可行的算法, 还有待我们继续去探究.
Read more…

World of Goo 是一个由 2D BOY 推出的大型物理学&建筑学益智游戏，这是一个有着成千上万的叫做 Goo 的粘性小球的神奇世界，该游戏的乐趣在于如何把这些 Goo 搭建到水管口处，好让更多的 Goo 被水管收集。

Read more…