趣题:用四个数学运算符号译出 EBCDIC 编码

ASCII 编码已经是非常直观了。 65 号字符就是大写字母 A , 66 号字符就是大写字母 B ,以此类推, 90 号字符就是大写字母 Z 。为了看出某个编码究竟对应字母表中的第几个字母,我们只需要用下面的函数关系即可:

f(x) = x - 64

整个函数关系极其简单,里面只包含一个数学运算符号。

当然,历史上也出现过很多非常不直观的字符编码方式。 EBCDIC 是由 IBM 提出的一种字符编码标准,它的编码方式十分古怪,可害苦了当年的那些程序员。据说,当年的程序员没有一个不痛恨 EBCDIC 的。因此, EBCDIC 也理所当然地成为了众人调侃的对象。 Wikipedia 上的 EBCDIC 页面甚至还专门有一节,讲述各种与 EBCDIC 有关的笑话。有一个经典的笑话说的就是,美国政府跑去 IBM ,想要研发一种数据加密标准,于是 EBCDIC 编码就诞生了。经典游戏 Zork 中, EBCDIC 也被用来形容艰涩难懂的文字:

一个大房间里,各式各样笨重的机器在呼呼作响,电阻烧焦了的味儿扑鼻而来。其中一面墙上有三个按钮,形状分别是圆形、三角形和正方形。自然,这些按钮上方的说明文字都是用 EBCDIC 书写的……

Read more…

WOM 编码与一次写入型存储器的重复使用

计算机历史上,很多存储器的写入操作都是一次性的。 Wikipedia 的 write once read many 词条里提到了两个最经典的例子,一个是大家熟悉的 CD-R 和 DVD-R ,另一个则是更早的打孔卡片和打孔纸带。在介绍后者时,文章里说:“虽然第一次打孔之后,没有孔的区域还能继续打孔,但这么做几乎没有任何实际用处。”因此,打孔卡片和打孔纸带通常也被看成是只能写入一次的存储设备。

事实上真的是这样吗? 1982 年, Ronald Rivest 和 Adi Shamir 发表了一篇题为《怎样重复使用一次写入型存储器》(How to Reuse a “Write-Once” Memory)的论文,提出了一个很有意思的想法。大家有觉得 Ronald Rivest 和 Adi Shamir 这两个人名都很眼熟吗?没错,这两个人之前曾经和 Leonard Adleman 一道,共同建立了 RSA 公钥加密系统。其中, Ronald Rivest 就是 RSA 中的那个 R , Adi Shamir 就是 RSA 中的那个 S 。

在这篇论文的开头, Ronald Rivest 和 Adi Shamir 举了一个非常简单的例子。假设初始时存储器里的所有 bit 全是 0 。存储器的写入操作是单向的,它只能把 0 变成 1 ,却不能把 1 变成 0 。我们可以把存储器里的每 3 个 bit 分为一组,每一组都只表达 2 个 bit 的值,其中 000 和 111 都表示 00 , 100 和 011 都表示 01 , 010 和 101 都表示 10 , 001 和 110 都表示 11 。好了,假设某一天,你想用这 3 个 bit 表示出 01 ,你就可以把这 3 个 bit 从 000 改为 100 ;假设过了几天,你想再用这 3 个 bit 表示出 10 ,你就可以把这 3 个 bit 从 100 改为 101 。事实上,容易验证,对于 {00, 01, 10, 11} 中的任意两个不同的元素 a 、 b ,我们都能找到两个 3 位 01 串,使得前者表示的是 a ,后者表示的是 b ,并且前者能仅仅通过变 0 为 1 而得到后者。因此,每组里的 bit 都能使用两遍,整个存储器也就具备了“写完还能再改一次”的功能。

不可思议的是,两次表达出 {00, 01, 10, 11} 中的元素,其信息量足足有 4 个 bit ,这却只用 3 个 bit 的空间就解决了。这乍看上去似乎有些矛盾,但仔细一想你就会发现,这并没有什么问题。在写第二遍数据的时候,我们会把第一遍数据抹掉,因此总的信息量不能按照 4 个 bit 来算。利用这种技术,我们便能在 300KB 的一次写入型存储器里写入 200 KB 的内容,再把这 200KB 的内容改写成另外 200KB 的内容。这听上去似乎是神乎其神的“黑科技”,然而原理却异常简单。

Read more…

趣题:用两枚硬币随机生成 1 到 n 之间的整数

为了随机地并且概率均等地生成一个 1 到 6 之间的整数,通常的做法就是抛掷一个正方体的骰子。不过,这并不是唯一的办法。如果你有一枚公正的、正反概率相同的硬币,以及一枚不公正的、正反概率之比为 1 : 2 的硬币,那么你也能概率均等地生成一个 1 到 6 之间的整数。首先抛掷那枚不公正的硬币,那么结果有 1/3 的概率是正面朝上,有 2/3 的概率是反面朝上。如果出现了正面朝上的情况,那么令 i = 1 ;如果出现了反面朝上的情况,那么就再抛掷那枚公正的硬币,掷出正面则令 i = 2 ,掷出反面则令 i = 3 。最后,再抛掷一次公正的硬币,如果正面朝上则令 j = 0 ,如果反面朝上则令 j = 3 。容易看出, i + j 的值有 1, 2, 3, 4, 5, 6 这六种可能,它们出现的概率是均等的,都是 1/6 。

