上次那篇日志发布之后，据说大家解题的热情相当高。Michael Brand告诉我说，他收到了很多来自中国的邮件，他感到非常高兴。在揭晓谜底之前，还是让我们先回顾一下题目：
对数列的一次“块移动”是指把一段数取出来插入到数列中的另一个地方（说穿了就是一次选择剪切粘贴的操作）。例如，数列1,4,5,6,2,3,7可以通过一次块移动完成排序（把456挪到3后面）。那么，想要让一个1到n的逆序排列n, n-1, …, 3, 2, 1变为顺序排列，最少需要多少次块移动？给出你的算法，并证明这个移动数目不能再少了。
需要指出的是，答案并不是n-1那么简单。当n=5时，只需要三步就可以搞定了：
5 4 [3 2] 1
3 2 5 [4 1]
[3 4] 1 2 5
1 2 3 4 5
很多时候，我们往往不知道如何证明一些最简单、最基本的命题，即使证明本身也并不复杂。上个星期我去《数学思维方法与创新》这门通选课时，丘维声教授就提到了这个问题；在随堂统计中，知道三角函数和角公式证明方法的人出乎意料的少，而事实上高中的数学教材上印有这个公式的完整证明。
试着证明这个定理：给定一个圆，则端点在圆周上的平分圆面积的曲线以圆的直径最短。
现在，我在心里想一个不超过n的正整数t。你的任务是尽可能用奇数次猜测猜中这个数（你知道n是多少）。每次猜测后，我都会告诉你你所做的猜测是大了还是小了。你不能猜测已经被排除了的数（来消耗猜测次数），你的每次猜测都必须符合我原来给出的回答。你觉得，你获胜（奇数次猜中）的几率有多大？
动态规划的几个类似的经典模型启发了我们：设a[m]表示采取最优策略后在m个数里猜奇数次猜中的概率，b[m]表示如果题目要求我们猜偶数次，那最优策略下有m个数时获胜的概率是多少。考虑现在我有m个数可以猜，我想在奇数次内猜中。现在我猜的是数字i。狗屎运最好时，我一次猜中直接就赢了，它的概率是1/m；有(i-1)/m的情况下我会得到“大了”的提示，这样的话我需要用偶数次猜测去猜前面那i-1个数；剩余的那(m-i)/m的情况中，我需要用偶数次猜测去猜m-i个数。因此，a[m] = Max {1/m + (i-1)/m * b[i-1] + (m-i)/m * b[m-i], 1≤i≤m} 。类似地，我们也可以得出b[m]的递推公式：b[m] = Max {(i-1)/m * a[i-1] + (m-i)/m * a[m-i], 1≤i≤m} 。
学习使用Mathematica确实是一件好事，你可以用Mathematica非常方便地描述出我们上面的两个递推公式，不需要自己去写那些冗长的程序了。
a[m_] := Max[Table[1/m + (i-1)/m * b[i-1] + (m-i)/m * b[m-i], {i, m}]]; a[0] := 0;
b[m_] := Max[Table[(i-1)/m * a[i-1] + (m-i)/m * a[m-i], {i, m}]]; b[0] := 0;
有这么一个无自环的有向图，它的顶点数在30和40之间（包括30和40）。对于图里面的任意两个点A和B，要么存在一条有向边A->B，要么存在唯一的一个“中间点”C使得A可以通过A->C->B两步走到B。换句话说，对任意给定的A、B两点，从A到B的长度不超过2的路径有且仅有一条。注意，即使当A=B时，这个条件也是成立的。试问这个图有多少个顶点。
最近忙着迎新，很久没有更新了。见了很多可爱的MM，让人欲火焚身。管萌MM是我们这个专业08的新生，人气相当高。在这里祝她生日快乐。好了，最近的情况就聊到这儿。
Wilson定理指出，对于任一个质数p，都有(p-1)! ≡ -1 (mod p)，换句话说(p-1)! + 1能被p整除。为了证明这一点，让我们来考虑一个圆周上的p等分点。顺次连接这p个点我们可以得到一个正p边形，让它随便旋转多少个360/p度所得到的图形都和原来一样。类似地，跳跃着连接起第1, 3, 5…个点，或者两个两个地跳开来（连接1, 4, 7…个点），你可以得到一个星形的广义正p边形，它们同样满足类似的旋转对称性质。由于跳过k个点和跳过p-k-2个点是一回事，因此这种类型的多边形一共有(p-1)/2个。注意像这种“k个点k个点地跳着连接”的连接方式一定会遍历所有的点最后回到出发点：假如连接d个点后你就提前回到出发点了（而没有遍历完所有点），那一定还有若干组大小为d的点集没被连过，这样的话总点数就是d的倍数，与p是质数就矛盾了。
除了这种旋转对称的“广义正p边形”以外，其它的多边形随便旋转多少都不能和原来全等。假设有图形最少只需要旋转d个点的位置(d>1)之后就与原图形重合，那么p一定是d的倍数，否则当到了k·d<p<(k+1)d时p-k·d就成了更小的与原图重合的旋转角度；然而p是d的倍数与p是质数矛盾。这告诉我们，非旋转对称的多边形总是p个p个的成组出现，因此它们的数目能被p整除。
另一方面，连接圆周上的各点所能形成的多边形总数为(p-1)!/2，这是因为规定了起始点后，多边形就由剩下的p-1个点的排列确定，但每个多边形都各算了两次（顺时针、逆时针遍历各一次）。而前面已经提到过，广义的正p边形有(p-1)/2个。这样的话，非旋转对称的多边形总数就等于
(p-1)!/2 – (p-1)/2 = 1/2 [(p-1)! + 1 – p]
这个数目能被p整除当且仅当(p-1)! + 1能被p整除。
来源：http://www.cut-the-knot.org/blue/GeometricWilson.shtml
有趣的是，“p是质数”这一条件也是必要的。假设一个合数p也能整除(p-1)! + 1，这意味着它的某个大于1的因子d也能整除(p-1)! + 1；但同时d还能整除(p-1)!，这显然是不可能的。