摘录几道题目。
计算1·2^2 + 2·3^2 + 3·4^2 + … + 19·20^2
原式 = (1^3 + 2^3 + … + 20^3) – (1^2 + 2^2 + … + 20^2) = 44100 – 2870 = 41230
求2^x = 3^y – 1的所有正整数解
x=1时(1,1)是一个解；当x>1时，方程模4后左边永远等于0，右边则是(-1)^y – 1，可知y为偶数。令y=2z，那么有2^x = (3^z – 1)(3^z + 1)，这就要求3^z-1和3^z+1都是2的幂；但它们只相差2，因此它们只有可能是2和4，于是z=1，即原方程的另一个解为(3,2)。
圆周上有2008个点。选择两个点连成一条线，再选另外两点连一条线，这两条线段相交的概率为多少？
给定四个点，在三种连接方案中恰有一种会发生相交。取遍所有C(2008,4)种组合，相交的总情况数总是占了1/3，因此所求的概率就是1/3。
概率论给我们带来了很多匪夷所思的反常结果，条件概率尤其如此。网络上每一次有人发帖提出与条件概率有关的悖论时，总会引来无数人的围观和争论，哪怕这些问题的实质都是相同的。
来看两道简单的组合数学问题：
1. 四个人打桥牌。其中一个人说，我手上有一个A。请问他手上有不止一个A的概率是多少？
2. 四个人打桥牌。其中一个人说，我手上有一个黑桃A。请问他手上有不止一个A的概率是多少？
这两个问题看起来很像，实际算法大不相同。在第一题问题中，
手上一个A也没有 有 C(48,13) 种情况
手上有至少一个A 有 C(52,13) – C(48,13) 种情况
手上恰好有一个A 有 C(48,12) * 4 种情况
手上有至少两个A 有 C(52,13) – C(48,13) – C(48,12) * 4 种情况
根据条件概率公式，手上有超过一个A的概率为(C(52,13) – C(48,13) – C(48,12) * 4) / (C(52,13) – C(48,13)) = 5359/14498 ≈ 37%
电影中经常出现这样的情节：有一份绝密文件需要交给5位特工，为了防止某个特工被捕或者叛变，5名特工各自只持有其中1/5的文件（更好的做法是只持有其中1/5的密钥），这5名特工需要同时在场才能获取文件全文。但这也有一个隐患：如果真的有特工被抓了，当坏人们发现只拿到其中一份文件没有任何用处的同时，特工们也会因为少一份文件无法解开全文而烦恼。此时，你或许会想，是否有什么办法能够让特工们仍然能够恢复原文，即使一部分特工被抓住了？换句话说，有没有什么密文发布方式使得，只要5个人中半数以上的人在场就可以解开绝密文件？这样的话，侵入者必须要能操纵半数以上的特工才可能对秘密文件造成实质性的影响。这种秘密共享方式被称为(3,5)门限方案，意即5个人中至少3人在场才能解开密文。
实现(m,n)门限方案的一个传统办法是，把这份文件的密钥拆成C(n,m-1)份，每个人持有C(n-1,m-1)份密钥。在(3,5)门限方案中，我们需要C(5,2)=10个密钥，不妨分别用0到9编号；5个特工各持有6个密钥，密钥的分配如下：
特工#1: 012345
特工#2: 012 678
特工#3: 0 34 67 9
特工#4: 1 3 56 89
特工#5: 2 45 789
上述分配表的构造其实很简单：为特工的每一种5选3组合分配一个密钥，例如把密钥0分给特工1、2、3，把密钥1分给特工1、2、4，把密钥9分给特工3、4、5。这样的话，任意两个人在场都无法打开文件，因为他们始终缺少一把钥匙（这把钥匙分给了其余三个人）。而任意三个人在场都足以打开文件，因为根据鸽笼原理，任何一个5选3组合中总有一个人落在这三个人当中。这样，我们便利用组合数学巧妙地解决了这一问题。
记得当年搞NOIp时，我犯过一个相当严重的错误：错误地把Floyd算法的i, j, k三层循环的位置顺序搞颠倒了。直到准备省选时我才突然意识到，Floyd算法应该最先枚举用于松驰操作的那个“中间变量”k，表示只经过从1到k的顶点的最短路；而我却一直习惯性地以为i, j, k应该顺次枚举。令人惊讶的是，这个错误跟了我那么久我居然从来都没有注意到过。后来，我发现有我这种经历的人不止一个。惯性思维很可能会让你接受一些明显错误的算法，并且让你用得坦坦荡荡，一辈子也发觉不了。
假使你需要把一个数组随机打乱顺序进行重排。你需要保证重排后的结果是概率均等、完全随机的。下面两种算法哪一种是正确的？其中，random(a,b)函数用于返回一个从a到b（包括a和b）的随机整数。
1. for i:=1 to n do swap(a[i], a[random(1,n)]);
2. for i:=1 to n do swap(a[i], a[random(i,n)]);
最近忙着迎新，很久没有更新了。见了很多可爱的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)!，这显然是不可能的。