趣题:随机选取两个无穷大的图,求两者相同的概率

    假设我们俩各自独立地随机选取一个有无穷多个顶点的图(两点之间1/2的概率有边1/2的概率没有边)。那么,我们俩选到相同的图的概率是多少?

    令人难以置信、但想通了之后又异常显然的是,两个图相同的概率为1。并且,我可以精确地告诉你,这个相同的图是什么样子的。考虑这样一个无穷大的图,我们用自然数1, 2, 3, …给所有顶点标号,然后如果y的二进制表达中的右起第x位为1,就在顶点x和顶点y之间连一条线。比如,顶点5就和顶点1、顶点3相连。我可以证明,我们俩都100%地会选取到上述这个图。

Read more…

俄罗斯方块可以永无止境地玩下去吗?

    大家在玩俄罗斯方块的时候有没有想过这样一个问题:如果玩家足够牛B的话,是不是永远也不可能玩死?换句话说,假设你是万恶的游戏机,你打算害死你面前的玩家;你知道任意时刻游戏的状态,并可以有针对性地给出一些明显不合适的方块,尽量迫使玩家面对最坏情况。那么,你有没有一种算法能保证害死玩家,或者玩家无论如何都存在一种必胜策略呢?注意,俄罗斯方块的游戏区域是一个宽为10,高为20的矩形,并且玩家可以预先看到下一个给出的方块是什么。在设计策略时,你必需考虑到这一点。

  

    相信很多人有过这样的经历:玩俄罗斯方块时一开局就给你一个“S”型方块,让完美主义者感到异常别扭;结果,第二个方块还是这个“S”,第三个方块依旧是“S”,相当令人崩溃。于是,我们开始猜测,如果游戏机给你无穷个“S”形方块,玩家是不是就没有解了?答案是否定的。如图1,从第10步开始,整个局面产生一个循环;只要机器给的一直都是“S”方块,玩家可以不断重复这几个步骤,保证永远也死不了。

    不过,这个循环是在游戏场地清空了的情况下才产生的。有人会进一步想了,要是在玩着玩着,看着你局势不好时突然给你无穷多个“S”方块呢?事实上,此时局面的循环依然可能存在,如图2。在第5个“S”形方块落地后,循环再次产生。

Read more…

有限域的二次剩余与x^2+y^2=c的解的个数

    上个月的UyHiP谜题涉及到一些抽象代数的东西:考虑一个有f个元素的有限域,其中c是有限域中的一个元素。试求x^2+y^2=c有多少个解。你的答案应该是一个关于f和c的函数。

    有趣的是,对所有c≠0的情况,x^2+y^2=c的解的个数与c都是无关的。事实上,方程解的个数只与f模4的余数和c是否为零元有关。具体地说:

  c = 0 c ≠ 0
f mod 4 = 0 或 2 f f
f mod 4 = 1 2f – 1 f – 1
f mod 4 = 3 1 f + 1

Read more…