现在的位置: 首页 > 综合 > 正文

趣题:由0和1构成的虫子

2013年08月11日 ⁄ 综合 ⁄ 共 1847字 ⁄ 字号 评论关闭

问题摘自:http://www.cs.cmu.edu/puzzle/puzzle37.html

A long worm crawls into a cosmetic veterinary surgery, complaining of a problem with 1's. 
A worm can be thought of as a string of 0's and 1's and the most beautiful worm is 00000 ... 0. The worm is a sequence of segments and there is a 0 or a 1 on each segment. The procedure for removing 1's is complicated. If there is a 1 at the right hand end (where the tail is), then the surgeon can remove this 1 (and the segment it lies on) and place a new segment with 0 or a 1 at the left hand end (where the head is).
If however there is a 0 at the right hand end then the surgeon can remove it, but he has no control over what appears on the new segment at the left hand end. Indeed, the surgeon has to operate under the assumption that there is an adversary making a choice of what to replace a 0 by.
The adversary would like the operation to continue indefinitely. The surgeon claims a 100% success rate. Do you believe him?

有一条虫子,它的整个身体由 n 节构成,每一节要么是有瑕疵的 1 ,要么是没有瑕疵的 0 ,因而整个虫子的身体结构就可以用一个 n 位 01 串来表示。你的目标是把整个虫子变成 000...00 的完美形式。每一次,你可以砍掉虫子最右侧的一节,同时虫子会在最左侧长出新的一节,以保持虫子的总长度不变。如果你砍掉的是一个 1 ,那么你可以指定虫子在最左侧长出的是 1 还是 0 ;但如果你砍掉的是一个 0 ,那么你无法控制虫子会在最左侧长出什么——它可能会长出 0 ,也可能会长出 1 ,因而你不得不假定,概率总是会和你做对,上天会竭尽全力地阻挠你。我们的问题是:不管虫子的初始状态是什么,你总能保证在有限步之内让虫子变成 000...00 吗?
注意,这个问题可能没有你想的那么简单。显然,我们必须得把一些 1 变成 0 ,这样才能让 1 的数目逐渐减少并最终消失。但是,如果只是简单地每次都把 1 变成 0 ,最终也不见得就一定能取胜。比如,如果这条虫子是 101 ,那么去掉最右边的 1 并选择在左边长出一个 0 ,虫子会变成 010 ;再把 010 右边的 0 去掉后,如果不巧左边长出的是 1 ,那么整条虫子又会回到 101 的状态。如此反复,将永远也不能得到 000 。而更加聪明的方法则是先把 101 变成 110 ,下一步虫子将会变成 111 或者 011 ,不管是哪种情况,接下来只需要逐个把 1 变成 0 就能获胜了。运用恰当的策略才能走到终点,这无疑让问题变得更加有趣。
不管虫子一开始是什么样子的,我们总能够在有限步之内获胜。下面是 Peter Winkler 给出的证明。让我们把连续 n 次操作视为一轮操作,因而完成一轮操作正好让虫子的整个身体更新一次。于是,每一轮操作实际上相当于是从右到左依次考虑虫子的每一位,每遇到一个 1 时你都可以选择是否把它修改成 0 ,每遇到一个 0 时它都会随机地被修改成 1 。我们一轮一轮地改造虫子的身体,并且每一轮都采取这样的策略:从最右端开始,每次遇到 1 都把它改成 0 ,直到第一次有 0 被改成 1 ;在此之后,不管新遇到的 0 变没变,都保留所有的 1 不变。如果这一轮下来后,没有 0 被改成 1 ,那么我们将会把所有的 1 都替换成 0 ,从而得到 000...00 的形式,直接获得胜利;如果途中有 0 被改成了 1 ,那么整个虫子作为一个二进制数将会严格增加。每经过一轮后,只要虫子没有变成 000...00 ,整个二进制数都会变得更大,最终将会变成 111...11 的形式,此时再也不会有 0 变成 1 了,于是按照我们的策略,在下一轮中,所有的 1 都会变成 0 ,从而获得胜利。

解题思路摘自:http://www.matrix67.com/blog/archives/5063

抱歉!评论已关闭.