点燃绳子究竟还能测出哪些时间?

    有一根不均匀的绳子,烧完正好需要 1 个小时。如何用这根绳子测出半个小时的时间呢?答案很巧妙:把这根绳子的两头同时点燃,绳子烧完时正好就过了半个小时。更妙的是下面这个加强版:如何用两根这样的绳子来计时 45 分钟?答案是,把其中一根绳子的两头都点燃,同时点燃另一根绳子的其中一头;待到前一根绳子烧完之后,再把第二根绳子的另一头也点燃,于是便能测出 30 + 15 = 45 分钟了。
    一个有趣的问题自然而然地产生了:假如这样的绳子足够多,哪些时间能够用烧绳子的方法测出来呢?

    为了解决这一问题,让我们先把这个问题本身理清楚——“烧绳子测量时间”的“游戏规则”究竟是什么?首先,一根绳子(的任意一头)可以在第 0 时刻或者另外某根绳子烧完的瞬间点燃。另外我们假设,在同一时刻,我们可以同时点燃任意多根绳子。而由此测出的时间段则定义为从点燃第一根绳子到最后一根绳子烧完的总时间。
    用形式化的语言来描述,如果绳子两端分别在第 a 时刻和第 b 时刻点燃(其中 |a – b| < 1 ),那么绳子最终将在 (a + b + 1)/2 时刻烧尽。我们说某个时间点 x 是可以到达的,当且仅当存在两个可以到达的时间 a 、 b ,使得 x = (a + b + 1)/2 。显然,第 0 时刻是可以到达的。从第 0 时刻出发,不断用 (a + b + 1)/2 进行迭代,我们就能得到所有能够测出的时间了。   

     可以看到,随着迭代次数的增加,能够测量的时间越来越多,也越来越精确;不过,时间一去不复返,有些时间还是无法测量,绳子再多也没法弥补。

Read more…

神秘常量复出!用0x077CB531计算末尾0的个数

    大家或许还记得 Quake III 里面的一段有如天书般的代码,其中用到的神秘常量 0x5F3759DF 究竟是怎么一回事,着实让不少人伤透了脑筋。今天,我见到了一段同样诡异的代码。
    下面这个位运算小技巧可以迅速给出一个数的二进制表达中末尾有多少个 0 。比如, 123 456 的二进制表达是 1 11100010 01000000 ,因此这个程序给出的结果就是 6 。

unsigned int v;  // find the number of trailing zeros in 32-bit v
int r;           // result goes here
static const int MultiplyDeBruijnBitPosition[32] =
{
  0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
  31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
r = MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x077CB531U)) >> 27];

    熟悉位运算的朋友们可以认出, v & -v 的作用就是取出右起连续的 0 以及首次出现的 1 。当 v = 123 456 时, v & -v 就等于 64 ,即二进制的 1000000 。怪就怪在,这个 0x077CB531 是怎么回事?数组 MultiplyDeBruijnBitPosition 又是什么玩意儿呢?

Read more…

