由0和1構(gòu)成的蟲子

有一條蟲子，它的整個(gè)身體由 n 節(jié)構(gòu)成，每一節(jié)要么是有瑕疵的 1 ，要么是沒(méi)有瑕疵的 0 ，因而整個(gè)蟲子的身體結(jié)構(gòu)就可以用一個(gè) n 位 01 串來(lái)表示。你的目標(biāo)是把整個(gè)蟲子變成 000...00 的完美形式。每一次，你可以砍掉蟲子最右側(cè)的一節(jié)，同時(shí)蟲子會(huì)在最左側(cè)長(zhǎng)出新的一節(jié)，以保持蟲子的總長(zhǎng)度不變。如果你砍掉的是一個(gè) 1 ，那么你可以指定蟲子在最左側(cè)長(zhǎng)出的是 1 還是 0 ；但如果你砍掉的是一個(gè) 0 ，那么你無(wú)法控制蟲子會(huì)在最左側(cè)長(zhǎng)出什么——它可能會(huì)長(zhǎng)出 0 ，也可能會(huì)長(zhǎng)出 1 ，因而你不得不假定，概率總是會(huì)和你做對(duì)，上天會(huì)竭盡全力地阻撓你。我們的問(wèn)題是：不管蟲子的初始狀態(tài)是什么，你總能保證在有限步之內(nèi)讓蟲子變成 000...00 嗎？
注意，這個(gè)問(wèn)題可能沒(méi)有你想的那么簡(jiǎn)單。顯然，我們必須得把一些 1 變成 0 ，這樣才能讓 1 的數(shù)目逐漸減少并最終消失。但是，如果只是簡(jiǎn)單地每次都把 1 變成 0 ，最終也不見(jiàn)得就一定能取勝。比如，如果這條蟲子是 101 ，那么去掉最右邊的 1 并選擇在左邊長(zhǎng)出一個(gè) 0 ，蟲子會(huì)變成 010 ；再把 010 右邊的 0 去掉后，如果不巧左邊長(zhǎng)出的是 1 ，那么整條蟲子又會(huì)回到 101 的狀態(tài)。如此反復(fù)，將永遠(yuǎn)也不能得到 000 。而更加聰明的方法則是先把 101 變成 110 ，下一步蟲子將會(huì)變成 111 或者 011 ，不管是哪種情況，接下來(lái)只需要逐個(gè)把 1 變成 0 就能獲勝了。運(yùn)用恰當(dāng)?shù)牟呗圆拍茏叩浇K點(diǎn)，這無(wú)疑讓問(wèn)題變得更加有趣。
不管蟲子一開始是什么樣子的，我們總能夠在有限步之內(nèi)獲勝。下面是 Peter Winkler 給出的證明。讓我們把連續(xù) n 次操作視為一輪操作，因而完成一輪操作正好讓蟲子的整個(gè)身體更新一次。于是，每一輪操作實(shí)際上相當(dāng)于是從右到左依次考慮蟲子的每一位，每遇到一個(gè) 1 時(shí)你都可以選擇是否把它修改成 0 ，每遇到一個(gè) 0 時(shí)它都會(huì)隨機(jī)地被修改成 1 。我們一輪一輪地改造蟲子的身體，并且每一輪都采取這樣的策略：從最右端開始，每次遇到 1 都把它改成 0 ，直到第一次有 0 被改成 1 ；在此之后，不管新遇到的 0 變沒(méi)變，都保留所有的 1 不變。如果這一輪下來(lái)后，沒(méi)有 0 被改成 1 ，那么我們將會(huì)把所有的 1 都替換成 0 ，從而得到 000...00 的形式，直接獲得勝利；如果途中有 0 被改成了 1 ，那么整個(gè)蟲子作為一個(gè)二進(jìn)制數(shù)將會(huì)嚴(yán)格增加。每經(jīng)過(guò)一輪后，只要蟲子沒(méi)有變成 000...00 ，整個(gè)二進(jìn)制數(shù)都會(huì)變得更大，最終將會(huì)變成 111...11 的形式，此時(shí)再也不會(huì)有 0 變成 1 了，于是按照我們的策略，在下一輪中，所有的 1 都會(huì)變成 0 ，從而獲得勝利。