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…

IMO2015 趣题:平衡的但无中心的点集

2015 年 IMO 的第 1 题很有意思。假设 S 是平面上的某个点集。如果对于 S 中的任意两点 A 、 B ,我们都能在 S 中找到一个点 C 满足 AC = BC ,我们就说这个点集 S 是平衡的。如果对于 S 中的任意三点 A 、 B 、 C ,我们都无法在 S 中找到一个点 P 满足 PA = PB = PC ,我们就说这个点集 S 是无中心的。这道题有两个小问。

  1. 证明:对于所有大于等于 3 的正整数 n ,都存在一个由 n 个点构成的平衡点集。
  2. 对于哪些大于等于 3 的正整数 n ,存在由 n 个点构成的平衡的但无中心的点集?

Read more…

趣题:正方形能被画成什么样?

房间的正中间悬浮着一个正方形的金属框。五位画家看到这般奇迹后,立即拿出纸和笔,把这个金属框的样子画了下来。但是,由于五位画家观察这个金属框的角度不同,它们画出来的结果也互不相同。请问,这五位画家画出来的结果都是对的吗?换句话说,有没有哪一幅图或者哪几幅图根本不可能是一个正方形的透视图?

Read more…

Sierpiński 的初等数论问题

波兰数学家 Wacław Sierpiński 对数论有很多研究。在他一生出版的 50 多本书里, 250 Problems of Elementary Number Theory 一书显得格外有趣。这里面不但有各种出人意料的数学事实,还有很多精妙的证明和大胆的构造,让人大呼过瘾。我从中选择了一些问题,在这里和大家一块儿分享。下面的文字没有完全照搬书中的内容,而是做了大量的改动和扩展;若有出错的地方,还请大家指正。个别题目会涉及一些初等数论中的著名定理,它们都可以在这篇文章里找到。

Read more…

趣题:不等式背后的直观意义

有时,为了说明某个式子始终成立,我们会为它构造一个情境。例如,为了说明

C(m, 0) · C(w, r) + C(m, 1) · C(w, r – 1) + … + C(m, r) · C(w, 0) = C(m + w, r)

始终成立,只需要注意到,等号的左边和右边计算的都是同一个东西:假如一个班上有 m 个男生 w 个女生,从中选出 r 个人有多少种方案。等号左边的计算方式是,分别计算 0 男 r 女、 1 男 r – 1 女、 2 男 r – 2 女等 r + 1 种情况的方案数,然后把它们加起来。等号右边则是直接算出了从这 m + w 个人中选出 r 个人的方案数。两种算法所得的答案应该是相等的。

现在,请你构造一个情境,来说明不等式

(1 – pm)n + (1 – qn)m ≥ 1

总成立,其中 m 、 n 是任意正整数, p 、 q 是任意正实数,并且满足 p + q ≤ 1 。

Read more…