高老头的厕纸问题

March 20, 2008 1:23 pm UTC | In Life, Study

2-roll-holder.jpgKnuth 在 1984 年发过一片研究厕纸问题的论文(The Toilet Paper Problem,后收入 Selected Papers on the Analysis of Algorithms)。在很多卫生间都可以看到如右图所示的双卷卫生纸架,以防一卷用完时出现尴尬情景。Knuth 研究的问题就是一卷用完时另一卷平均还剩几张的问题。他论文里写道:世界上有两种人,喜欢从大卷里用纸的和喜欢从小卷里用纸的;但是无论是谁,如果碰到两卷都用完了,那就有麻烦了!(很多人都说 Knuth 是因为自己碰到过这个事情所以才写了这篇文章)。Knuth 在 Mathematical Writing 第 31 页 15. Excerpts from class, October 30 提到发表这个论文时遇到的麻烦。杂志编辑对这个图灵奖得主的论文评价是“在我们杂志上讲笑话是危险的!”。Knuth 最后同意修改有粪便学双关含义的论文章节标题,但是论文题目死活不肯改了,因为 Knuth 号称已经用这个题目做过两次演讲。最后编辑只好说:Your toilet paper is accepted!

toilet.png

Knuth 推导出的结果如上图所示(憎恨数学者请跳过此段) 。n 是厕纸初始张数(张的含义是单个人 D.B. 后使用的厕纸数量),p 是大卷厕纸爱好者的比例,Mn(p) 为一卷用完时另一卷剩余的张数。结果很符合逻辑:如果 p 很小,大部分人都用小卷厕纸,最后剩下的一卷肯定很大;而大卷厕纸爱好者一旦占优(p > 50%),则最后很有可能出现两卷厕纸差不多一起用完的情形(Mn(p) 极小)。一个细节问题是这篇论文里面的 Catalan 数定义略有不同,论文里的 Ci 是通常定义下的 Ci-1

Knuth 推导出公式之后感叹:When a formula turns out to be so simple, it must have a simple explanation. But the author hasn’t been able to think of any direct proof.(统计学里常见,很多时候确实可以找到简单方法)Knuth 一直很追求简单性,写 TAOCP 里很多算法都要斟酌词汇找到最有效的表达方法,不过在厕纸问题上却碰了个钉子,于是直接把郁闷的心情写进了论文。Knuth 在厕纸问题论文最后感谢:I wish to thank the architect of the computer science building at Stanford University for implicitly suggesting the problem… 大牛是不是都喜欢搞笑,想起诺贝尔物理学奖得主 Ramsey 大师在巨著 Molecular Beams 的参考书目里有一条是这样的:RAM50e N. F. Ramsey, private communications and lectures (1950)。囧,private communication 一般表示和别的大牛私人通信,他居然自己和自己私人通信……

Knuth 更多八卦可以看收入水木精华区的 helloooo 的文章。Knuth 中文名字是高德纳,我们一般叫他高老头,高老头非常可爱,几个月会出来讲个学(Computer Musings视频)。

f-functionopaperholder-cmprsd.jpgforced-2-roll-holder.jpg

上面这俩是啥?是新的厕纸设备,只有使用完第一卷时才能使用第二卷(图片来源)。这么看来,Knuth 那篇论文完全是在自娱自乐,有统计学上的价值却不能解决实际问题。现在新厕所都用上面这类新装置了,(啊,我终于回到我写这篇文章的起因了)不过上个月我上厕所,发现两卷居然都被人用光了!看来这种新装置也不靠铺。当时我身上一没手机二没女朋友照片三没人民币,连选择的条件都没有,只好等有老大爷进来求他给我送点纸。更奇怪的是,过去了两天居然还没有人装上新厕纸,资本主义的效率是不是就是这么低啊?看来我碰到的恐怕不是什么小概率事件,而是清洁工罢工了……

说到资本主义的低效率,我住的公寓楼地下室的垃圾箱要维护,这一维护,居然就维护了三个多月,搞得垃圾通道完全停用,门口的临时垃圾箱一到周末就会满出来。据说他们把垃圾箱拆开了才发现少零件……零件来了每天叮叮咚咚敲一会儿就收工了,晕啊,修个垃圾桶就能修三个月,这就是资本主义!

这篇文章思维好跳跃,我最近逻辑有点乱……

Tags: , ,

12 Comments »

RSS feed for comments on this post.

  1. 我强烈相信高老头是因为自己遇到了这样的问题才写的那篇东东,另外,离开学校有些日子了,不知道他现在是不是还会像以前一样在临近感恩节圣诞节的时候在系里露个脸,讲些有趣的小段子。又及,我曾经和zt无聊研究过高老头的录像(一年一年的翻。。。)后来发现他好像并不是慢慢有了大师的气质的,而是在某一年之后(好像是86年)突然有了变化。。。。不知道是不是当时发生了些什么。。。。。anyway,无论如何高纳德同志应该是迄今为止在获奖时最年轻的图灵奖得主了吧?拜 A core~~~

    Comment by aozukina — March 20, 2008 2:08 pm UTC #

  2. 拜 A core,另外高德纳老爷子近期还会在这边出现吗?

    Comment by Xin LI — March 20, 2008 4:28 pm UTC #

  3. 拜aa。。。
    “后来发现他好像并不是慢慢有了大师的气质的,而是在某一年之后(好像是86年)突然有了变化。。。。”

    拜大师。
    这个Mn(p)-p的chart非常好,非常好,很让人欣赏+喜欢。

    能欣赏这个问题及其推导+结论以及外界反应前因后果的人,都不同凡响。。。

    鼓巴巴掌。

    Comment by nailear — March 20, 2008 5:17 pm UTC #

  4. 又见多项式

    Comment by hayate — March 20, 2008 6:36 pm UTC #

  5. Xin LI 同学:关注 Computer Musings 即可,目前写着:The next talk in the series will be announced in 2008.

    Comment by atppp — March 20, 2008 7:52 pm UTC #

  6. 您没有人民币,但是您有美元可以用来解决问题!

    Comment by kxn — March 21, 2008 7:56 am UTC #

  7. 拜康神!~~ nailear同学难道是果子的化身?

    Comment by aozukina — March 21, 2008 9:11 am UTC #

  8. 幽默感跟智商成正比,例子:
    老高,
    费曼,
    爱因斯坦。
    等等

    Comment by hacker47 — March 22, 2008 5:47 am UTC #

  9. 感觉这样的问题用心理学来研究比较好。
    用数学?

    Comment by hacker47 — March 22, 2008 5:55 am UTC #

  10. 您老人家的blog不在msn里面闪小星星,所以总要想起来才能过来看一眼,不过每看一次收获都颇丰阿。。。看来得加bookmark了。JK罗琳的七本书啊!
    btw, 不会用google reade,好用否?

    Comment by tension — March 24, 2008 11:48 pm UTC #

  11. 难道用女朋友的照片擦pp吗:)

    Comment by cat — March 25, 2008 8:48 am UTC #

  12. 很明显,这个问题在中国也不成问题。中国厕所要么不提供厕纸,如果提供,那也是卖的。

    Comment by StarKnight — March 25, 2008 6:43 pm UTC #

Leave a comment

XHTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

This weblog is licensed under a Creative Commons License.
Powered by WordPress. Theme based on Pool by Borja Fernandez.