从 OI 退役下来就一直计划要写一批回报 OI 界的文章, 其他文章还在规划当中, 而这一篇是从九月份的 UyHiP 的解法而想到的. 接下来这段时间也不算太忙, 我就保质保量的完成这一批文章吧.

一百囚犯问题: 这里的一百囚犯可不是开关灯泡的那些囚犯, 而是戴手套的. 这一群囚犯被告知, 在第二天早上, 他们每个人头上会被写上一个不同的实数, 每个人在单间里会看到其他人头上写着数的照片, 但都不知道自己头上写了什么, 接下来每个人会有一只白手套和一只黑手套, 在每个人都决定好要怎么戴上手套之后, 他们会被从各单间里拉出来按照头上的数从小到大排成一排, 相邻的人要手拉着手, 如果每一对拉着的手都是同样颜色的, 那么他们就会被释放. 现在他们有一晚上的时间来商量如何应对.

答案当然就是利用逆序对, 如果我们给每个人都编上号, 最后按照头上的数排序后我们就会得到一个序列. 每个人可以看到的特征: 这个序列除去他自己, 这样得到的一个序列就是它能得到的所有可用信息了. 仔细观察每个人看到的序列的逆序对个数是有性质的: 原序列中相邻两个同奇偶的数看到的逆序对数是不同奇偶的, 反之相邻两个不同奇偶的数看到的逆序对个数就是同奇偶的. 这启发了我们用一个巧妙的构造来解决这些囚犯们的难题: 如果我们把两种戴手套方法叫做 0 和 1 的话, 一个编号是奇数的人, 若看到的逆序对数是奇数就是 0 状态, 否则就是 1 状态; 一个是编号是偶数的人, 若看到的逆序对数是奇数就是 1 状态, 否则就是 0 状态. 这样我们就可以保证相邻两个人的状态不同了.

你可能会想, 逆序对难道有这么重要的性质吗? 事实上, 逆序对是一个数列的很重要的特征. 有一个很简单的例子, 就是信息学竞赛当中的八数码问题, 如果我们把八数码中的那个空格忽略, 把剩下来的 8 个数按照顺序写成一个数列. 我们发现, 把空格平移对数列没有影响, 而若是把空格上移或者下移的话, 分情况讨论被移动的数和中间隔的两个数, 我们会发现逆序对的奇偶性是不变的. 因此, 我们对于八数码的初状态和目标状态, 若逆序对奇偶性不相同, 一定是无解的. 但反过来证明要是逆序对就相同就有一点点困难了, 虽然这也是对的, 所有八数码的可能状态只分为两个等价类: 逆序对奇数, 逆序对偶数.

从上面的例子还可以推广到很多, 比如说一个排列通过对换变成一个顺序列 (eg., 1, 2, 3, 4…) 的次数的奇偶性和逆序对相同, 也就是说, 一个排列应用一次对换逆序对的奇偶性会改变.

另外, 逆序对能够一定程度上反映序列的混乱状况, 所以逆序对在排序算法的复杂度分析上也有很重要的作用, 当然了, 在各种 OI 竞赛上面逆序对也同样有他的一番用武之地.

在多人 project 里, 代码注释是必不可少的东西, 通常注释都是解释此段程序的用途, 但下面这段注释却让人啼笑皆非:

//
// Dear maintainer:
//
// Once you are done trying to 'optimize' this routine,
// and have realized what a terrible mistake that was,
// please increment the following counter as a warning
// to the next guy:
//
// total_hours_wasted_here = 32
//

更多例子请见此帖.

(original post via walking randomly)

Martin Gardner 先生於昨日(22日)去世了, 終年95歲.

這是一個很有趣的數, 他應該會很喜歡的.

Martin 先生最著名的成就便是在科學美國人上開設二十餘年的數學遊戲專欄, 下面這張很有名的數學謬論就是他提出來的:

你要是還想進一步了解他所作的謎題, 請移步科學美國人的紀念文章.

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