有一条虫子，它的整个身体由 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 ，从而获得胜利。
沙发么？？还久没见更新了
还是用笨方法啊 先变成可控的1 然后再全转成0.
“如果途中有 0 被改成了 1 ，那么整个虫子作为一个二进制数将会严格增加”
–数学没学好不明白 如果运气特别差的话 这个还是有限步吗?
中间好大的空行是怎么回事？不过很多全局最优的问题来说，适当松弛有助于得到最优解啊，局部贪心往往悲剧。。
– -可怜的虫虫。
同意板凳，假如第一次有0被改成1之后，后面随机永远是0怎么办。既然是随机的，无法证明一定会有机会出现1啊。。。
一定可以在有限步内实现
不一定是最优解
板凳说的有道理。
“如果途中有 0 被改成了 1 ，那么整个虫子作为一个二进制数将会严格增加。每经过一轮后，只要虫子没有变成 000…00 ，整个二进制数都会变得更大，最终将会变成 111…11 的形式”
文中这句分析是有问题的。遇到 0 的时候引入的随机性不能被排除掉，考虑到“因而你不得不假定，概率总是会和你做对，上天会竭尽全力地阻挠你”这句，有可能每次砍掉 0 ，都长出 0 。这样，每循环过了一轮以后，发现永远都是和上一轮完全相同的数字。
@地壳，@板凳
如果每次砍掉0都长出0，那么就会直接得到最终目标全0的完美虫。
讚一下~「嚴格增加」這一點很讚~
标记一下，稍后分析这道题目。
– –
把第一个0改成1时，已经使数字有所增加；
此后遇到0，不论长出0或1，都不使数字减小；
遇到可控的1，令其长出1，维持数字不变。
如果一条虫子里有n-1个1和1个0，每次砍掉1换成1的时候0都变成0；要砍掉1换成0的时候这个0就变成1。那也没法保证在有限步里啊
这就好比俄罗斯方块也存在必死的序列
不对…我说错了…
如果1…10变成了01…1，那只要把1都变成0就行了…
但是在这之前，一旦第一次0变成1之后，不能保证在有限次内出现下一次0变成1
方法很有意思 说不对的没看懂那段话
不知道是不是我的理解问题，见到1不该让它还是1，见到0会由于恶性的随机变为1，那么在n的复杂度（也就是n步后），整个虫子都会变成全1的，在下一个n的时间就可以全部变为0，这个题目和解法到底想说明什么？
如果是足够聪明的随机的话，那么也很有可能再某一步再也无法转换下去，进入一个循环（也即没有恶性的随机让序列单调增加而是保持不变），所以我觉得题目的整体构造本身有问题，或者相应的下列解法也太不加思索了
了解了，不是单纯的变化随机，而是适当变化的随机，解法不错~~对自己鄙视下~~
希望题目本身可以对随机性进行一点点定义，不然这个题目本身还是有问题，虽然解法不至死~
所谓“随机出现0或1”，其实等价于在一个足够大的有限的次数里，必然会出现至少1次0，至少1次1。
题目中就不该说老天会作对⋯⋯纯概率的话那是可行的。。
看懂了方法，但是文中有几个词儿没有看懂。。只理解大概意思。
又看了一边，这个方法是对的，关键就在“那么整个虫子作为一个二进制数将会严格增加”
给你的英文翻译水平跪了
是不是可以从一开始就：遇到1，不变；遇到0，随机。这样不停地进行下去，所有的0总会慢慢地变成1，然后就都变1为0就可以了。
这样做有问题吗？没有的话好像比lz的更快？？
看到17楼好像和我想的一样
回26楼：
那是不可以的，因为如果单纯的遇到1不变，遇到0随机，那有可能n步操作下来，整个虫子没变，就不能保证在有限步中解决了。
文中的解法是正确的，因为保证了每n步下来要么全清0要么整条虫子作为二进制数严格增加，所以在n·2^n步内一定可以变成全是0的序列
说不对的没看懂那段话
很严谨啊 没问题
每次操作就两个事情 one：要么就没有 0 被改成 1 而1都改成0 那不就全0嘛 two： 要么就有0变成1了，而在此之后 其他1不变0 都变1.那么这个数肯定就变大了啊。
那就搞定了 不会有无限循环啊 解法不赌概率 就算老天作对也能完成 而且有限步 你给定序列之后 可以计算出至多多少步。
大家要仔细看 再回复 不然怎么对得起楼主。
确实是严格增加，即使上帝跟你作对
这巧妙的方法啊！！！！
又是游戏
膜拜。。
用数学归纳法倒是可以证明。
长度1的序列显然有有限解。
长度为n的序列如果都有有限解的话，长度为n+1的就可以认为是一个n序列右边置一个数。如果这个数是0，那么就砍掉，一直砍到是1为止。此时最右边是1，左边是一个n长度的序列，仍然有有限解，然后按照这个解法解出左边的n个序列，右边的1保持不变，直到某一时刻左边为全零序列（即已解出），右边的1变0即可。
真有意思，34楼大神啊，只不过这种递归的证明做解法的话太慢了，看来有解和解之间还是有差距的。
刚才读错题，看成从两个方向都可以砍= =
两个方向砍的方法：
如果序列一端都是0，一端都是1，那么我们可以把它变为全是0
整个序列都是1或都是0或一端都是0，另一端都是1，有解
否则
1.假如左端有一段连续的1，把它移到右端
2.左端第1个是0，砍
(1)右端出现1，砍右端，令左端出现1，砍左端，令右端出现0
(2)右端出现0
3.接下来一直从左端砍，如果遇到0，就按2；如果遇到1，令右端出现0
这样最后就会有0000000……
1.根据题目条件“概率总是会和你做对，上天会竭尽全力地阻挠你。”我认为无法让虫子变成000…00。
2.如果假设砍掉虫子最右侧的一节0，其在最左侧他出0或1的概率是相等的，那么将虫子变成000…00的策略如下：
首先，不管虫子一开始是什么样子(为了更直观讲述此策略，假设虫子初始状态为101011)，我们都将其最右端的1砍掉，同时让最左侧长出新的一节1，以下简称将1砍成1，此时虫子由101011变为111010。当碰到虫子最右端为0的时候，假设他在最左端长出1或0的的概率相等(i.e.都为0.5)。
我们分析第一种情况(以下称为情况a)，假设将最右端的0砍成了1，此时虫子由111010变为111101，继续沿袭上面策略将右端的1砍成1，虫子变为111110，此时，如果仍然出现情况a，将最右端的0砍成了1，那么整个虫子就变成111111，接下来只要将1全部砍成0即可。
然后分析第二种情况(以下称为情况b)，假设将最右端的0砍成了0，此时虫子由111010变为011101，根据策略将右端的1继续砍成1，虫子变为101110，如果出现情况a，则虫子变为110111，接下来，将右端的1全砍成1，虫子变为111110，如果继续出现情况a，则虫子将变成理想的111111；如果出现情况b,则虫子变为011111，我们再将右端的1全砍成1，将虫子变为111110，这时便出现了和前面重复的序列，因为我们假设将虫子最右端的0砍成0或1的概率是相同的，所以只要我们按照如上策略一直走下去，在有限步内总可以获得理想的虫子。
可以考虑一下最坏情况下需要几步。
最坏情况多少步需要怎么考虑？每轮让最左边的一个0变为1，其他的0都变为0，这样增加的最慢。我这样想对么？
最坏情况多少步这样考虑对么？每轮让最左边的一个0变为1，其他的0都变为0，这样增加的最慢。
最坏的情况是老天总是跟你作对，永远也不会成功，是这样么
34楼的归纳有一点问题，左边的n长度的序列，并不一定刚好在n的整数倍次操作后全部清零，也许最后形成了一个0.（n-x个0).010.(x个0).0的序列，那就不一定能把最后一个1变成0，同时保持其他0不变
直观上想最坏的情况是在本轮不会被变成0*的情况下，让二进制数尽量小？可能也不完全对，呵呵
原文：“如果这一轮下来后，没有 0 被改成 1 ，那么我们将会把所有的 1 都替换成 0 ”，这一轮下来后，没有 0 被改成 1，不代表下一轮将 1 都替换成 0 的时候没有 0 被改成 1
34楼的“一直砍到是1为止”是有问题的，不能保证能够在有限步砍到1……
感觉最坏情况就是每轮增长最慢的情况。即第一个0变1出现的尽可能早，而后的0都不变为1，这样让每轮增加就最慢了。
回复 34楼与46楼
关于“一直砍到是1为止”事实上你可以在左边没有变成0的时候 无视右边的那一个只要简单的砍去他就可以了，当左边都变成0时，右边的那一个是1 就继续原结尾操作，是0就无视
但 我认为存在另一个问题 对n+1的最后一步操作会改变原有顺序（将最后一个变成第一个） 使得对n+2的操作中当一开始的左边n个变成0时 一开始的最右边一个变成了作起第二位
你们砍死我吧，恶毒的人们
这blog观众的智商什么时候变这么低了。。。。
重点是每一轮都必须搞完n次,不是搞到一半就重头算.楼主还是描述的不清楚.哈哈.
以101为例,可能会出现下面的情况:
第一轮:010,101,110 每轮都必须搞满3次
第二轮:011,001,000
错误的想法源自你是这样理解的:
第一轮:010,101 没搞满
第二轮:010后面略
这个算法其实还是贪心,只不过比较鬼一点:要不你让我把这个全变成0,要么你就让2进制增大,都是有利于我的.只不过大多数人可能洞察不到,佩服!!!!
还是我,数学归纳法显然也是可以推的.先不说数学归纳法,楼主的算法就是把一个虫子变成1000…—>1100…—>1110…,总之就是左边全是1,右边全是0,1越来越多,最后变成全是1,搞定.
数学归纳法:假设n节虫子满足条件,则我们给这个虫子加一节变成n+1节,加在什么位置都无所谓,因为你可以把这个虫子想象成一个环.然后无视新加的这节,我们依然可以再有限的步骤内把其余的部分全变成0(因为每一轮我们只是多切了一刀而已),这时候我们回头想想最后一轮,顺手把新增的那节处理了不就妥了???
还以101为例子,数学归纳法:
处理n==1,我只管第一节,变成虫子变成001或者011
处理n==2,001的情况前两节都是0,顺手把新增的第三节也处理了,妥了;011的情况,只管前两节,中间的1变0,变成001了,还是妥了.
看不懂的自己慢慢理解理解,这个blog的人的智商的确是被我拖累坏了.
数学归纳的方法是对的，而且用数学归纳法提出来的步数上限远远低于原文中的方法
54楼,非也.直觉上是这样的,但你操作一下会发现其实殊途同归.另外我53楼101的例子说明不了什么问题
我想的方法是先随便运行一段使虫子最左端有1出现 这个1每次运行都坚定地继续执行为1 然后再证明这个1右方最近处的0最终总会变成1 然后成了1以后也永远坚定执行1 最终所有都是1或者连着的1右边都为0时 这些1执行为0 就好了 然后最后发现其实方法是和lz一样的 我的显得繁
方法对的至于最坏复杂度应该是≤O(2^n)
这个问题很有意思，仔细看看
仔细看看
数学归纳法其实最好理解了，只是好像前面说的都不全。。。我来试试看
1. 显然对于长度为0或者1都是有有限解的，我就省略了
2. 假设 H : 对于长度为n的虫子我们都是有有限解的
那么，长度为n+1的虫子即为一条n的虫子加上右边一个小尾巴。接下来分类讨论：
a. 小尾巴是1，那么情况很简单，砍成1那么每轮下来最右边的尾巴都是1，问题就变成只要左边那条n长度的虫子有有限解(由假设H可得)，左边全变0，最后把右边的1砍成0就行了
b.小尾巴是0，那么结果有两种，
第一种简单些因为变成1就会直接进入和a一样的情况
第二种仍然是0那么继续，如果变成1就会进入a，一直到左边都变成了0（因为也是长度n的虫子，根据假设有有限解）如果还没是0，这条虫子就完美了~
好了，我觉得这样的应该都能理解了。。。
那个神一般的随机难道是墨菲定律…
DP可解吧，他那个算法我感觉不一定能拿到最优解。步数上应该会超
这其实是一个博弈问题，可以看作你和上帝的博弈，你的目标是尽量少的步数变成全0，而上帝是尽量延长这个步数。总状态数量是有限的，双方可知的，这就是一个有限全信息对抗，理论上对于给定的长度n，都可以计算出最优解。
严格增加这点真的太棒了。如果是纯概率操作（遇1变0），则有几率步数是无限的。
60楼你说的才不对，因为小尾巴也可能被上帝改变，所以你以它初始的状态去讨论是不对的，我们只需要关注“最后一轮”它的状态即可。详情看53楼
楼主这个几乎就是最优解了吧。我分析的结果是它和最优解最多差一轮，但不知道对不对。希望大神们分析。
64楼你如果仔细看我写的就不会搞错我60楼说的了，我说的是小尾巴1的时候当然是可控为一直是1的，是0当然不可控，但变成1不就是和前面一样可控了吗？只要一直不变最后左边解完了，整条虫子不久都是0了吗？这么清楚了还要我怎么解释。。。
你好，上次一个纪念马丁加德纳聚会的活动没能邀请你，感觉很遗憾，希望能沟通和联系！
66楼你的说法不对吧，完全依靠概率，能保证有限步骤吗。
68楼请看我60楼的证明吧，66楼只是附加的阐述，我用的是数学归纳法，归纳也就是归纳了所有情况，完全不依靠概率的，如果你要我解释数学归纳法如何保证有限步骤，那我只好再复习下高中知识了：因为情况1能保证，那么根据n->n+1的递推方法，我们能推出2能保证，继而3,4,。。。。这就是数学归纳法,数学归纳法的证明可以轻易的实现，你可以自己编程去验证下
好久没来了，给主人问个安
每次来到这里都发现又有很有趣的文章，总想有一天能看完这里的文章，就像想游览完数学的每个分支一样~真的谢谢你分享了那么多~
唐突提个问题，我纠结很久了。你是怎么理解矢量积这个概念呢？为什么要把它定义成垂直于原来平面的向量？完完全全为了处理角速度、力矩这些概念而构造出来的吗？他们怎么想到这样定义的，那么巧妙，那么自洽……
再次感谢博主~加油！
这个是不是需要考虑初始状态。如果初始值最左一位是1,那是不是代表需要构造n-1位的虫子。也就是文中说的第一次0变成了1的状态。同样无法知道n-1位时虫子的第一位的状态。
这个算法可以优化，概括来说就是对虫子进行分析，然后确定它的头部和尾部，而不是根据最初的状态来确定头部和尾部。
例如：01011这样的序列，为了减少循环的轮数，可以将其顺序定义为11010，然后再进行上面的循环。
同时在每一轮结束，也执行一次寻找头尾的操作，
例如：序列为01000这样的，分析确定其顺序为10000，但是经过循环一轮之后，被随机弄成了10110，那这时候可以将顺序定为11010.
这样最大操作次数可以由2^n变为2^(n-1)
回复 34楼 53楼 60楼等试图用那种归纳法证明的朋友（虽不说归纳一定不行，但至少你们描述的归纳法是不行的）
34楼所说的 最右边的第n+1节“一直砍到是1为止”这已经跟“上帝作对时用有限步”相冲突了，后面几位的归纳法，说n+1节，在左边n节全为0时，如果是0，OK；如果是1则再砍一刀，砍成0，也OK，但是，这已经改变了整个序列，违背了归纳法的原则，48楼的大神HTML已经提到了这点，可被你们无情的无视了
我也不想说我智商多高，因为我的观点也是在看评价时的思考中，一次次变换来变换去的
74楼我真拙计啊.你所谓的违背了归纳法的原则是什么原则?
回复75楼：
我以为根据我所说的再结合48楼，大家应该能看懂了
如果改变了序列（n问题切x刀，x mod n!=0），那么子问题对于父问题来说，就不再是透明的了，两者是有关联的了，具体点讲就是，n+1问题中，其子问题n，如果最后需要多切一刀（也就是我楼上提到的左边n-1节全为0，第n节为1时），这一刀切出来的结果是什么？是切在了第n+1节上面
我有更简单的方法。 每次最右是１时，都在左边添一个和本来最左边相同的数字，目标并非全是１，而是000000011111111的样子。然后就全是0啦。 完成第一步最差的运气需要ｎ的平方个动作。
回复77楼
乍一看就感觉不行，说得太简单了。反证了一下，此方法可能会出现循环，就是砍出来的结果跟原始状态相同
如11001100的初始序列，演变过程为:1100110000001000111001100（从右边往左边一刀刀的砍）
楼主证明无误,收下. 没看懂的请自行重读.
回复75楼
想到了个比较好的解释，如果不保持整倍于长度的切除的话，问题n-1就不是问题n的子问题，独立的n-1问题中，单独切掉一个，切的是第n-1个；而n问题中的“子问题”n-1问题中，单独切掉是一个，切的是第n个，这与独立的n-1问题是不一样的，所以违背了归纳法的基本法则。
然而如果是整倍切除的话，就没有此问题，一轮下来，n中的n-1就像是独立的
我做了一可以在线玩的这个游戏：http://binaryworm.meteor.com。用你说的这个办法，赢实在没有难度。
80楼说的对。
按照我的理解的话，在N+1切一刀后前面的n序列已经不是原来n序列的解决步骤中的一步了。也就是说若N+1的虫子表示为AX，其中A是。而A的解决步骤是先变成B再继续。然而切完以后变成了YB的样子，我们把YB最右端的字节提取，表示成CZ的样子。虽然C也有有限解，但是我们不能保证A、C和以后的某些子问题不会形成循环。
希望解释清楚了。
M67神牛的证明最简无误。
好有趣～
49L亮了~戳中萌点啊
大家看看这种取法可不可以实现：
当最右边的数字是0的时候不考虑。当最右边的数是1的时候是我们可控的，那怎么样来取值呢？这时我们来看最左边的一个数字，如果最左边的数字是0的话，就指定生成的数字是0，如果最左边的数字是1的话，就指定生成的数字是1。相信这样可在有限步内实现目标。
大家看看这个串好像用标准解答中的算法会出现循环:
100100100>000100100>101000100>000101000>
100100010>001001000>100100100
还是我对解答的理解有误。请大家指点。
这题可能是错的，还以序列100100100为例，独立”1″字块的个数是三个，独立”0″字块的个数也是三个。假设”上帝”想要保持字块的个数分布，因为这样永远都不能生成全零序列。如果”1″不转化为”0″的话，”上帝”也就保持”0″不变，如果”1″转化为”0″的话，必然存在一个长度不小于五的”0″字块，而我们万能的”上帝”又可以在这个”0″字块中重新分块保持”0″﹑”1″字块都是三个，所以想要实现完美虫的愿望难以实现。
回复85楼，看下77楼和78楼吧
回复86楼，表示看不懂，说的是这道题么？
回复87楼，标准答案已经说得很清楚了，你无视解答，自己弄出个小世界，并在那里自以为是，否定这个否定那个
冲你这态度，我真想人身攻击你的智商
对不起，我上面的说法是错误的。原来还要固定一个1字块不变。然后才是0>0﹑1>0，0中生成1﹑1保持不变。确实很巧妙。
我还是没有完全明白标准答案，惭愧。还请楼上高手给出100100100序列按照标准答案算法的过程。我不怀疑有解，只是怀疑标准答案上的解是否正确，或者是我对标准答案翻译得有误。还请高手指点。
二进制数将会严格增加————-确实是个很聪明的做法！
这个完全可以来出一个OI题啊
太有意思了吧
完全想不到啊
60楼的解答非常好。
楼主的问题其实不是找到一个解法，而是证明有限次可解。用数学归纳法就可以。不需要从算法的角度找出解题步骤。
好题！
只要0随机出1的概率p>0，那么总步数X是依概率1收敛到有限次范围（给定N次）内
方法很有意思 说不对的没看懂那段话
我当时看了这道题，我先希望能使得1（或者0）的个数不断增大，但是，失败了，后来使用数学归纳法，轻松得证，现在把证明写下来，尽管我厌恶打数学的东东，但是没法说啊呵呵
显然对于1个长度的虫子是ok的，假设对于k长度的虫子成立，我们来看k+1长度的虫，
我们把这条虫子看成两条虫子，分别是前面的k长度虫子，我们记为虫A，以及最后一位的虫子，记为虫B，此时我们把虫B砍掉，虫B可以是1可以是0，所以砍完后长出来的虫B会变成什么，我不知道，但是没关系，虫A仍然按照之前数归的说法是可以砍成全0的，所以我们很谈定的去砍虫B，不管长出什么，而使得虫A慢慢变成全0，这是有限步就能达到的，也就是说，可以变成k个0最后加一个虫B，显然如果虫B是0，那么k+1长度的虫子全是0，问题得证，如果虫B是1，很简单，砍掉1，并长出0（你可以强迫），那么游戏也就结束了，问题非常简单，不懂可以问我
显然在我的证明里藏着巨大的漏洞，我现在知道漏洞了，暂时没时间思考怎么弥补，抱歉
我想说 数学归纳法里面藏着巨大的漏洞，而且，直觉告诉我是个无法挽回的漏洞，我把原文的答案看了下，没什么问题，非常妙，不是简单的使得1的个数增大，而是使得这个数字增大，又怕0只是变成0，所以还要先把1变成0，妙哉！
如果有人对数学归纳法中的漏洞没有看穿的话，可以问我，大家可以自己思考一下漏洞是什么
看了半天，支持trytocatch
看到的所有的归纳法都是错的，好可惜
ls那位，trytocatch并没有说到重点哦，归纳法的问题在于，当虫A（参见96楼的错误证明）变成全0的时候，虫B不一定在最后，也就会出现000…001000…000的情况，各位想通了么，我已经在98楼判定归纳法是不可以使用的，当然不一定不可以使用，这只是我的直觉，如果这道题有有别于原题答案的方法，请一定告诉我，我太想知道了呵呵
我理解的trytocatch在提到了48楼时所包含的意思，应该就说到了你所述的问题了。我和你理解的点是一样的。
回复 34楼与46楼
关于“一直砍到是1为止”事实上你可以在左边没有变成0的时候 无视右边的那一个只要简单的砍去他就可以了，当左边都变成0时，右边的那一个是1 就继续原结尾操作，是0就无视
但 我认为存在另一个问题 对n+1的最后一步操作会改变原有顺序（将最后一个变成第一个） 使得对n+2的操作中当一开始的左边n个变成0时 一开始的最右边一个变成了作起第二位
这是48楼的吧，你看看就知道了，他以为整条虫每次砍一下，就把最后一个看成虫B，这样实际上虫B在变，这是很愚蠢的数归（我没看前面的人的数归，我猜不是这个意思），我在98楼给的数归，是把最后的那位虫B看成不变的，你明白我的意思了么？呵呵
我想48楼想表述的意思和你说的一样，知识他表述的方式未必有你说的那样易懂。
首先，48楼时在34楼和46楼的基础上进行衍生的，34楼提出的是“一直砍到是1为止”，然后再退化为一个n序列右边一个1。再用数学归纳法归纳。事实上，34楼的问题不是46楼提到的“永远不会为1”，相反，在一轮内，肯定可以让最右边一位为1（因为序列不是全0的，等到序列中的1到最右边即可）。
34楼的问题是48楼第二段提到的。就是假如归纳法n->n+1是成功的，那么n+1->n+2时，在试图将左n+1个变为0时，当左n个变为0，形成如1000…001的形式（这里假设归纳时最后两位都是1，便于和全0序列区分），最开始的最右一位现在居于左起第一位。这时运用n->n+1是的策略，将最右边的1砍掉，那么会形成0100…000。我想这就是48楼说的“变成了左起第二位”。
显然这一迭代是失败的，归纳法失效。
我窃以为这和你所说的“虫A（参见96楼的错误证明）变成全0的时候，虫B不一定在最后，也就会出现000…001000…000的情况”在本质上是一个意思。当然，你说的更有普遍性。
我重新看了34楼，“如果这个数是0，那么就砍掉，一直砍到是1为止。”这句似乎有歧义，我想34楼不会异想天开的认为原来这个为0的数总有一次会被砍成1，所以我采用了另外一种理解，而不是46楼的“永远不会为1”。
当然，我这样的理解的证明除了48楼提出的问题外，还有一个问题，就是归纳之前的调整，当n->n+1时，无法保证对n+1序列的调整能够刚好促成n序列的调整。
你的意思我懂，只不过34楼的意思是什么，我不清楚呵呵，能讨论很高兴，我在《趣题：空间四边形外切于给定球，求证四切点共面》给了一个数学证明，希望你能去看看，是不是证得没有问题呵呵，互相讨论互相学习哈
n=5时的最优解，不知能找出什么规律来么
00001
00010
00100
01001
10010
00101
01010
10100
01000
10001
00011
00110
01101
11010
10101
01011
10110
01100
11001
10011
00111
01110
11101
11011
10111
01111
11111
11110
11100
11000
10000
00000
见上面一条回复，从全0串倒着开始。如果产生的串不重复，则前面添加1，后面去掉一位。否则前面添加0，后面去掉一位。容易证明，如此构造出来的串，0abcd一定在abcd0和abcd1的上面。因此对手无论如何选择，一定能不停向下走直到全0串，而且是最优解。
接着，只需证明如此构造方法能够遍历从全0到全1的所有串即可。
在虫子变成全1串之前，遇1选1，不论怎么随机，总会使串变成全1，之后必胜
楼上，不是随机，是故意给你捣乱的对手。
接107楼
假设不在如此构造序列中的首0最少的串是00001abcdefg，
则0001abcdefg1和0001abcdefg0都在构造序列中，由于构造方法要求不产生重复串，以上两个串不可能都产生10001abcdefg，故必有其一产生00001abcdefg，与假设矛盾。
所以该构造方法确实可以遍历所有串。
回复100楼lbf003000
我是从归纳法的原理上反证，你是用一个具体存在的矛盾去反证，你我的切入点不同罢了
另外，我觉得这题应该不会有其它解了（换汤不换药的不算），上帝每时每刻都与你作对，你能做的是，必需把上帝的每一次捉弄都转化成对自己的一丁点恩赐，一点点地向目标前进，二进制数严格增大正好能做到这点，其它投机取巧的做法，只能是被上帝愚弄罢了
数学归纳法：长度1的序列显然有有限解。
若当n=k时有有限解，当n=k+1时，将末尾的一节（称作X）若为1则变为1，若为0则随机，这样X不影响前k节。使前k节变为完美，当前k节变为完美时正好到X，若X为0已完美，若X为1则变为0，完美。
数学归纳法：
长度1的序列显然有有限解。
若当n=k时有有限解，当n=k+1时，将末尾的一节（称作X）若为1则变为1，若为0则随机，这样X不影响前k节。使前k节变为完美，当前k节变为完美时正好到X，若X为0已完美，若X为1则变为0，完美。
欧，一不小心发了两遍。
就是0 1随机过程中获得长度为m的特定序列的停时问题嘛
好方法！
60 楼的数学归纳法有问题，但很容易修正。设 A[k] = 格子内容，S[k] = A[1,k] 的序列， T(S) = 该序列所需步骤轮。
在 n+1 规模时，60 楼等到 T(S[n])+1 轮方才修改了 A[n+1] = 1 -> 0，导致 S[n] 在该轮没有刷新，不符合数学归纳法。
正确方法仍然是每次随机 A[n+1] = 0，保持 A[n+1] = 1。讨论第 T(S[n]) 轮开始时的情况。
(a) A[n+1] = 1，在该轮立即与 S[n] 一起修改为零。该轮整个序列刷新完毕，完成任务。
(b) A[n+1] = 0，且该轮保持随机数 0。该轮整个序列刷新完毕，完成任务。
(c) A[n+1] = 0，且(坑爹的上帝)恰好该轮刷新为 1。此时强制刷新 S[n]（即使已经可以完全变为 0），一切从头重新来过，这时由于保持 A[n+1] = 1 而最终一定会落入 (a) 的情况，也就是说可以做最多 2 遍 S[n] 的问题而完成 S[n+1]，而且每次都能保证完整刷新序列后结束过程。证毕。
60 楼的数学归纳法有问题，但很容易修正。设 A[k] = 格子内容，S[k] = A[1,k] 的序列， T(S) = 该序列所需步骤轮。
在 n+1 规模时，60 楼等到 T(S[n])+1 轮方才修改了 A[n+1] = 1 -> 0，导致 S[n] 在该轮没有刷新，不符合数学归纳法。
正确方法仍然是每次随机 A[n+1] = 0，保持 A[n+1] = 1。讨论第 T(S[n]) 轮开始时的情况。
(a) A[n+1] = 1，在该轮立即与 S[n] 一起修改为零。该轮整个序列刷新完毕，完成任务。
(b) A[n+1] = 0，且该轮保持随机数 0。该轮整个序列刷新完毕，完成任务。
(c) A[n+1] = 0，且(坑爹的上帝)恰好该轮刷新为 1。此时强制刷新 S[n]（即使已经可以完全变为 0），一切从头重新来过，这时由于保持 A[n+1] = 1 而最终一定会落入 (a) 的情况，也就是说可以做最多 2 遍 S[n] 的问题而完成 S[n+1]，而且每次都能保证完整刷新序列后结束过程。
证毕。
有点表达不清，修正一下：
60 楼的数学归纳法有问题，但很容易修正。设 A[k] = 格子内容，S[k] = A[1]-A[k] 的序列， T(S) = 该序列所需步骤轮。
在 n+1 规模时，60 楼等到 T(S[n])+1 轮方才修改了 A[n+1] = 1 -> 0，导致之前的 S[n] 在该轮没有刷新，不符合数学归纳法。
正确方法仍然是每次按步执行 S[n] 的方案，随机 A[n+1] = 0，保持 A[n+1] = 1。讨论第 T(S[n]) 轮开始时的情况。
(a) A[n+1] = 1，在该轮立即与 S[n] 一起修改为 0。
(b) A[n+1] = 0，且该轮保持随机数 0，直接修改 S[n] 为 0。
(c) A[n+1] = 0，且(坑爹的上帝)恰好该轮刷新为 1。此时在下一轮强制刷新 S[n]（即使已经全为 0），如果刷出了 1，则一切从头重新来过，重新按新的 S[n] 执行。
这时由于保持 A[n+1] = 1 而最终一定会落入 (a) 的情况，也就是说可以做最多 2 遍不同的 S[n] 的问题而完成 S[n+1]。
即 For all S[n+1], T[S[n+1]] <= MAX {2T[S[n]], For all S[n]}
每次都能保证完整刷新序列后结束过程。
证毕。
好像还是有问题……T(S[n]) 的存在不确定性
这是一个极为巧妙的题，我觉得这么漂亮的题都很少见
楼上一群理解能力差的人能不能别再玷污这么好的题了= =
话说怎么这么多人没看懂这个证法.(这个证法很好呀)
号