1956年Robert Abbott发明了一个全新的纸牌游戏叫做Eleusis，后来Martin Gardner在1959年6月的Scientific American杂志上介绍了这个游戏。77年10月这个游戏又进一步得到完善，并发展出一些其它的玩法。最近，John Golden提出了这个游戏的第三个版本Eleusis Express，他比Eleusis更简单，更完备，平均游戏时间也更短。Robert Abbott对这个游戏非常满意，这种简单而有趣的推理游戏很可能会像杀人游戏一样流行起来。下面我简单介绍一下这个游戏的规则，你将会看到一种集策略和推理于一体的全新的纸牌游戏。

    这个游戏的规则极其简单，但变化也异常丰富，因为这个游戏的出牌方式是不固定的，游戏开始时玩家甚至不知道出牌的规则是什么。玩家的主要任务就是在游戏过程中探索出牌的规则。游戏需要两副牌，玩家以3到8人为宜。每轮游戏前，玩家需要推选出一位主持人，主持人在这个游戏里扮演最重要的角色。游戏开始前，主持人自己在心里默想一个出牌规则(Secret Rule)，但不能告诉玩家。规则的内容应该只考虑扑克牌的花色与点数，与出牌人、牌的摆放方式等无关。这个规则必须简单、明确，通常以“如果上一张牌是什么什么，那么下一张牌就该接什么什么”一类的形式给出，比如“如果上一张牌是红色，下一张牌就是黑色；如果上一张牌是黑色，下一张牌就该是红色”，或者是“要么与前一张牌同花色，要么与前一张牌同点数”。然后主持人洗牌，给每个人发12张牌，然后再翻出一张放在桌面上作为第一张牌打出。这张牌及后面正确的跟牌都摆成一行，叫做主线(Mainline)；主线下方可能会有若干边线(Sideline)，表示错误的跟牌。游戏正式开始前，主持人可以对秘密规则进行一些提示，之后玩家轮流打牌，主持人判断玩家打出的牌是否符合他的规则：

    
如果打出的牌符合规则
    此时主持人把这张牌加在主线的右边，该玩家手中的牌就少了一张。如果此时该玩家手中的牌打完了，则游戏结束，否则游戏继续进行。
    另外，该玩家还可以获得一次猜测出牌规则的机会，同时每个玩家都必须听他说的答案。如果该玩家猜对了，主持人也宣布游戏结束，否则游戏继续。
如果打出的牌不符合规则
    此时主持人把这张牌放在的相应的边线位置上，告诉大家这张牌不能接在这个位置。这名玩家需要再摸一张牌，手中的牌的张数不变。

    轮到某位玩家出牌时，该玩家可以选择不出牌，即宣称自己无牌可打。此时他应该把手中的牌摊出来给所有人看，同时主持人判定该玩家是否确实无牌可打：
如果该玩家确实无牌可打
    如果此时玩家手中只有一张牌，游戏结束。否则，主持人清点该玩家手中牌的数目N，把它们放回还没发完的牌摞的最底下，再发给他N-1张牌。同时，该玩家获得一次猜测出牌规则的机会，猜对了同样可以直接获胜。
如果该玩家有可以打的牌
    此时主持人从中选出一张可以打的牌接在主线后面，该玩家收起自己其余的牌并再摸一张，保持手中的牌数不变。

    游戏结束后，每个人的得分就是自己打出去的牌的张数。打完所有牌而获胜的玩家再获3分的加分，猜对规则而获胜则得到6分的加分。主持人的得分与本轮最高分相同。然后大家重新推选主持人，继续下一轮游戏。
    如果牌抓完了但游戏还没结束，可以再洗一副牌继续进行，或宣布游戏结束，本轮不计分。然后，主持人阴笑几下，故弄玄虚地说出自己所想的规则，等待玩家们恍然大悟并集体发出“哎呀~~~”的叹息声（或者等待玩家大骂这规则太他妈BT了谁能想到啊）。
    若干轮游戏后，最终的胜者就是累积得分最高的人。我们可以适当给赢家一些奖励，比如让他亲一下最漂亮的MM玩家，或者传几个小A给他。得分最低的人也应当受到惩罚，比如叫他把MM共享出来让大家玩弄，或者贡献一个XX论坛的账号。

    能想到一个简单明了而又富有新意的规则是非常重要的，因此游戏的主持人是整个游戏的灵魂，一个思维活跃又爱捉弄人的主持人可以让游戏变得非常精彩。这里写一些自己想到的规则，大家有什么好的想法也可以在下面说一说。