公平分割问题:均衡分割与免嫉妒分割

    大家或许都知道经典的两人分饼问题——为了实现公平性,只需要一个人切,另一个人选即可。不过,在现实生活中,情况远没有那么理想。如果把大饼换成蛋糕,问题就复杂了很多——你想吃奶油,我想吃巧克力,他想吃水果⋯⋯如果分蛋糕的人对蛋糕各部分的价值看法有分歧,还能实现公平的分割吗?如果分蛋糕的人不止两个呢?

    事实上,对于两个人分蛋糕的情况,经典的“你来分我来选”的方法仍然是非常有效的,即使双方对蛋糕价值的计算方法不一致也没关系。首先,由其中一人执刀,把蛋糕切分成两块;然后,另一个人选出他自己更想要的那块,剩下的那块就留给第一个人。由于分蛋糕的人事先不知道选蛋糕的人会选择哪一块,为了保证自己的利益,他必须(按照自己的标准)把蛋糕分成均等的两块。这样,不管对方选择了哪一块,他都能保证自己总可以得到蛋糕总价值的 1/2 。
    不过,细究起来,这种方法也不是完全公平的。对于分蛋糕的人来说,两块蛋糕的价值均等,但对于选蛋糕的人来说,两块蛋糕的价值差异可能很大。因此,选蛋糕的人往往能获得大于 1/2 的价值。一个简单的例子就是,蛋糕表面是一半草莓一半巧克力的。分蛋糕的人只对蛋糕体积感兴趣,于是把草莓的部分分成一块,把巧克力的部分分成一块;但他不知道,选蛋糕的人更偏爱巧克力一些。因此,选蛋糕的人可以得到的价值超过蛋糕总价值的一半,而分蛋糕的人只能恰好获得一半的价值。而事实上,更公平一些的做法是,前一个人得到所有草莓部分和一小块巧克力部分,后面那个人则分得剩下的巧克力部分。这样便能确保两个人都可以得到一半多一点的价值。
    但是,要想实现上面所说的理想分割,双方需要完全公开自己的信息,并且要能够充分信任对方。然而,在现实生活中,这是很难做到的。考虑到分蛋糕的双方尔虞我诈的可能性,实现绝对公平几乎是不可能完成的任务。因此,我们只能退而求其次,给“公平”下一个大家普遍能接受的定义。在公平分割 (fair division) 问题中,有一个最为根本的公平原则叫做“均衡分割” (proportional division) 。它的意思就是, 如果有 n 个人分蛋糕,则每个人都认为自己得到了整个蛋糕至少 1/n 的价值 。从这个角度来说,“你来分我来选”的方案是公平的——在信息不对称的场合中,获得总价值的一半已经是很让人满意的结果了。

Read more…

《新知客》趣题专栏 2010.11

目前,我正在《新知客》杂志上主持一个趣题栏目。每月杂志发行后,我将在 Blog 上同步更新。点击 这里 可以查看往期题目。

推理
1. 高三 (17) 班有 50 个同学,他们的学号分别是 1, 2, 3, …, 50 。一次数学考试结束后,同学们都交完试卷离开了考场。数学老师小 A 清点试卷时发现,他手中只有 49 张卷子。究竟是谁没有交卷呢?正巧小 A 手边没有笔,他也不想把所有卷子按照学号重新排序。他希望不借助任何工具,仅仅通过依次查看每张卷子上写的学号,便能找出缺失的那个学号。和常人一样,小 A 的记忆力很有限,他没法记住之前到底看到过哪些学号;不过,作为一个数学老师,小 A 拥有无人匹敌的计算能力。他有办法找出没交卷的那位同学的学号吗?

2. 小 A 和小 B 玩游戏。从小 A 开始,两个人轮流从 1 到 9 当中选一个数(已经选过的数不能再选),约定谁先选到三个和为 15 的数,谁就获胜了。比方说,小 A 先选了 4 ,然后小 B 选 5 ,小 A 选 6 ,小 B 选 2 。为了阻止小 B 获胜,下一步小 A 就必须得选 8 (否则小 B 将靠 5 、 2 、 8 三个数获胜)。为了阻止小 A 获胜,小 B 选择了 1 (否则小 A 将靠 6 、 8 、 1 三个数获胜)。但是,这已经阻止不了小 A 的胜利了——小 A 可以选择 3 ,从而得到 4 、 8 、 3 三个加起来等于 15 的数。
在这个游戏中,小 A 有必胜策略吗?

Read more…

UyHiP趣题:100囚犯之黑白手套

    上个月的 UyHiP 趣题非常妙,个人认为是近几个月里最漂亮的一道谜题了。
    典狱长要和 100 个囚犯玩这么一个游戏。典狱长给每个囚犯发两个手套,一个黑色的,一个白色的。之后,每个囚犯的额头上都会写上一个实数,所有这 100 个实数互不相同。每个囚犯都能看到其他 99 个囚犯前额上所写的数,但不能看到自己的数。接下来,每个囚犯必须独立地决定把哪个手套戴在哪只手上。等到所有囚犯都戴好了手套,典狱长会把他们按照前额上所写的数从小到大地排好,并要求他们手牵着手站成一横排。如果每两只握在一起的手都戴着相同颜色的手套,那么所有 100 个囚犯都可以被释放。
    在游戏开始前,他们可以聚在一起,商量一个对策。游戏开始后,囚犯与囚犯之间不允许有任何交流。囚犯们能够保证全部释放吗?

Read more…