http://www.newgrounds.com/portal/view/480006
http://www.deadwhale.com/play.php?game=874
今天玩到了一个超级有意思的Flash小游戏“Closure”，在这里跟大家推荐一下。游戏画面效果独特，规则简单而有新意，谜题设置巧妙，是难得一见的好游戏。这个游戏世界是一个唯心的世界，物质依赖于人的认识而存在。游戏世界遵从“主观不可见”的物理定律：凡是没被灯光照亮的地方，实际上都是不存在。
上面两个地址里的内容是一样的。这个游戏本来在newgrounds.com上，但是这个网站被那个掉了，大家上不了的话可以用后面那个链接。游戏有点大，要载入很久，左边那颗心脏是载入的进度条。游戏需要Flash Player 10。
某日凌晨4点多，网友Superwyh发来短信说，他梦到了这样一个颇具启发性的问题：如果我们能够证明两个数之间不存在其它的数，这是否足以说明这两个数是相等的？正好当时我还没睡，稍微想了一下，发现这个命题是成立的，因为它的逆否命题显然成立。倘若两个数不相等，那它们之间一定能够插入其它的数（例如这两个数的算术平均值）；反过来，如果两个数之间无法插入别的数，这两个数自然就应该相等了。
这个命题是相当具有启发性的。或许有人会想，能不能用这一思路去证明两个数相等呢？
关于两数是否相等的争论，最著名的就是那个关于0.9999....和1是否相等的问题了。这一问题理解起来简单，细想起来争议颇大，真可谓是一个全民化的数学争论，与著名的Monty Hall问题有得一拼。不了解极限概念的人可能会说，不管你在后面写多少个9，它都不能达到1的，量变和质变存在本质上的区别。因此，当高中数学课上老师明确指出0.9999....精确地等于1时，还是有不少人瞠目结舌，甚至高声反对。
偶然看到这个网页，很是受启发，然后自己也没事干，一个人躺在床上想了很多。
昂贵而奢侈的房间
制造一个房间将变得非常的昂贵，也将变得非常非常奢侈。为了建造一个1000维的立方体空间，你需要在2000个方向上各修建一个999维的墙，即使墙的“厚度”很小很小，这也需要耗费大量的人力、物力和财力。同时，这样的房间也将非常非常非常大。假设1000维空间中的人是一个边长一米的超立方体，边长两米的超立方体房间里可以容纳10^300个人。当然，也许有人会问，为什么不把房间边长定小一些呢？如果房间边长仅有1.01米，容量也超过20000了啊？其实，房间容量大了没有任何意义，人多了照样挤不下。正如把一个单位大小的三维立方体放进边长为1.5米的三维立方体盒子中一样，虽然余下的空间超过了两立方米，但这点空间仍然不可能挤下哪怕再多一个的单位立方体。
死一般的世界
不要对高维世界抱有任何美好的幻想。1000维世界里是一片黑暗的。在1000维世界中，发光体再也牛B不起来了。半径为2的超球体，体积是单位超球体的10^300倍；因此随着与光源的距离的增加，照度以难以想象的恐怖速度垂直递减。类似地，1000维世界也是无声的。要想让声音传到10米外的地方，需要耗费的能量是一个天文数字。
在这样的世界中，生物将无法进行远程交流，甚至不会进化出视觉和听觉能力。一切社交行为都是以直接接触的形式发生的。另外一种可能是，当被动接收外界能量不可能实现时，生物将进化出一种主动探测外部世界的能力。生物可以发出一种集中程度高、不易向四周弥散的能量束，该能量束能够沿原路返回，使得生物能定向地获取外部信息。
正如宇宙射线、暗物质、反物质等一些我们（或许是因为缺少某种感觉器官而）感受不到，但事实上确实存在的东西一样，1000维世界中的科学家猜想有光源、声源等自然能量产生。他们投入了大量精力，耗尽了身边可用的资源，企图创造出一个可测量的尺度下的能量源。发现自然的光源和声源将成为物理学界的前沿科学，或者被宗教利用，成为一种具有蛊惑性的仪式。
密钥是密码的命根，一切不安全的秘密交换都源于不安全的密钥交换。目前，绝大多数协议采取RSA算法进行密钥交换，但在RSA算法出现之前，人们又是怎么做的呢？据说，第一个密钥交换算法是一个名叫Ralph Merkel的人在1974年发明的，算法叫做Merkle's Puzzles。这是一个非常奇特、非常邪恶的密钥交换协议。
假设A和B想进行秘密通信，他们需要选取一个密钥。A准备好很多很多个形如“密钥编号为X_i，密钥是Y_i”的消息，其中X_i是一个随机标识符，Y_i是一个随机密钥。消息的个数越多越好，起码要有几十万几百万条。然后，A把这些消息都编码为一个个难题，比方说对第i条消息异或一个大质数P_i，并宣称P_i是某个数N_i最小的那个质因子。A把所有编码后的消息全部发给B。B收到这些消息之后，随便选择一条消息进行暴力破解（在上例中就是暴力分解某个N_i），得到某一对对应的x和y。B用明文给A发一个消息，说“我们就用编号为x的密钥吧”。由于A知道这个x对应的是哪个y，因此A知道B说的密钥是哪个。
这个协议的核心就是，第三者不知道B当时选的是哪条消息。如果有第三者截获了他们之间的通信，要想获得密钥y，他必须一一破解所有的难题，直至解开了那个编号为x的密钥消息。由于这样的难题数量大得惊人，第三者要花费的努力是B的上百万倍。假如用计算机暴力破解一个难题需要一个小时的时间，那么第三者即使有百倍于B的计算能力，他也需要平均一年多才能解到正确的x和y。
刚过完年回到家，也跟大家说一声新年快乐。
今天莫名其妙地收到一封邮件，邀请我参加felicity.iiit.ac.in举办的几个编程比赛。我看了一下介绍，这些比赛还是挺有意思的，这里向大家推荐一下。
http://felicity.iiit.ac.in/codecraft/
CodeCraft，举办了两三年了，一个传统方式的编程比赛。
测试赛：14th Feb, 6pm - 8pm IST (GMT +5:30).
正式比赛：15th Feb, 2pm - 10pm IST (GMT +5:30).
http://felicity.iiit.ac.in/~math/
MathematiKa，已经举办过一年了，这是第二年的比赛。比赛共12道数学题，你只需要提交答案即可。例如，去年的第四题叫你计算前30个正整数x使得F(x) = 5x^2 + 14x + 1是一个完全平方数。提交时，把所有30个数从小到大连接在一起即可。最大的那个x有十几位，因此这题硬算是不行的。
测试赛：12th Feb, 6pm - 9pm IST (GMT +5:30).
正式比赛：13th Feb, 2pm - 10pm IST (GMT +5:30)
这个名叫Caterpillar飞船的图形是有史以来最大的生命游戏构造，它的宽度为4195，高度为330721，要想完整地显示出整个图案需要2000多个显示屏。整个图像即使压缩成RLE文件也有29MB，多数生命游戏模拟软件都无法成功处理。它的周期为270代，每过270代之后整个飞船将竖直移动102个单位，也就是说整个飞船以17c/45的速度向前飞行（c是生命游戏世界中的光速，即一格每代，任何物体都不能超过这个速度）。
下图以1:40的比例展示了整个构造图。
电影中经常出现这样的情节：有一份绝密文件需要交给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组合中总有一个人落在这三个人当中。这样，我们便利用组合数学巧妙地解决了这一问题。
Hash表是一个很有用的数据结构，它用O(N)的空间描述一个元素在0到N-1范围内的集合，支持常数级别的添加、删除和查询。遗憾的是，Hash表不能在常数时间内批量删除元素，返回全部元素也需要O(N)的时间，而理论上说这几个操作可以做的更好。现在，你能否设计一个数据结构，它同样占用O(N)的空间，支持常数时间的添加、删除、查询、清空（删除所有元素）、势查询（返回元素个数），以及O(n)时间的元素遍历（其中n表示集合中的元素个数）。
Matrix67 |
2009-01-31 23:37 | 