• 按黑红梅方的顺序出牌
• 按三张红色，三张黑色，又三张红色，又三张黑色的顺序出牌
• 如果上一张牌的点数是1到7，则应该接8到K；如果上一张牌是8到K，则应该接1-7
• 相邻两张牌的点数之和大于10
• 相邻两张牌的点数的差的绝对值不超过3
• 相邻两张牌的点数加起来能被3整除
• 下一张牌的点数比上一张牌大1点、2点、3点或4点；数字大小关系是“循环的”
• 如果上一张牌的点数是奇数，则出红色牌；如果上一张牌的点数是偶数，则出黑色牌
• 如果上一张牌是红色，则出牌的点数小于等于上张牌的点数；否则，出牌的点数大于等于上张牌的点数
• 如果上一张牌的点数为平方数，则出牌的点数是非完全平方数；否则出牌的点数应该是一个平方数
• 牌的点数一大一小交替排列（即奇数位置上的牌比前面的点数小，偶数位置上的牌比前面点数大）
• 如果花色与前面一张相同，则点数必须比它大；如果花色与前面一张不同，则点数必须比它小

做人要厚道 转贴请注明出处
查看更多：http://www.logicmazes.com/games/eleusis/index.html

    定义f(n)的值为将n拆分成若干个2的幂的和，且其中每个数字出现的次数不会超过两次的方案数。规定f(0)=1。
    例如，有5种合法的方案可以拆分数字10：1+1+8, 1+1+4+4, 1+1+2+2+4, 2+4+4 和 2+8。因此，f(10)=5。
    请用一句最简单的话来描述集合{ f(n)/f(n-1) }。证明你的结论。

    注意：答案远比一个递归公式来得精辟，来得巧妙。如果你发现了我们的结论，你会一眼认定它为正确答案。

    答案：数列{ f(n)/f(n-1) }以最简形式包含了所有的正有理数。

    如果n是奇数（等于2m+1），那么数字1（即2^0）必须出现且只能出现一次。现在的问题就是，2m的拆分方案中有多少个方案不含数字1呢？稍作思考你会立即发现，它就等于f(m)，因为m的所有拆分方案的所有数都乘以2后正好与不含1的2m拆分方案一一对应。因此，f(2m+1) = f(m)
    如果n是偶数（等于2m），那么数字1要么没有出现，要么恰好出现两次。对于前一种情况，我们有f(m)种可能的方案；第二种情况则有f(m-1)种方案。因此，f(2m) = f(m) + f(m-1)
    另外，显然f(k)都是正数。于是，f(2k-1) = f(k-1) < f(k-1)+f(k) = f(2k)
    这样，我们可以得到以下三个结论：

    结论1：gcd( f(n),f(n-1) ) = 1
    证明：对n进行数学归纳。显然gcd( f(1),f(0) ) = gcd(1,1) = 1
    假设对于所有小于n的数结论都成立。根据n的奇偶性，下面两式中必有一个成立：
    gcd( f(n),f(n-1) ) = gcd( f(2m+1),f(2m) ) = gcd( f(m), f(m)+f(m-1) ) = gcd( f(m),f(m-1) ) = 1
    gcd( f(n),f(n-1) ) = gcd( f(2m),f(2m-1) ) = gcd( f(m)+f(m-1), f(m-1) ) = gcd( f(m),f(m-1) ) = 1

    结论2：如果f(n+1)/f(n) = f(n'+1)/f(n')，那么n=n'
    证明：还是数学归纳法。当max(n,n')=0时结论显然成立，因为此时n=n'=0。
    假如对于所有小于n的数结论都成立。由于f(2k-1)<f(2k)，那么要想f(n)/f(n-1) = f(n')/f(n'-1)，n与n'的奇偶性必须相同，于是可以推出f(m)/f(m-1) = f(m')/f(m'-1)，根据归纳我们有m=m'，这就告诉我们n=n'。

    结论3：对于任何一个有理数r，总存在一个正整数n使得r=f(n)/f(n-1)。
    证明：把r写成两个互素的数p和q的比。我们对max(p,q)施归纳。
    显然，当p=q=1时结论成立，此时n=1。
    不妨设p<q，那么定义r'为p/(q-p)。根据归纳假设，总存在一个数m满足r'=f(m)/f(m-1)。于是r=f(2m+1)/f(2m)。当p>q时同理可证明。

做人要厚道
转贴请注明出处

    不少人可能为找不到非传统题型的练习题而头疼。这几天我专门发出一些用于省选集训的题目供大家参考。

Problem 1: cell 手机
题目来源：USACO Contest FEB06 Gold (Translated by Matrix67)

问题描述
    奶牛们已经开始使用手机交流了，但它们发现手机的按键设计不适合它们的蹄子。它们想设计一个新的手机，让它的按键更少，但是更大。
    它们喜欢普通手机的一个功能：词语联想。每个按键都有一些字母和它对应，打出一个单词只需要按对应的按键。因为一个按键可能对应多个字母，因此某些单词可能会发生“歧意”。不过，大多数时候这种歧意可以通过用字典判断的方法来消除。
    考虑到奶牛们在自定义一款新的手机，它们还需要用奶牛字母表替换英文字母表。神奇的是，奶牛字母表中的字母恰好是英语字母表中的前L个字母，即使顺序也一样。它们想知道如何把这些字母分配给B个按键(1<=B<=L)使得在字典中不会产生歧意的单词最多。就像普通的手机一样，他们希望每个按钮上的字母都是字母表中一段连续的字母。

    这是一个答案提交类的题目。你只需要在你自己的计算机上计算出你的答案，然后把输出文件提交上来。与输入文件cell.3.in相对应的输出文件应该为cell.3.out，这里“3”表示你提交的答案是第3个输入文件的解。当然，其它输出文件需要把这个3替换成相应的数字。你不需要提交任何其它的文件。

输入数据
    第一行：一个整数N，表示这是第N个输入文件。
    第二行：两个用空格隔开的整数：B和L
    第三行：D，字典中的单词数(1<=D<=1000)
    第四行到第D+3行：每一行包含一个字典中的单词，用1到10个大写字母表示。这些单词按照字典序给出，并且保证没有重复。

输出数据
    第一行：字典中具有唯一的按钮序列的单词数。
    第二行到第B+1行：其中的第n行包含有第n个按钮上的字母，用大写的字母按照字典的顺序表示。所有行必须按照字典序排列，每个字母出现恰好一次。如果有多个最优解，选用第一个按键上字母最多的解。如果最优解仍然不唯一，考虑第二个按键上字母最多，依此类推。

样例输入(cell.1.in)
1
3 13
11
ALL
BALL
BELL
CALK
CALL
CELL
DILL
FILL
FILM
ILL
MILK

样例输出(cell.1.out)
7
AB
CDEFGHIJK
LM

样例说明
    第一个按键上只有AB两个字母，第二个按键上含有C到K，第三个按键上为LM。单词CELL、DILL、FILL和FILM的输入都是2233，其它7个单词的输入都是唯一的。

题解(Ctrl+A)：
    这道题目……搜索，乱搞。

Problem 2: selfstr 自描述序列
题目来源：Matrix67根据经典问题改编

问题描述
    “这句话里有1个数字零，2个数字一，1个数字二，0个数字三”。

    在N(N>=2)进制中只允许0到N-1这N个数字出现。一个N位的N进制数（允许有前导0）可以由另一个同样多位的数来描述。我们定义一个N位N进制数的描述序列为：左起第i个数字为原数中数字i-1出现的次数。
    例如，在4进制中，0023的描述序列为2011，因为0023中有2个0，0个1，1个2和1个3。
    我们惊奇地发现，4进制数1210的描述序列是它本身！我们称这样的数叫做“自描述序列”。

    你需要编写程序计算出在某个进制下的自描述序列。一个进制下的自描述序列可能有很多个，你只需要给出其中一个即可。
    这是一个答案提交类的问题。你只需要在你自己的计算机上计算出你的答案，然后把输出文件提交上来。与输入文件selfstr.3.in相对应的输出文件应该为selfstr.3.out，这里“3”表示你提交的答案是第3个输入文件的解。当然，其它输出文件需要把这个3替换成相应的数字。你不需要提交任何其它的文件。

输入格式
    输入数据只有一个正整数N

输出格式
    输出N个字符，它表示N进制下的自描述序列。在高于10的进位制下，大于9的数字请用大写字母表示。
    如果有多种可能的解，你只需要输出其中一个。
    如果该进制下无解，请输出“NONE”。

样例输入(selfstr.1.in)
4

样例输出(selfstr.1.out)
1210

题解：
    这道题太有意思了！首先，你需要先算几个小数据。你会发现，算到N>=6后，渐渐有规律了：

   N   N进制下的自描述序列
   4    1210 or 2020
   5    21200
   6    NONE
   7    3211000
   8    42101000
   9    521001000

    事实上，这道题目就是考你当搜索到一些解后能不能找到规律得到所有解。这里我们发现，对所有N>6，至少存在一个解为R21(0…0)1000，其中R=N-4，中间0的个数为N-7。结论显然正确。
    有可能除了这个之外存在其它的解，因此我们仍然需要写一个check来核对答案。

Problem 3: relation 大小关系
题目来源：Matrix67根据经典问题改编

问题描述
    用关系“ < ”和“ = ”将3个数a、b、c依次序排列时，有13种不同的序列关系：
      a=b=c, a=b<c, a<b=c, a<b<c, a<c<b
      a=c<b, b<a=c, b<a<c, b<c<a, b=c<a
      c<a=b, c<a<b, c<b<a

    用这两种关系连接N个数有多少种不同的方案？

    这是一个答案提交类的问题。所有选手将得到10个输入数据，你只需要在你自己的计算机上计算出你的答案，然后把你的答案提交上来。与输入文件relation.x.in相对应的输出文件应该为relation.x.out，这里x表示一个1到10之间的数。

输入格式
    输入一个整数，表示N。

输出格式
    输出用小于和等于符号将N个数进行有序排列的方案数。

样例输入(relation.1.in)
3

样例输出(relation.1.out)
13

题解：
    组合数学+高精度。由于数据规模很小，我就直接搞成了答案提交类的题目。
    下面给出两种递推方法：
    Solution 1: N个数中必然存在一个最大的“等价类”，如果这个等价类里有k个数，那么剩下的数就有F(N-k)种排列方案。别忘了我们需要枚举这k个数是哪k个数。于是，F(N)
=C(N,1)F(N-1)+C(N,2)F(N-2)+C(N,3)F(N-3)+ … +C(N,N)F(0)
    Solution 2: 用F[ i, j]表示 i个数中有j 个等价类的排列方案（就是说有j-1个小于符号）。第 i个数有可能并入了F[i-1, j]中的 j个等价类中的一个，也有可能不与任何一个已有的数相等，独自成为一个等价类插入F[i-1, j-1]里产生的 j个空位中。于是，F[ i,j ]=F[i-1, j]*j + F[i-1,j-1]*j。

其它问题：
    如何用Cena评测答案提交类问题？
        见http://www.matrix67.com/blog/article.asp?id=176
    这些题的数据哪里有？
        第一题：http://ace.delos.com/FEB06，GOLD DIVISION里面的第三个
        第二题：自己写check，不需要数据
        第三题：http://www.research.att.com/~njas/sequences/b000670.txt，吓死你

Matrix67原创
转贴请注明出处

    我们年级有许多漂亮的MM。一班有7个左右吧，二班大概有4个，三班最多，16个，四班最可怜，一个漂亮的MM都没有，五班据说有1个。如果用一个函数“f(班级)=漂亮MM的个数”，那么我们可以把上述信息表示成：f(1)=7,f(2)=4,f(3)=16,f(4)=0,f(5)=1,等等。
    生成函数（也有叫做“母函数”的，但是我觉得母函数不太好听）是说，构造这么一个多项式函数g(x)，使得x的n次方系数为f(n)。于是，上面的f函数的生成函数g(x)=7x+4x^2+16x^3+x^5+…。这就是传说中的生成函数了。关键是，这个有什么用呢？一会儿要慢慢说。我敢打赌这绝对会是我写过的最长的一篇文章。

    生成函数最绝妙的是，某些生成函数可以化简为一个很简单的函数。也就是说，不一定每个生成函数都是用一长串多项式来表示的。比如，这个函数f(n)=1 （n当然是属于自然数的），它的生成函数就应该是g(x)=1+x+x^2+x^3+x^4+…（每一项都是一，即使n=0时也有x^0系数为1，所以有常数项）。再仔细一看，这就是一个有无穷多项的等比数列求和嘛。如果-1<x<1，那么g(x)就等于1/(1-x)了。在研究生成函数时，我们都假设级数收敛，因为生成函数的x没有实际意义，我们可以任意取值。于是，我们就说，f(n)=1的生成函数是g(x)=1/(1-x)。

    我们举一个例子说明，一些具有实际意义的组合问题也可以用像这样简单的一个函数全部表示出来。
    考虑这个问题：从二班选n个MM出来有多少种选法。学过简单的排列与组合的同学都知道，答案就是C(4,n)。也就是说。从n=0开始，问题的答案分别是1,4,6,4,1,0,0,0,…（从4个MM中选出4个以上的人来方案数当然为0喽）。那么它的生成函数g(x)就应该是g(x)=1+4x+6x^2+4x^3+x^4。这不就是……二项式展开吗？于是，g(x)=(1+x)^4。
    你或许应该知道，(1+x)^k=C(k,0)x^0+C(k,1)x^1+…+C(k,k)x^k；但你或许不知道，即使k为负数和小数的时候，也有类似的结论：(1+x)^k=C(k,0)x^0+C(k,1)x^1+…+C(k,k)x^k+C(k,k+1)x^(k+1)+C(k,k+2)x^(k+2)+…（一直加到无穷；式子看着很别扭，自己写到草稿纸上吧，毕竟这里输入数学式子很麻烦）。其中，广义的组合数C(k,i)就等于k(k-1)(k-2)…(k-i+1)/i!，比如C(4,6)=4*3*2*1*0*(-1)/6!=0，再比如C(-1.4,2)=(-1.4)*(-2.4)/2!=1.68。后面这个就叫做牛顿二项式定理。当k为整数时，所有i>k时的C(k,i)中分子都要“越过”0这一项，因此后面C(k,k+1),C(k,k+2)之类的都为0了，与我们的经典二项式定理结论相同；不同的是，牛顿二项式定理中的指数k可以是任意实数。

    我们再举一个例子说明一些更复杂的生成函数。n=x1+x2+x3+…+xk有多少个非负整数解？这道题是学排列与组合的经典例题了。把每组解的每个数都加1，就变成n+k=x1+x2+x3+…+xk的正整数解的个数了。教材上或许会出现这么一个难听的名字叫“隔板法”：把n+k个东西排成一排，在n+k-1个空格中插入k-1个“隔板”。答案我们总是知道的，就是C(n+k-1,k-1)。它就等于C(n+k-1,n)。它关于n的生成函数是g(x)=1/(1-x)^k。这个生成函数是怎么来的呢？其实，它就是(1-x)的-k次方。把(1-x)^(-k)按照刚才的牛顿二项式展开，我们就得到了x^n的系数恰好是C(n+k-1,n)，因为C(-k,n)*(-x)^n=[(-1)^n*C(n+k-1,n)]*[(-1)^n*x^n]=C(n+k-1,n)x^n。这里看晕了不要紧，后文有另一种方法可以推导出一模一样的公式。事实上，我们有一个纯组合数学的更简单的解释方法。因为我们刚才的几何级数1+x+x^2+x^3+x^4+…=1/(1-x)，那么(1+x+x^2+x^3+x^4+…)^k就等于1/(1-x)^k。仔细想想k个(1+x+x^2+x^3+x^4+…)相乘是什么意思。(1+x+x^2+x^3+x^4+…)^k的展开式中，n次项的系数就是我们的答案，因为它的这个系数是由原式完全展开后k个指数加起来恰好等于n的项合并起来得到的。

    现在我们引用《组合数学》上暴经典的一个例题。很多书上都会有这类题。
    我们要从苹果、香蕉、橘子和梨中拿一些水果出来，要求苹果只能拿偶数个，香蕉的个数要是5的倍数，橘子最多拿4个，梨要么不拿，要么只能拿一个。问按这样的要求拿n个水果的方案数。
    结合刚才的k个(1+x+x^2+x^3+x^4+…)相乘，我们也可以算出这个问题的生成函数。

g(x)=(1+x^2+x^4+…)(1+x^5+x^10+..)(1+x+x^2+x^3+x^4)(1+x)
    =[1/(1-x^2)]*[1/(1-x^5)]*[(1-x^5)/(1-x)]*(1+x) （前两个分别是公比为2和5的几何级数，
                                                     第三个嘛，(1+x+x^2+x^3+x^4)*(1-x)不就是1-x^5了吗）
    =1/(1-x)^2   （约分，把一大半都约掉了）
    =(1-x)^(-2)=C(1,0)+C(2,1)x+C(3,2)x^2+C(4,3)x^3…   （参见刚才对1/(1-x)^k的展开）
    =1+2x+3x^2+4x^3+5x^4+….

    于是，拿n个水果有n+1种方法。我们利用生成函数，完全使用代数手段得到了答案！
    如果你对1/(1-x)^k的展开还不熟悉，我们这里再介绍一个更加简单和精妙的手段来解释1/(1-x)^2=1+2x+3x^2+4x^3+5x^4+….。
    1/(1-x)=1+x+x^2+x^3+x^4+…是前面说过的。我们对这个式子等号两边同时求导数。于是，1/(1-x)^2=1+2x+3x^2+4x^3+5x^4+….。一步就得到了我们所需要的东西！不断地再求导数，我们同样可以得到刚才用复杂的牛顿二项式定理得到的那个结论（自己试试吧）。生成函数还有很多其它的处理手段，比如等式两边同时乘以、除以常数（相当于等式右边每一项乘以、除以常数），等式两边同时乘以、除以一个x（相当于等式右边的系数“移一位”），以及求微分积分等。神奇的生成函数啊。
    我们用两种方法得到了这样一个公式：1/(1-x)^n=1+C(n,1)x^1+C(n+1,2)x^2+C(n+2,3)x^3+…+C(n+k-1,k)x^k+…。这个公式非常有用，是把一个生成函数还原为数列的武器。而且还是核武器。

    接下来我们要演示如何使用生成函数求出Fibonacci数列的通项公式。
    Fibonacci数列是这样一个递推数列：f(n)=f(n-1)+f(n-2)。现在我们需要求出它的生成函数g(x)。g(x)应该是一个这样的函数：
    g(x)=x+x^2+2x^3+3x^4+5x^5+8x^6+13x^7+…
    等式两边同时乘以x，我们得到：
    x*g(x)=x^2+x^3+2x^4+3x^5+5x^6+8x^7+…
    就像我们前面说过的一样，这相当于等式右边的所有系数向右移动了一位。
    现在我们把前面的式子和后面的式子相加，我们得到：
    g(x)+x*g(x)=x+2x^2+3x^3+5x^4+8x^5+…
    把这最后一个式子和第一个式子好好对比一下。如果第一个式子的系数往左边移动一位，然后把多余的“1”去掉，就变成了最后一个式子了。由于递推函数的性质，我们神奇地得到了：g(x)+x*g(x)=g(x)/x-1。也就是说，g(x)*x^2+g(x)*x-g(x)=-x。把左边的g(x)提出来，我们有：g(x)(x^2+x-1)=-x。于是，我们得