有人或许会说,用硬币模拟骰子哪有那么复杂,只用一枚公正的硬币就能办到:连续抛掷三次硬币,并且规定掷出“正正正”代表数字 1 ,掷出“正正反”代表数字 2 ,“正反正”为 3 ,“正反反”为 4 ,“反正正”为 5 ,“反正反”为 6 ,掷出“反反正”和“反反反”则重来,这不就行了吗?不过,这种方法有一个局限性:它不能保证整个过程在有限步之内完成。而我们刚才的方法中,总的步骤数有一个上限:三步之内必然完成。

我们的问题是:是否对于所有的正整数 n ,都能找到两枚合适的硬币,使得借助它们便能在有限步之内概率均等地产生一个 1 到 n 之间的整数?

Read more…

趣题:竞技场里的狮子能否保证抓住最高速度相同的小明?

小明和狮子同被关在一个半径为 10 米的竞技场里,狮子位于竞技场的圆心处,小明则在距离圆心 1 米的地方。两者的最大运动速度都是每秒 1 米。狮子有没有什么必胜策略,使得不管小明怎么跑,它总能在有限的时间里抓住小明?

根据 MathWorld 相关词条的描述,这个问题是由 R. Rado 在 1925 年时提出的。一个经典的“答案”是,狮子只需要始终保持自己与小明在圆盘的同一半径上即可。直觉上看,由于狮子总是处在“内圈”上,因而不管小明跑到了哪里,狮子总能轻松地与小明继续保持在同一半径上;并且,狮子总有足够的余力向小明靠近,严格减小它与小明之间的距离,除非小明是沿着半径方向径直向外跑。由于竞技场的大小是有限的,小明不可能无限地向外跑,因而狮子最终总会追上小明。但是,后来人们发现,这个解法其实是错误的,原因很简单:能不断靠近小明,不一定就能在有限的时间里抓住小明,正如 1/2 + 1/4 + 1/8 + 1/16 + … 永远不会超过 1 一样。最终, A. S. Besicovitch 为小明构造出了一个极其巧妙的策略,使得狮子无论如何都抓不到小明,从而完美地解决了这个问题。不过, MathWorld 的词条里并没有提到这个解法。你能想到这个解法吗?

Read more…

Penney 的游戏:正所谓后发制人,先发制于人

让我们来玩一个游戏。连续抛掷硬币,直到最近三次硬币抛掷结果是“正反反”或者“反反正”。如果是前者,那么我获胜,你需要给我 1 元钱;如果是后者,那么你获胜,我会给你 1 元钱。你愿意跟我玩这样的游戏吗?换句话说,这个游戏是公平的吗?

乍看上去,你似乎没有什么不同意这种玩法的理由,毕竟“正反反”和“反反正”的概率是均等的。连续抛掷三次硬币可以产生 8 种不同的结果,上述两种各占其中的 1/8 。况且,序列“正反反”和“反反正”看上去又是如此对称,获胜概率怎么看怎么一样。

实际情况究竟如何呢?实际情况是,这个游戏并不是公平的——我的获胜概率是你的 3 倍!虽然“正反反”和“反反正”在一串随机硬币正反序列中出现的频率理论上是相同的,但别忘了这两个序列之间有一个竞争的关系,它们要比赛看谁先出现。一旦抛掷硬币产生出了其中一种序列,游戏即宣告结束。这样一来,你就会处于一个非常窘迫的位置:不管什么时候,只要掷出了一个正面,如果你还没赢的话,你就赢不了了——在出现“反反正”之前,我的“正反反”必然会先出现。

事实上,整个游戏的前两次硬币抛掷结果就已经决定了两人最终的命运。只要前两次抛掷结果是“正正”、“正反”、“反正”中的一个,我都必胜无疑,你完全没有翻身的机会;只有前两次掷出的是“反反”的结果,你才会赢得游戏的胜利。因此,我们两人的获胜概率是 3:1 ,我的优势绝不止是一点。

你或许想问,如果已知我的硬币序列是“正反反”,那么你应该选择一个怎样的硬币序列,就能保证获胜概率超过我呢?研究表明,你可以选择“正正反”,这样一来,我们两人的获胜概率将会变为 1:2 ,换句话说你将会有 2/3 的概率获胜。 Using your Head is Permitted 趣题站 2014 年 5 月的趣题对此进行了更深一步的探究。

A 、 B 两人打算玩这么一个游戏。首先, A 选择一个长度为 n 的正反序列,然后 B 再选择另一个长度为 n 的正反序列。之后,不断抛掷硬币,哪名玩家所选的正反序列最先出现,哪名玩家就获胜。我们的问题是,假如两名玩家都采取最优策略的话,对于哪些 n ,游戏对玩家 A 更有利一些(换句话说,玩家 A 拥有超过 50% 的胜率),对于哪些 n ,游戏对玩家 B 更有利一些(换句话说,玩家 B 拥有超过 50% 的胜率)。今后,为了方便起见,我们用数字 1 代表“正面”,用数字 0 代表“反面”。

Read more…