心电图数列 (EKG Sequence) 的定义简单而有趣：第一项为 1 ，第二项为 2 ，以后的每一项都是最小的和前一项不互质并且不曾出现过的数。换句话说，数列 a(1)=1 ， a(2)=2 ，且当 n>2 时取 a(n) 为所有满足以下两个条件的数中最小的那一个：该数与 a(n-1) 有大于 1 的公约数，并且该数与前面 n-1 项都不相等。心电图数列的前面 20 项为
1, 2, 4, 6, 3, 9, 12, 8, 10, 5, 15, 18, 14, 7, 21, 24, 16, 20, 22, 11 ...
为什么它叫做心电图数列呢？原因很简单——因为把它描绘在图象上时，看上去像一张心电图。
某日夜里我突发奇想，想到用分形图形来表示各种几何级数，于是写下了上一篇日志。日志发出后我收到了相当多的回复，很多网友告诉我说，这篇日志还留下了很多空白，大有扩展的潜力和推广的空间，非常具有启发性。网友morrowind在原日志第29楼评论说，大图形里面放置若干个相似的小图形时，并不一定要对应边与对应边相拼。考虑一个边长分别为1和根号5的矩形，它能够轻易地分成五个相同的小矩形，并且每一个都和原来的相似。这样的话，我们便又能递归地表示(1/5)^n了。只要能够递归地表示出(1/5)^n，从图形上我们总可以得出Σ(1/5)^n=1/4的结论，因为在每一个尺度下总有四个未被继续分割的区域，其中染色的区域始终占据了1/4。
12楼的est用一个极其简单的式子给出了Σ(1/5)^n=1/4的证明：在五进制中，0.1 + 0.01 + 0.001 + 0.0001 + ... = 0.11111...，这恰好就说明了1/5 + 1/25 + 1/125 + .. = 1/4。上述两套证明方案对所有大于2的正整数n都成立，并且仔细思考你会看出它们的本质是相同的：0.11111...就是0.44444...的1/4，因为在每一个小数位上前者都是后者的1/4。
小学时经常在计算器上面按12345679这个神秘的8位数。这个数牛就牛在，它乘以9的结果正好等于111111111。你可以在计算器上输好12345679，然后问MM“你的幸运数字是多少”；如果她说“7”，你就在计算器上按“乘以63”，计算器上将会显示出清一色的7字，看上去无比壮观。
假如123456789×9=1111111111的话，我倒不会觉得奇怪。网上流行过一个火星帖子，写了一大堆诸如111111111 * 111111111 = 12345678987654321的式子来展示数学之美，以至于大家会认为123456789×9的结果也一定是一串很有规律的数字。因此，如果我不在这里说一句123456789×9其实并不等于1111111111的话，估计很多人都发现不了问题。事实上，123456789×9=1111111101，偏偏就差一个“1”。而怪就怪在，去掉被除数中的数字“8”，偏偏又有了12345679×9=111111111，一个极其别扭的算式反而得到了完美的结果。不要让你的直觉被数学之美所蒙蔽，数学上有大量出人意料的、看上去很不对称的结论。
为什么偏偏要少一个“8”呢？难道这真的是算术中的一个不可抹去的疤痕？我们急需要寻求一个解释，填补上算术中的这个不和谐的“漏洞”。一种解释是，我们看到了123456789×9=1111111101并不美观，想要对其进行改造，进而得到(123456789+1)*9 = 1111111101+9 = 1111111110，于是(123456789+1)*9/10 = 12345679*9 = 111111111。用这种办法的确可以解释“迷失的8”，不过这个解释并不漂亮。为了寻求一个更好的解释，我们来看一看111111111和9的关系。
上次我们谈到，我们考虑时间复杂度时往往假设任意大的整数运算（赋值、四则运算、取余运算、比较运算、位运算包括左移右移）都可以在常数时间内完成，殊不知这留下了一个非常具有研究价值的漏洞：能否利用计算机理想模型中的整数运算，把问题打包成超大整数后并行计算，从而办到一些在普通计算机上无法办到的事情？我们在上一次的文章中介绍了利用“大整数随便算”的漏洞“耍赖”得到了一个线性时间的排序算法。这个漏洞真的已经被充分利用了吗？我们还能从里面榨出多少汁水来？令人无法想象的是，线性时间的排序算法远远没有挖掘到理想大整数运算的巨大潜力，事实上我们能做到常数时间的排序！问题和解答仍然来自Using your Head is Permitted，在这里向Michael Brand表示深深的膜拜。
自然，说“常数时间排序”是有前提条件的，否则即使读入输出也得耗费线性的时间。不过，我们可以假设所有待排序的数都已经打包进一个大整数里，输出时也无需解包，直接返回另一个大整数即可。在这样的情况下，我们完全可以用常数时间完成排序。换句话说，我可以用O(1)的时间，“一下子”就把0100 0111 0001 0010变成0001 0010 0100 0111，不管这个大整数里面装了多少个数。为了方便大家阅读和思考，我们再取一些名字，方便描述。我们把由多个数构成的大整数叫做“整数串”。整数串中所含的数都是二进制，它们用空格隔开。整数串中每个数的位数都必须相等，位数不够用零补足。我们把这个位数叫做“定宽”，本文例子的定宽都是4。
如果说数学家是魔术师的话，无穷就是一根最强大的魔杖。在Manfred Schröder的一篇题为Fractals in Music的论文里，作者提到，把每个正整数对应的二进制数中“1”的个数依次写下来，得到的数列有一个很神奇的性质：划掉所有的奇数项，得到的序列仍然是整个序列本身。
十进制数 1 2 3 4 5 6 7 8 9 10 11 12 13 14
二进制数 1 10 11 100 101 110 111 1000 1001 1010 1011 1100 1101 1110
1的个数 1 1 2 1 2 2 3 1 2 2 3 2 3 3
取偶数项 1 1 2 1 2 2 3
最初我是在《算法艺术与信息学竞赛》里见到这个东西的，当时硬是被震撼住了。这样的序列叫做“自相似序列”，意思是说自己的一部分等于本身。注意到，这个“自相似”可以无限制地进行下去。再次取出所得的序列中的偶数项，结果还是与最初的序列一样；再这样做下去做无数次，每一次的结果都会与原始序列相同。也就是说，无穷里面包含了无穷多个规模不同的无穷，并且所有这些无穷都和原来完全相同。不过呢，仔细一想你会发现这个一点也不奇怪，奥妙就在于，n和2n的二进制表达中唯一的差别就是末尾的那个“0”。
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论坛的账号。
能想到一个简单明了而又富有新意的规则是非常重要的，因此游戏的主持人是整个游戏的灵魂，一个思维活跃又爱捉弄人的主持人可以让游戏变得非常精彩。这里写一些自己想到的规则，大家有什么好的想法也可以在下面说一说。
做人要厚道 转贴请注明出处
查看更多：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时同理可证明。
做人要厚道
转贴请注明出处
Matrix67 |
2010-02-20 0:06 | 
