大家都知道正常的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…

假如Alice和Bob需要经过一个不可靠媒介传送一条消息, 他们大概会把这条消息加密, 而普遍使用的字母移位法(凯撒加密法)太容易被破解, 所以他们可能会考虑使用更加安全的加密法.

在上个世纪70年代被麻省理工学院的三位教授发明的RSA加密算法就是一个足够安全的加密法, 当今互联网的SSL安全连接协议的重要加密算法就包括了RSA加密算法. 连接到你的网上银行, 查看这个安全连接的证书, 证书上很可能写的就是“RSA加密”.

当然, RSA被广泛使用的原因还有一个, 那就是它的加密钥匙是公开的, 也就是说, 任何人都可以使用公开的密钥给消息加密, 却无法给刚加密的消息解密.

Read more…

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

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

方法一: 素数编码

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

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

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

方法二: 利用 Wilson 原理

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

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

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

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

去年就开始用 Mathematica 了, 在今年 Wolfram|Alpha 推出后, 我使用 Mathematica 的次数就越来越多了, 但有时候有的函数用起来还是不够得心应手, 所以前几天特意看了一下 Overview, 把初用者需要的重点记了下来, 难免会有不准确之处, 请各位大牛批评指正.

另外, 最近一直都很忙, 有几个话题一直没写完, 所以有段时间没有更新, 望各位见谅.

Read more…

有的时候我们需求一种简介的表示数的方法，对于普通的有理数来说，普通的分数足够了。但是对于无理数，普通的分数可就无能为力了。我们有没有简介的方法来表示无理数呢？

连分数( continued fractions )就是这样的一种表示数的方法，连分数是形如下图的式子。

我们一般将连分数简写成

Read more…

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

Read more…