在 2048 里能够得到的最大的数是多少?

Michael Brand 在 Using your Head is Permitted 趣题站 2014 年 4 月的谜题中提出了一个这样的问题:在最近非常流行的小游戏 2048 中,你能得到的最大的数是多少?

在这里,我们简单描述一下游戏的规则。游戏在一个 4 × 4 的棋盘上进行,棋盘里填有一个个的“数块”,每个数块上都写有某个形如 2n 的正整数。每一步,你需要从上、下、左、右四个方向中选取一个方向,按下对应的方向键之后,所有的数块都会“落”到这个方向;若有两个同种的数块在此过程中发生碰撞,则它们的值会相加起来,并合成一个新的数块。然后,系统会在棋盘中随机选择一个空白位置,并在此生出一个新的数块,上面写有数字 2 或者数字 4 (两种情况之比为 9 : 1)。游戏开始时,棋盘上会自动生成两个随机的数块,你的目标就是通过有限步的操作,得出一个写有 2048 的数块。当然,即使得到了 2048 这个数块,游戏也不会自动结束,你还可以向更大的数发起挑战。于是就有了我们刚才的问题:理论上,这个游戏当中能够得到的最大的数是多少?

Read more…

Thue-Morse 序列与免平方字符串

字符串 hello 当中连续出现了两个 l 。字符串 prototype 当中连续出现了两个 ot 。字符串 nonsense 当中连续出现了两个 nse 。如果某个字符串中连续出现了两个相同的片段,换句话说这个字符串里面含有形如 XX 的模式(其中 X 代表一个子串),我们就说这个字符串中含有一个“平方”(square)。如果某个字符串中没有平方出现,我们就说这个字符串是“免平方”的(square-free)。

如果只使用两种字符,比方说字符 0 和字符 1 的话,我们只能构造出一些长度非常有限的免平方字符串。事实上,我们只能构造出以下 6 个免平方字符串: 0 、 1 、 01 、 10 、 010 、 101 。然而,如果允许使用三种字符,比方说字符 0 、 1 、 2 的话,我们不但能够构造出任意长的免平方字符串,还能构造出无限长的免平方字符串。在继续阅读下去之前,你不妨先自己试试看。

Read more…

趣题:只允许加倍操作的水桶倒水问题

    今天的题目来自这里。有三个水桶,它们里面分别装了 a 升的水、 b 升的水和 c 升的水(其中 a 、 b 、 c 都是正整数,桶本身没有容量限制)。你可以把水从一个桶倒进另一个桶,但必须保证让后者的水量刚好变成原来的两倍。证明,不管 a 、 b 、 c 是多少,你总能让其中某一个水桶变空。

    例如,假设初始时 (a, b, c) = (3, 2, 1) ,那么你可以先把 (3, 2, 1) 变成 (1, 4, 1) ,再把它变成 (2, 4, 0) ,从而把第三个水桶变空。

Read more…

趣题:老鼠与毒药问题的推广

    今天的趣题来源于 IBM Ponder This 三月份的谜题

    大家应该都听说过这个老题目:有 1000 个一模一样的瓶子,其中有 999 瓶是普通的水,有一瓶是毒药。任何喝下毒药的生物都会在一星期之后死亡。现在,你只有 10 只小白鼠和一星期的时间,如何检验出哪个瓶子里有毒药?

    这个问题的答案也堪称经典:把瓶子从 0 到 999 依次编号,然后全部转换为 10 位二进制数。让第一只老鼠喝掉所有二进制数右起第一位是 1 的瓶子,让第二只老鼠喝掉所有二进制数右起第二位是 1 的瓶子,等等。一星期后,如果第一只老鼠死了,就知道毒药瓶子的二进制编号中,右起第一位是 1 ;如果第二只老鼠没死,就知道毒药瓶子的二进制编号中,右起第二位是 0 ⋯⋯每只老鼠的死活都能确定出 10 位二进制数的其中一位,由此便可知道毒药瓶子的编号了。

    现在,有意思的问题来了:如果你有两个星期的时间(换句话说你可以做两轮实验),为了从 1000 个瓶子中找出毒药,你最少需要几只老鼠?注意,在第一轮实验中死掉的老鼠,就无法继续参与第二次实验了。

Read more…

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

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

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

Read more…