IBM Ponder This #155 · 2011 年 3 月

飞船有 100,000 个存储位，已知恰好一个故障。检测程序可以检查任意子集，若其中全好则返回 OK，若遇到故障位就永久失效。一次检查无论子集大小都耗时一小时，任意多个程序可同时运行，也可同时访问同一存储位。必须在两小时内确定故障位。

A. 最少需要预先携带多少个检测程序？附加问：推广为 n 个存储位、t 小时，给出所需程序数公式。

B. 如果还要求第一次任务后剩余未失效的程序，足以把同样的定位任务再完整执行一次，预先要携带多少个？

另一附加问：在 A 中，把存储位数增加最多 X 个仍不需要增加程序数。求 X，并说明它与当时 IBM 历史上的一件近期事件有什么联系。

解答

认真尝试后再打开

待补充。