Dec 28th 2012 趣题巧解 @童年崩坏FML.pdf

Dec. 28th 2012 趣题及详解 （更新于Dec. 29th ） by @童年崩坏FML 原题： 今天的趣题来自我不日前阅读‘Concrete Mathematics ’ 的一道练习。出题者并非此书作者—— 既大名鼎鼎的图灵奖 得主Don. Knuth—— 而是公元一世纪的异见历史学家Flavius Josephus. 相传在某一次地下会议中，Josephus 与其它40 名犹太异 见人士被罗马军队困于一个山洞。被罗马军方抓住也逃不过 被处死的命运，所以他们商量了一种集体自杀的办法。学历 史的Josephus 不吃这一套，他深谙苟活于世的道理，但迫于 压力不得不从。这41 个人围成了一个圈，从某一个人开始， 顺时针，每隔一个人，处死一个人。处死的人被拖出圈，周 而往复，直到最后只剩下一个人，此人自杀。 举个例子，比如只有10 个人，编号1~10,顺时针站立成 圈.从1 号开始数，处决顺序便是2,4,6,8,10,3,7,1,9. 最后剩下的 人是5 号。 那么，很明显，想明哲保身主人公Josephus 就要迅速计 算出在41 个人中站在哪个地方才是最后剩下的那个人，现在 他正焦急的思考，你能帮助他么？ 对，没错，这是一道数数的题，首杀只需要拿笔拿纸快 速数数。 不过瘾？ Bonus problem: 如果是200 个人呢，你站在哪里？如果 是N 个人呢。是否存在一种封闭形式来快速计算呢？如果每 隔k 个人处死而不是1 个呢？ 解答 ： 为了方便后面的探讨，我们姑且将在总共 N 个人的情况下 最后一个逃生者的编号记为 J(N)吧。比如，10 个人围圈后，处 死顺序按照规则依次为：2 、4 、6、8、10、3、7、1、9 ，最后活 下来的人是5 号，那就记做J(10)=5.联想到J(2)=1 ，猜测当N 为 偶数时，J(N)=N/2. 但第一次检验就失败了，当N=4 时，处死顺 序为2 、4 、3 ，可见J(4)=1,我们的第一感觉并不准确。 实际上，根据规则列出N 较小时J(N) 的值很容易，如下 N 1 2 3 4 5 6 J(N) 1 1 3 1 3 5 我们发现，J(N) 并非关于N 的单调递增数列—— 总人数越多 并不代表存活者的序号越大，并不能简单猜测J(N) 可表达为某个 关于N 的多项式，只能另寻办法。 思考原题目，每隔一人处死一人，且被处死的人都会被拖出， 我们下意识的觉得，在处死一轮之后，总人数大概剩下了原人数 N 的一半。且在总人数为偶数的时候，处死一圈后总人数精确等 于N/2 。让我们作图来看看到底发生了什么。 当N 为偶数时，设N=2n ，处死前后有： 1 1 2n 2 2n-1 3 2n-1 3 2n-3 5 4 7 …… …… 完成一轮处死之后，右图还剩下n 个人。不难想到，右图最 后存活的人的标号一定与初始问题等价，毕竟不可能处决一圈之 后，原先存活者的标号变了。重新编号，设a(1)=1 ；a(2)=3 ；…； a(n)=2n-1。得到新图： 1 a(1) 2n 2 a(n)