在漆黑的夜里，四位旅行者來(lái)到了一座狹窄而且沒(méi)有護(hù)欄的橋邊。如果不借助手電筒的話(huà)，大家是無(wú)論如何也不敢過(guò)橋去的。不幸的是，四個(gè)人一共只帶了一只手電筒，而橋窄得只夠讓兩個(gè)人同時(shí)過(guò)。如果各自單獨(dú)過(guò)橋的話(huà)，四人所需要的時(shí)間分別是1、2、5、8分鐘；而如果兩人同時(shí)過(guò)橋，所需要的時(shí)間就是走得比較慢的那個(gè)人單獨(dú)行動(dòng)時(shí)所需的時(shí)間。問(wèn)題是，如何設(shè)計(jì)一個(gè)方案，讓這四人盡快過(guò)橋。

　　假設(shè)這四人分別為A、B、C、D。很明顯，開(kāi)始兩人拿著手電筒過(guò)橋后，手電筒就在橋的另一邊了，此時(shí)需要已經(jīng)過(guò)橋的那兩人中的一個(gè)再把手電筒送回橋這邊。送手電筒回來(lái)過(guò)橋也要化時(shí)間，所以要選一個(gè)跑得比較快的。一個(gè)很自然的想法就是，每次讓跑得最快的A陪著另一個(gè)過(guò)橋，然后A快速地跑回來(lái)，再陪下一位過(guò)去，最后所有人就都可以過(guò)橋了。

　　讓我們來(lái)算一下這要多長(zhǎng)時(shí)間。為了方便起見(jiàn)，我們把旅行者出發(fā)的橋的這一邊稱(chēng)為“此岸”，而把旅行者想要到達(dá)的那邊叫“彼岸”。在表達(dá)一個(gè)過(guò)橋方案時(shí)，我們用“←”來(lái)表示從彼岸到此岸的移動(dòng)，用“→”表示從此岸到彼岸的移動(dòng)。前面“A護(hù)送大家過(guò)河”的方案就可以寫(xiě)成：（右邊數(shù)字為完成此步驟所需時(shí)間）

　　　　　　　　　　A　B　→　2
　　　　　　　　　　　 A　←　1
　　　　　　　　　　A　C　→　5
　　　　　　　　　　　 A　←　1
　　　　　　　　　　A　D　→　8

一共就是2+1+5+1+8=17分鐘。

　　但其實(shí)有更快的辦法：

　　　　　　　　　　A　B　→　2
　　　　　　　　　　　 A　←　1
　　　　　　　　　　C　D　→　8
　　　　　　　　　　　 B　←　2
　　　　　　　　　　A　B　→　2


一共是2+1+8+2+2=15分鐘。這個(gè)辦法的聰明之處在于讓兩個(gè)走得最慢的人同時(shí)過(guò)橋，這樣花去的時(shí)間只是走得最慢的那個(gè)人花的時(shí)間，而走得次慢的那位就不用另花時(shí)間過(guò)橋了?？梢园阉锌赡艿姆桨付剂信e一遍，就會(huì)發(fā)現(xiàn)這是最快的方案了。

　　現(xiàn)在我們把這個(gè)問(wèn)題推廣到N(N≥4)個(gè)人過(guò)橋的情況：如果有N個(gè)旅行者，假設(shè)他們有各自所需的過(guò)橋時(shí)間（正實(shí)數(shù)）。在只有一只手電筒的情況下，要過(guò)上述的一條橋，怎樣才能找到最快的過(guò)橋方案？

　　假設(shè)最快地把N個(gè)旅行者從此岸移動(dòng)到彼岸需要f分鐘時(shí)間，那么我們把所有在f分鐘時(shí)間內(nèi)把N個(gè)旅行者從此岸移動(dòng)到彼岸的方案稱(chēng)為“最佳方案”。最佳方案很有可能不止一個(gè)，我們的目的是要找到一個(gè)最佳方案，但是并不需要把所有的最佳方案全都找出來(lái)。

　　為了討論的方便起見(jiàn)，這一節(jié)我們要說(shuō)明的是，事實(shí)上我們可以假設(shè)每個(gè)旅行者的速度都是不一樣的。這樣當(dāng)我們說(shuō)一些人中“最快的那個(gè)”，“次慢的那一個(gè)”時(shí)，都不會(huì)有歧義了，因?yàn)槊總€(gè)人的速度都是獨(dú)一無(wú)二的。這個(gè)假設(shè)在討論中并非必要，只是為了在證明的敘述過(guò)程中避免不斷地啰嗦類(lèi)似“我們讓兩人中最快的那個(gè)過(guò)橋，如果兩人一樣快，那就隨便選一人”、“我們選在彼岸最快的那個(gè)人回來(lái)，如果上一步剛從此岸到彼岸的人中，其中有一個(gè)是現(xiàn)在彼岸走得最快的之一，我們就特別選擇讓他回來(lái)”之類(lèi)的話(huà)。

　　為什么我們可以假設(shè)每個(gè)旅行者的速度都是不一樣的？原理就在于，我們可以把原來(lái)過(guò)橋時(shí)間相同的旅行者的過(guò)橋時(shí)間分別加上一個(gè)不同的但是非常非常小的量，這樣就能保證旅行者的速度是不一樣的了。但是因?yàn)榧由先サ牧慷挤浅Ｐ?，所以?duì)最終總的過(guò)橋時(shí)間的影響也非常小。所以這樣改動(dòng)過(guò)后得到的最佳方案在原來(lái)的條件下實(shí)施的話(huà)，也該是原來(lái)?xiàng)l件下的最佳方案。

　　如果你對(duì)上面的說(shuō)明滿(mǎn)意了，就完全可以跳過(guò)這一節(jié)直接看第三節(jié)。這一節(jié)后面啰哩叭嗦的都是為了向一些對(duì)嚴(yán)格性要求比較高的朋友解釋上面所說(shuō)的方法的確可行。

　　首先對(duì)于任何一組N個(gè)旅行者，假定他們過(guò)橋所需的時(shí)間分別為a₁、a₂、……、a_N，它們都是大于零的實(shí)數(shù)。假設(shè)這個(gè)序列已經(jīng)從小到大排列了（當(dāng)然不排除其中有數(shù)相等）。每次都由第一個(gè)旅行者陪同一個(gè)人過(guò)橋，然后第一個(gè)旅行者回來(lái)，這樣一個(gè)方案所需要的時(shí)間是：

　　　　S = (N-2)*a₁+a₂+……+a_n

（第一個(gè)旅行者要返回N-2次）。所以最佳方案所需要的時(shí)間一定不會(huì)比S大。

　　我們把一個(gè)過(guò)橋方案中讓一個(gè)或者兩個(gè)人拿著手電筒從橋的一邊走到另一邊的一次移動(dòng)叫做這個(gè)方案中的一次移動(dòng)或者“一步”，就是前面解四個(gè)人的題中使用“→”或“←”來(lái)表示的一個(gè)步驟。因?yàn)橐淮我苿?dòng)所需要的最少的時(shí)間是a₁分鐘，所以最佳方案中所需的移動(dòng)步數(shù)一定不會(huì)多于K=[S/a₁]步，這里"[]"是取整運(yùn)算。

　　讓我們考慮一下所有在K步以?xún)?nèi)完成的方案。上面的例子表明這樣的方案至少有一個(gè)，而且這樣的方案顯然只有有限多個(gè)，假設(shè)一共有M個(gè)。我們又設(shè)這些方案執(zhí)行時(shí)要花的時(shí)間是

　　　　t₁、t₂、……、t_M

我們還可以假設(shè)上面這些時(shí)間已經(jīng)從小到大排列了，t₁就是最佳方案所需要的時(shí)間。

　　現(xiàn)在是關(guān)鍵的步驟。我們要選取一個(gè)很小的正實(shí)數(shù)ε＞0。它有多小呢？它必須滿(mǎn)足下面的條件：

1) 對(duì)于任何兩個(gè)過(guò)橋時(shí)間不同的旅行者（假設(shè)他們的過(guò)橋時(shí)間是a和b分鐘），必須滿(mǎn)足ε＜|a-b|/N。換句話(huà)說(shuō)，Nε要小于不同的旅行者過(guò)橋時(shí)間之間的差別。

2) 對(duì)于任何兩個(gè)所需的完成時(shí)間不同的K步以?xún)?nèi)的方案（假設(shè)它們的所需時(shí)間是t和s分鐘），必須滿(mǎn)足ε＜|t-s|/K。換句話(huà)說(shuō)，Kε要小于不同的方案完成時(shí)間之間的差別。

因?yàn)槁眯姓叩臄?shù)目和方案的數(shù)目都是有限的，所以我們必然可以選取這樣一個(gè)ε。至于這兩個(gè)條件有什么用，我們馬上就可以看到。

　　假設(shè)若干個(gè)旅行者過(guò)橋的時(shí)間都是一樣的a分鐘，我們就把題目改一下，使得他們的過(guò)橋時(shí)間分別為

　　　　a、a+ε/N、a+2ε/N、a+3ε/N……

如果有其他的旅行者過(guò)橋時(shí)間相互一樣，也按照同樣方式修改題目。這時(shí)在修改后的題目中，如果原來(lái)兩個(gè)旅行者所需的過(guò)橋時(shí)間相同，那么現(xiàn)在就變得不同，差一個(gè)非常小的量（不會(huì)超過(guò)ε）；如果原來(lái)兩個(gè)旅行者所需的過(guò)橋時(shí)間不同，那么根據(jù)上面的條件1)，現(xiàn)在還是不同，而且原來(lái)誰(shuí)比較快，現(xiàn)在仍舊是他比較快。

　　我們看看這個(gè)修改后的題目的最佳方案和原來(lái)的題目的最佳方案有什么聯(lián)系。

　　假設(shè)我們已經(jīng)有一個(gè)關(guān)于修改后的題目的最佳方案，那么它所需要的時(shí)間必定是這個(gè)模樣的：

　　　　a + bε

我們知道bε部分是修改時(shí)把旅行者過(guò)橋時(shí)間“微調(diào)”了以后造成的，而且每走一步這部分的改變不會(huì)超過(guò)ε，所以我們有0＜b＜K=[S/a₁]。

　　如果我們把這個(gè)最佳移動(dòng)方案照搬到原來(lái)的題目中去，所需要的時(shí)間就是a分鐘。這個(gè)方案應(yīng)該同樣是原來(lái)題目中的最佳方案。否則的話(huà)，假設(shè)我們有另一個(gè)方案，所需時(shí)間為a‘，而且a‘＜a。根據(jù)上面取ε時(shí)候的條件2)，我們有

　　　　a‘ ＜ a + Kε

把這個(gè)耗時(shí)a‘的方案搬到改動(dòng)過(guò)的題目里去的話(huà)，所需的時(shí)間就會(huì)是

　　　　a‘ + b‘ε

其中0＜b‘＜K。所以根據(jù)a‘＜a+Kε

　　　　a‘ + b‘ε ＜ a + bε

這就和a+bε是改動(dòng)后題目的最佳方案所需的時(shí)間矛盾了。

　　所以只要找到一個(gè)修改過(guò)的題目中的最佳方案，我們就得到了原來(lái)題目中的一個(gè)最佳方案，于是我們只要考慮所有旅行者的速度都不同的題目就可以了。

　　編個(gè)計(jì)算機(jī)程序，把所有步數(shù)少于上一節(jié)中所計(jì)算的K=[S/a₁]的可能的過(guò)橋方案都列舉一遍，然后找出最快的，當(dāng)然是一種方法，這理論上也是可行的，因?yàn)樯儆贙步的方案只有有限多個(gè)，計(jì)算機(jī)程序必定能夠?qū)⑺鼈內(nèi)苛信e出來(lái)。只是當(dāng)人數(shù)N增大時(shí)，過(guò)橋方案數(shù)會(huì)增加得很快。事實(shí)上，如果我們只考慮“每次過(guò)去兩個(gè)人，然后這兩個(gè)人中其中一個(gè)人回來(lái)”這類(lèi)方案的數(shù)目的數(shù)量就已經(jīng)遠(yuǎn)遠(yuǎn)超過(guò)N!個(gè)了，想像一下如果N=1000的話(huà)所需要的計(jì)算量！況且還有更多數(shù)量的其他類(lèi)型方案。特別是，我們是在做智力題，不是在學(xué)編程。當(dāng)然你還可以說(shuō)，如果人多的話(huà)，所需要的時(shí)間超過(guò)了12小時(shí)，那時(shí)天已經(jīng)亮了，不再需要手電筒，大家可以直接過(guò)橋——唉！我們是在做智力題，不是在做抬杠式的腦筋急轉(zhuǎn)彎——我們可以假設(shè)是在有漫長(zhǎng)極夜的極地嘛，要不然，這橋是在一個(gè)黑暗山洞里，就象電影《指環(huán)王》中的那樣……

　　但是如果不用列舉法的話(huà)，我們有一個(gè)重要的任務(wù)要做，就是不僅要說(shuō)明如何找到一個(gè)我們自以為最快的方案，而且還要證明這樣的方法的確給出了一個(gè)最佳方案。

　　在我們的直覺(jué)當(dāng)中，最快的方案必然有這樣一個(gè)特征：每次過(guò)橋去彼岸的一定是兩個(gè)人，然后一定只有一個(gè)人把手電筒送回此岸（當(dāng)然要除去最后一次過(guò)橋的情況，那時(shí)就不需有人把手電筒送回來(lái)了）。但是為什么一定是這樣的呢？為什么不可能有一個(gè)意想不到的巧妙方案，在那里有某一步居然需要一個(gè)人單獨(dú)過(guò)到彼岸去，或者需要有兩個(gè)人把手電筒送回此岸來(lái)？這是個(gè)看起來(lái)很顯而易見(jiàn)但是我們不能支吾不回答的問(wèn)題。

　　在討論中我們經(jīng)常需要說(shuō)明，在某一時(shí)刻，橋的兩邊分別有哪些人，手電筒又在哪一邊。這樣的說(shuō)明稱(chēng)為一個(gè)“局面”。當(dāng)然，一個(gè)局面必須是合理的。比如說(shuō)，不能夠所有人都在橋的一邊，而手電筒卻在橋的另一邊；一個(gè)人必須處在橋的某一邊，而且只能處在橋的某一邊。

　　比如說(shuō)，在四個(gè)旅行者的問(wèn)題里，如果某一個(gè)時(shí)刻A、B和C在此岸，而D在彼岸，手電筒也在彼岸，這就給出了一個(gè)局面（這個(gè)局面看起來(lái)有點(diǎn)奇怪，大概是D拿著手電筒一個(gè)人跑過(guò)橋去了，接下去除了他再拿著手電筒回來(lái)別無(wú)它法）。所有人和手電筒都在此岸，就是一個(gè)特殊的局面，叫作初始局面；而所有人和手電筒都在彼岸，也是一個(gè)特殊的局面，叫完結(jié)局面；所有其他的局面我們稱(chēng)為中間局面。

　　想像一下現(xiàn)在有兩種局面。在兩種局面中，手電筒都在橋的同一邊（都在此岸或都在彼岸）；而且在第一種局面里所有在彼岸的旅行者，在第二種局面里也都在彼岸，而且有這樣的旅行者，在第一種局面中他在此岸，而第二種局面中他在彼岸。那么我們就說(shuō)第二種局面“優(yōu)于”第一種局面。

　　比如說(shuō)，在四個(gè)旅行者的問(wèn)題里，第一種局面是A、B和C在此岸，而D在彼岸，手電筒也在彼岸；第二種局面是A和B在此岸，C和D在彼岸，手電筒也在彼岸。那么第二種局面就優(yōu)于第一種局面。很顯然，除了初始局面以外，所有手電筒在此岸的局面都優(yōu)于初始局面；除了完結(jié)局面本身外，完結(jié)局面要優(yōu)于所有手電筒在彼岸的局面。但是要注意的是，并不是任意給兩個(gè)局面都能比較哪個(gè)優(yōu)于哪個(gè)，比如說(shuō)初始局面和完結(jié)局面，誰(shuí)都不優(yōu)于誰(shuí)。

　　如果現(xiàn)在有兩個(gè)局面，第二種局面要優(yōu)于第一種局面。假設(shè)現(xiàn)在我已經(jīng)有了一個(gè)方案，從第一種局面開(kāi)始，通過(guò)符合題目要求的方法來(lái)移動(dòng)旅行者（最多只能同時(shí)移動(dòng)兩個(gè)旅行者，手電筒必須和他們一起移動(dòng)），在t分鐘內(nèi)能夠使所有旅行者到達(dá)彼岸（也就是說(shuō)轉(zhuǎn)變成完結(jié)局面，或者說(shuō)“解決”了這種局面），那么我們可以保證我們同樣也有了一個(gè)方案，從第二種局面開(kāi)始，在不多于t分鐘內(nèi)使它轉(zhuǎn)變成完結(jié)局面。

　　為什么呢？

　　假設(shè)第一種局面的方案中的第一步是要把某個(gè)（或某兩個(gè)）旅行者從此岸移動(dòng)到彼岸（這時(shí)手電筒開(kāi)始一定在此岸）。

1) 如果被移動(dòng)的這個(gè)（或這兩個(gè)）旅行者，在第二種局面里也在此岸，那么我們同樣把他們從此岸移動(dòng)到彼岸。這時(shí)兩個(gè)局面化了同樣多的時(shí)間轉(zhuǎn)化成另兩個(gè)局面，而且仍舊是第二種局面優(yōu)于第一種局面。（嚴(yán)格說(shuō)來(lái)應(yīng)該是“從第二種局面演化來(lái)的局面要優(yōu)于從第一種局面演化來(lái)的局面”，不過(guò)這樣也太拗口了，所以在下面我都用前面那種雖然不嚴(yán)格但是比較簡(jiǎn)明的方法來(lái)敘述。）

2) 如果被移動(dòng)的有兩個(gè)旅行者，但是只有一個(gè)在第二種局面里是在此岸，那么我們把他從此岸移動(dòng)到彼岸。如果這個(gè)旅行者是兩個(gè)中跑得比較快的，那么這一步所化時(shí)間會(huì)比第一種局面要少；如果他是跑得比較慢的那個(gè)，那么這一步所化時(shí)間就和第一種局面一樣。而且經(jīng)過(guò)這一步轉(zhuǎn)化后，第二種局面或者和第一種局面一樣，或者仍舊優(yōu)于第一種局面。

3) 如果被移動(dòng)旅行者都不在此岸，那么情況要稍微復(fù)雜點(diǎn)。如果在第一種局面中經(jīng)過(guò)這步移動(dòng)后就變?yōu)橥杲Y(jié)局面，那么這意味著第二種局面中所有人早已到達(dá)彼岸，而這是不可能的，此時(shí)第二種局面中手電筒不可能在此岸。所以在第一種局面中經(jīng)過(guò)這步移動(dòng)后，還會(huì)有接下去的一步，把某個(gè)（或某兩個(gè)）旅行者從彼岸移動(dòng)到此岸。我們很容易看到，第二種局面無(wú)需任何耗費(fèi)時(shí)間的移動(dòng)，要優(yōu)于第一種局面經(jīng)過(guò)兩次移動(dòng)后演變得到的結(jié)果！因?yàn)榻?jīng)過(guò)兩步移動(dòng)后，第一種局面里在彼岸多出來(lái)的旅行者，在第二種局面里早已都在彼岸。

　　假設(shè)第一種局面的方案中的第一步是要把某個(gè)（或某兩個(gè)）旅行者從彼岸移動(dòng)到此岸（這時(shí)手電筒開(kāi)始一定在彼岸），那么這就很簡(jiǎn)單，在第二種局面里這個(gè)（或這兩個(gè)）旅行者一定也在彼岸，所以我們用相同的一步移動(dòng)，花費(fèi)一樣的時(shí)間，把這個(gè)（或這兩個(gè)）旅行者移動(dòng)到此岸。這樣得到的結(jié)果還是第二種局面要優(yōu)于第一種局面。

　　于是總而言之，無(wú)論第一種局面中采取什么樣的移動(dòng)，我們總可以采取花費(fèi)同樣多的時(shí)間（甚至更少或者根本不花費(fèi)時(shí)間）的移動(dòng)，使得第二種局面或者變?yōu)楹偷谝环N局面相同，或者仍舊優(yōu)于第一種局面。于是當(dāng)?shù)谝环N局面演變?yōu)橥杲Y(jié)局面時(shí)，第二種局面也一定演變?yōu)橥杲Y(jié)局面了，而花費(fèi)的時(shí)間不會(huì)多于第一種局面所需的時(shí)間。

　　于是我們得到了很顯然的結(jié)論：

結(jié)論一：如果有兩種局面，第二種局面優(yōu)于第一種局面，那么我們總可以用少于解決第一種局面的時(shí)間來(lái)解決第二種局面。

　

　　通過(guò)結(jié)論一我們立刻得到：

結(jié)論二：一定有這樣一種最佳方案，在這個(gè)方案里，所有從彼岸到此岸的移動(dòng)只需一個(gè)人。

　　如果最佳方案中有一步中需要兩個(gè)人從彼岸移動(dòng)到此岸，那么我們可以把這一步改為只移動(dòng)比較快的那個(gè)人。在這一步后，我們花費(fèi)了最多和原來(lái)相同的時(shí)間，得到的局面卻優(yōu)于按原先方案執(zhí)行完這一步后的局面，所以剩下的解決步驟不會(huì)比原方案花費(fèi)更多的時(shí)間，所以必定是個(gè)最佳方案。

　　現(xiàn)在我們知道，我們可以要求在最佳方案中，每次只回來(lái)一個(gè)人。在下面我們要得出另一個(gè)結(jié)論：

結(jié)論三：一定有這樣一種符合結(jié)論二的最佳方案，在這個(gè)方案里，所有從彼岸到此岸的移動(dòng)中，回來(lái)的這個(gè)人一定是當(dāng)時(shí)在彼岸所有人中速度最快的。

　　假設(shè)在所有滿(mǎn)足結(jié)論二的最佳方案中，都沒(méi)有符合結(jié)論三的方案，也就是說(shuō)，任何一個(gè)最佳方案中，總有某一步從彼岸到此岸的移動(dòng)中，回來(lái)的那個(gè)人不是當(dāng)時(shí)在彼岸所有人中速度最快的。那么我們?cè)谶@些最佳方案中選取一個(gè)這樣的“壞”步驟最晚出現(xiàn)的方案。假設(shè)這個(gè)步驟首先出現(xiàn)在第n步。

　　我們特別假設(shè)在這第n步中回來(lái)的這個(gè)人是B，他的過(guò)橋所需的時(shí)間為b分鐘，而當(dāng)時(shí)在彼岸所有人中速度最快的是A，他的過(guò)橋所需的時(shí)間為a分鐘?，F(xiàn)在我們開(kāi)始把第n步“讓B回來(lái)”改為“讓A回來(lái)”。

　　　　　　　　原來(lái)的方案　　　　　　　修改后的方案
　　　　　　　　　……　　　　　　　　　　　……
　　　第n步：　　　B ←　　　　　　　　　　A ←

現(xiàn)在兩種局面的唯一區(qū)別在于，前一種是A在彼岸B在此岸，而后一種是B在彼岸A在此岸。但是前一種局面要比后一種局面多耗時(shí)b-a分鐘。

　　在第n步后面接下去的移動(dòng)步驟中，只要不牽涉A或B，那么可以在原來(lái)方案中進(jìn)行的移動(dòng)仍舊可以在改變了的方案中進(jìn)行。而第n步后第一次牽涉到A或B的在原方案中的行動(dòng)（我們假設(shè)它是第n+i步）只能是：

1) 把A從彼岸移動(dòng)到此岸。此時(shí)我們?cè)诟脑旆桨钢械囊苿?dòng)就是：把B從彼岸移動(dòng)到此岸。這時(shí)局面就變成和原來(lái)的完全一樣了，上一次由于用A來(lái)?yè)QB節(jié)省的b-a分鐘也在這步中耗費(fèi)掉了。接下去我們使用原方案完成其他移動(dòng)。所以改造后的方案同樣是個(gè)最佳方案：

　　　　　　　　原來(lái)的方案　　　　　　　修改后的方案
　　　　　　　　　……　　　　　　　　　　　……
　　　第n步：　　　B ←　　　　　　　　　　A ←
　　　　　　　　　……　　　　　　　　　　　……
　　第n+i步：　　　A ←　　　　　　　　　　B ←
　　　　　　　　　……　　　　　　　　　　　……

省略號(hào)部分表示此部分兩個(gè)方案相同。

2) 把B從此岸移動(dòng)到彼岸（可能還有另一個(gè)過(guò)橋時(shí)間為c分鐘的C和他一起移動(dòng)）。這就比較簡(jiǎn)單，第n+i步我們?cè)诟脑旌蟮姆桨钢羞€是用A來(lái)代替B，然后局面就恢復(fù)到原來(lái)的情況，接下去我們使用原方案完成其他移動(dòng)：

　　　　　　　　原來(lái)的方案　　　　　　　修改后的方案
　　　　　　　　　……　　　　　　　　　　　……
　　　第n步：　　　B ←　　　　　　　　　　A ←
　　　　　　　　　……　　　　　　　　　　　……
　　第n+i步：　B (C) →　　　　　　　　A (C) →
　　　　　　　　　……　　　　　　　　　　　……

這里括號(hào)內(nèi)的C表示有可能另有旅行者C同行，省略號(hào)部分表示此部分兩個(gè)方案相同。但我們發(fā)現(xiàn)這個(gè)移動(dòng)所花費(fèi)的時(shí)間一定要比原來(lái)的少：第n步修改后的方案就已經(jīng)要比原方案耗時(shí)少，而第n+i步中，如果c比a和b都大的話(huà)，修改后的方案和原方案耗時(shí)相同；否則的話(huà)修改后的方案照樣比原方案耗時(shí)少。所以我們得到了一個(gè)比“最佳方案”還要“佳”的方案，所以這種情況其實(shí)是不會(huì)發(fā)生的。

　　現(xiàn)在我們得到了一個(gè)修改過(guò)的方案，它仍舊是個(gè)最佳方案。雖然我們并不能保證它是滿(mǎn)足結(jié)論三的方案，但是這并不是關(guān)鍵——關(guān)鍵在于它一直到第n步還是滿(mǎn)足結(jié)論三的要求，這就和我們開(kāi)始的假設(shè)，即被選取的這個(gè)方案是“這樣的步驟最晚出現(xiàn)的方案”矛盾。所以我們的原先“假設(shè)在所有滿(mǎn)足結(jié)論二的最佳方案中，都沒(méi)有符合結(jié)論三的方案”是錯(cuò)誤的。這樣我們就得到了結(jié)論三。

　　在這里我要插一句題外話(huà)。上面的推理方法在數(shù)學(xué)中被稱(chēng)為“變分方法”，這是最重要的數(shù)學(xué)方法中的一種，我們可以在所有的數(shù)學(xué)分支中看見(jiàn)它的應(yīng)用。它一般被用來(lái)證明存在一個(gè)具有某種特點(diǎn)的對(duì)象。首先我們選取一個(gè)使得某個(gè)特征（或者函數(shù)）達(dá)到最大或者最小的對(duì)象，然后用反證法證明這樣的對(duì)象就是我們要找的對(duì)象：我們假設(shè)如果它不是我們要找的對(duì)象，那么我們總是還能把這個(gè)對(duì)象修改，使得這個(gè)特征（或者函數(shù)）更大或更小，這就和原來(lái)最大或最小的假設(shè)矛盾。

　　下面我們會(huì)不斷地用到這種方法來(lái)得出許多結(jié)論：一定存在某一個(gè)最佳解法，符合如此這般的性質(zhì)。一旦我們知道有一個(gè)最佳解法滿(mǎn)足一些非常具體的性質(zhì)以后，這個(gè)解法也就很容易被具體寫(xiě)出來(lái)了。

　　根據(jù)結(jié)論三我們立刻推出

結(jié)論四：一定有這樣一種符合結(jié)論二—三的最佳方案，在這個(gè)方案里，每當(dāng)出現(xiàn)手電筒在此岸的局面時(shí)，速度最快的那個(gè)人總是在此岸。

　　如果是初始局面，所有人都在此岸，當(dāng)然沒(méi)什么好說(shuō)的。如果是手電筒在此岸的中間局面，那么根據(jù)結(jié)論三，前一步有一個(gè)彼岸最快的人剛過(guò)來(lái)。如果這個(gè)人不是所有人中最快的，那么說(shuō)明最快的原來(lái)就已經(jīng)在此岸了；如果這個(gè)人是所有人中最快的，那么他剛剛過(guò)來(lái)，現(xiàn)在也已經(jīng)在此岸了。所以結(jié)論四成立。

　　如果在符合結(jié)論四的最佳方案方案中，有一步是只有一個(gè)人B從此岸走到彼岸，我們會(huì)有什么推論？如果在此岸另有一個(gè)A，他的速度比B快，那么A完全可以跟著B(niǎo)一起到彼岸去，這樣就在耗費(fèi)相同時(shí)間的情況下，得到了一個(gè)優(yōu)于原先局面的局面，根據(jù)結(jié)論一，這也是最佳方案；如果B是此岸最快的，根據(jù)結(jié)論四，他也是所有人中最快的，過(guò)到彼岸后，根據(jù)結(jié)論三，他馬上一個(gè)人又要回來(lái)，這就使這兩步移動(dòng)毫無(wú)意義，徒費(fèi)時(shí)間。所以我們得到：

結(jié)論五：一定有這樣一種符合結(jié)論二—四的最佳方案，在這個(gè)方案里，所有從此岸到彼岸的移動(dòng)都需兩個(gè)人。

　　下面我們要給出一個(gè)不那么顯然的結(jié)論。

結(jié)論六：一定有這樣一種符合結(jié)論二—五的最佳方案，在這個(gè)方案里，每次從此岸到彼岸移動(dòng)兩人，要么這兩人里有一個(gè)是所有人中最快的那個(gè)，要么這兩人到達(dá)彼岸后都再也不回來(lái)。

　　上面這個(gè)結(jié)論的意思是，在這個(gè)方案里不會(huì)出現(xiàn)這樣的情況：有一步兩個(gè)人跑到彼岸去，但兩人都不是跑得最快的，但是后來(lái)其中一個(gè)（或者兩個(gè)都）又跑回此岸來(lái)。

　　仍舊使用變分法。假設(shè)在所有滿(mǎn)足結(jié)論二—五的最佳方案中，都沒(méi)有符合結(jié)論六的方案，也就是說(shuō)，其中的每個(gè)最佳方案，總都有某一步從此岸到彼岸的移動(dòng)中，被移動(dòng)的那兩個(gè)人沒(méi)有一個(gè)是最快的，而且其中一個(gè)在后面的步驟中又回到此岸來(lái)。那么我們?cè)谶@些最佳方案中選取一個(gè)這樣的步驟最晚出現(xiàn)的方案。假設(shè)這個(gè)步驟首先出現(xiàn)在第n步。

　　我們假設(shè)在這第n步中過(guò)去的兩個(gè)人是Y和Z，他們過(guò)橋所需時(shí)間分別是y和z分鐘，而在后面的第n+i步中，Y又回到此岸來(lái)了。設(shè)A是走得最快的那個(gè)人，過(guò)橋所需時(shí)間為a分鐘。由結(jié)論四知道，他當(dāng)時(shí)一定同Y和Z一起在此岸。

　　現(xiàn)在我們開(kāi)始修改這個(gè)方案，把第n步“讓Y和Z過(guò)去”改為“讓A和Z過(guò)去”：

　　　　　　　　原來(lái)的方案　　　　　　　修改后的方案
　　　　　　　　　……　　　　　　　　　　　……
　　　第n步：　　Y Z →　　　　　　　　　　A Z →

如果y＜z，那么改過(guò)的步驟消耗的時(shí)間和原來(lái)的一樣；如果z＜y，那么修改后的步驟消耗的時(shí)間還會(huì)更少?，F(xiàn)在兩種局面的唯一區(qū)別在于，前一種是A在此岸Y在彼岸，而后一種恰好相反。而且我們看到，經(jīng)過(guò)這樣修改的第n步現(xiàn)在符合“兩人里有一個(gè)是所有人中最快的那個(gè)”這個(gè)結(jié)論六中的要求。剩下的工作就是要理順后面的步驟，使得修改過(guò)的方案仍舊是一個(gè)最佳方案，那時(shí)我們就用變分法推出了矛盾，從而證明結(jié)論六。

　　下面我們的技巧和前面所用過(guò)的略微不同，我們要修改的不是一個(gè)移動(dòng)而是一串移動(dòng)。

　　假設(shè)原來(lái)的第n+1步是“讓Y₁回來(lái)”，其中Y₁是在彼岸的某人，他是在彼岸最快的。我們把這第n+1步改為“讓A回來(lái)”：

　　　　　　　　原來(lái)的方案　　　　　　　修改后的方案
　　　　　　　　　……　　　　　　　　　　　……
　　　第n步：　　Y Z →　　　　　　　　　　A Z →
　　第n+1步：　　 Y₁ ←　　　　　　　　　　　A ←

這樣修改后的步驟消耗的時(shí)間少于原先方案，因?yàn)閅₁必定跑得比A慢。如果Y₁恰好就是Y自己（也就是說(shuō)i=1），那么從這步以后修改前后兩種情況的局面又恢復(fù)成一樣了。如果i≠1，也就是說(shuō)Y₁和Y不同，那么執(zhí)行第n+1步后，原先的局面和修改過(guò)后的局面的唯一差別在于前一種是Y₁在此岸Y在彼岸，而后一種恰好相反。我們注意到，根據(jù)結(jié)論三，Y₁一定走得比Y快，更一般地，任何一個(gè)在n+1步到n+i步之間從彼岸回此岸來(lái)的人都比Y要走得快。

　　如果原先方案中從n+2步一直到n+i步里的移動(dòng)都不牽涉到Y(jié)₁，那么我們只要把第n+i步的“Y回來(lái)”改成“Y₁回來(lái)”，就理順了所有的步驟：

　　　　　　　　原來(lái)的方案　　　　　　　修改后的方案
　　　　　　　　　……　　　　　　　　　　　……
　　　第n步：　　Y Z →　　　　　　　　　　A Z →
　　第n+1步：　　 Y₁ ←　　　　　　　　　　　A ←
　　　　　　　　　……　　　　　　　　　　　……
第n+i步：　　 Y ←　　　　　　　　　　　Y₁ ←

修改后的步驟消耗的時(shí)間少于原先所需的，因?yàn)閅₁走得比Y快。

　　如果不幸地在原先方案中的第n+j步(j＜i)Y₁又要和某個(gè)人M一起到彼岸去，而第n+j+1步是“Y₂回此岸來(lái)”，那么我們把第n+j步改為“A和M一起到彼岸”去，而把第n+k+1步改為“A回此岸來(lái)”：

　　　　　　　　原來(lái)的方案　　　　　　　修改后的方案
　　　　　　　　　……　　　　　　　　　　　……
　　　第n步：　　Y Z →　　　　　　　　　　A Z →
　　第n+1步：　　 Y₁ ←　　　　　　　　　　　A ←
　　　　　　　　　……　　　　　　　　　　　……
　　第n+j步：　 Y₁ M →　　　　　　　　　　A M →
　第n+j+1步：　　 Y₂ ←　　　　　　　　　　　A ←

這樣修改后的步驟消耗的時(shí)間也要比原先的少，因?yàn)锳是最快的。如果Y₂恰好就是Y自己（也就是說(shuō)m=k+1），那么從這步以后修改前后兩種情況的局面就恢復(fù)成一樣了。如果m≠k+1，也就是說(shuō)Y₂和Y不同，那么執(zhí)行第n+k+1步后，原先的局面和修改過(guò)后的局面的唯一差別在于前一種是Y₂在此岸Y在彼岸，而后一種恰好相反。

　　這樣我們有一個(gè)序列Y₁，Y₂，……，依次修改下去，每次修改后的步驟消耗的時(shí)間不會(huì)多于原先所需的，經(jīng)過(guò)最多[m/2]次修改，總會(huì)有一刻某個(gè)Y_t和Y相同，結(jié)束我們的這串修改。

　　這樣我們就得到了修改后的最佳方案，它的第n步也是符合結(jié)論六的要求的。所以和我們的反證假設(shè)矛盾，和結(jié)論三的證明方式相同，我們證明了結(jié)論六。

　　在本節(jié)的結(jié)尾我們給出一個(gè)不那么顯然的結(jié)論三的加強(qiáng)版。

結(jié)論七：一定有這樣一種符合結(jié)論二—六的最佳方案，在這個(gè)方案里，所有從彼岸到此岸的移動(dòng)中，回來(lái)的這個(gè)人一定是當(dāng)時(shí)在彼岸所有人中速度最快的，而且他只能是所有人中最快的或者次快的。

　　換句話(huà)說(shuō)，所有返回此岸的任務(wù)都可以只由跑得最快和跑得次快的人來(lái)?yè)?dān)當(dāng)，所有其他人一旦到達(dá)彼岸，就留在那里，再也不回來(lái)。

　　我們還是使用變分法。假設(shè)結(jié)論七是錯(cuò)的，所有（滿(mǎn)足結(jié)論二—六的）最佳方案中，都必須至少有一次需要一個(gè)跑得不是最快或次快的人回來(lái)，那么我們選取一個(gè)這樣的事情發(fā)生得最晚的最佳方案。假設(shè)在第n步，有一個(gè)C從彼岸跑回了此岸，但他不是跑得最快或次快的人。

　　我們假設(shè)A是跑得最快的人，他所需過(guò)橋時(shí)間為a分鐘，B是跑得次快的人，他需要b分鐘，而C需要c分鐘。我們有a＜b＜c。因?yàn)樵诘趎步C從彼岸跑回了此岸，所以在那之前一定有一步，C從此岸到達(dá)彼岸，而且根據(jù)結(jié)論六，那一步一定是A和C同行，我們假設(shè)此步為第n-i步。又根據(jù)結(jié)論三，接下去一步是A回到此岸。在第n-i步和第n步間，沒(méi)有有關(guān)于C的移動(dòng)。考慮第n-1步：根據(jù)結(jié)論五，這一步必定有兩人從此岸移動(dòng)到彼岸；這兩人中沒(méi)有A或B，否則根據(jù)結(jié)論三，第n步回此岸來(lái)的就該是比較快的A或B；另外這兩人中也沒(méi)有C，因?yàn)樵谠诘趎-i步和第n步間，C不移動(dòng)。所以我們根據(jù)上面的分析可以寫(xiě)出方案中的有關(guān)步驟： 　　　　　　　　　原來(lái)的方案
　　　　　　　　　　……
　　第n-i步：　　　A C →
　第n-i+1步：　　　　A ←
　　　　　　　　　　……
　　第n-1步：　　　Y Z →　（Y和Z未知，但非A、B或C）
　　　第n步：　　　　C ←
　　　　　　　　　　……

因?yàn)榈趎-i步和第n步之間沒(méi)有關(guān)于C的移動(dòng)，而第n-1步時(shí)A和B一定在此岸（否則根據(jù)結(jié)論三，第n步回此岸來(lái)的就該是比較快的A或B），所以我們可以把第n-i步和第n-i+1步移到第n-1步前，方案仍舊可以合理進(jìn)行（換句話(huà)說(shuō)，第n-i和第n-i+1步的唯一作用就是把C運(yùn)送到了彼岸，但是直到第n步之前這個(gè)C并不起什么作用，所以我們可以把這次運(yùn)送搬到第n-1步前而不影響其他步驟）：

　　　　　　　　修改后的方案
　　　　　　　　　　……　（原來(lái)第n-i步前的步驟）
　　　　　　　　　　……?。ㄔ瓉?lái)處于第n-i+1和第n步間的步驟）
　　第n-3步：　　　A C →　（原來(lái)第n-i步）
　　第n-2步：　　　　A ←?。ㄔ瓉?lái)第n-i+1步）
　　第n-1步：　　　Y Z →?。╕和Z未知，但非A、B或C）
　　　第n步：　　　　C ←
　　　　　　　　　　……

現(xiàn)在有問(wèn)題的步驟都聚在了一起，所以我們可以用B來(lái)代替C，進(jìn)一步修改方案：

　　　　　　　進(jìn)一步修改后的方案
　　　　　　　　　　……?。ㄔ瓉?lái)第n-i步前的步驟）
　　　　　　　　　　……　（原來(lái)處于第n-i+1和第n步間的步驟）
　　第n-3步：　　　A B →　
　　第n-2步：　　　　A ←　
　　第n-1步：　　　Y Z →?。╕和Z未知，但非A、B或C）
　　　第n步：　　　　B ←　　　　　　　　　　……

這個(gè)修改是可行的，因?yàn)楦鶕?jù)上面的分析，進(jìn)行第n-3步前B在此岸。這樣得到的方案不但直到第n步還符合結(jié)論七，而且所需要的時(shí)間也比原方案短，明顯違反了假設(shè)，所以我們得到矛盾，也就是說(shuō)，滿(mǎn)足結(jié)論七的最佳方案是存在的。于是結(jié)論七成立。
　這說(shuō)明“優(yōu)于”這個(gè)詞的使用是合理的。

　　結(jié)論七是非常強(qiáng)大的，事實(shí)上它描述了除了最快和次快以外所有其他旅行者的過(guò)橋模式。任取一個(gè)滿(mǎn)足結(jié)論七的最佳方案。

　　假設(shè)A為最快，B為次快，而Z是任意一個(gè)其他旅行者。根據(jù)結(jié)論七，他只過(guò)一次橋，然后就留在彼岸再不回來(lái)?？紤]一下和他同行的另一位旅行者，這里有兩種可能性：

1) 另一位旅行者還會(huì)回到此岸來(lái)。

那么根據(jù)結(jié)論六，另一位一定是A。所以Z過(guò)河的模式是這樣的；

　　　　　　　　　　……
　　　　　　　　　A Z →
　　　　　　　　　　A ←
　　　　　　　　　　……

也就是“由A護(hù)送到對(duì)岸，A返回”，稱(chēng)作“模式一”。

2) 另一位旅行者也不回來(lái)了。假設(shè)這兩位旅行者過(guò)橋是在第n步。

　　如果方案一共就是到第n步結(jié)束，那么根據(jù)結(jié)論四，在未執(zhí)行第n步時(shí)，A應(yīng)該在此岸，而在執(zhí)行完第n步時(shí)，所有人都到了彼岸，所以那另一個(gè)旅行者就是A。所以如果出現(xiàn)這種情況，Z過(guò)橋的模式實(shí)質(zhì)上和1)中相同，“由A護(hù)送到對(duì)岸”，只不過(guò)A不用再返回而已。

　　如果方案中還有第n+1步，我們考慮一下第n+1步是什么。根據(jù)結(jié)論七，這步應(yīng)該是A或者B回到此岸。但是根據(jù)結(jié)論四，我們知道在第n步時(shí)A在此岸，所以第n+1不步可能是A回來(lái)，所以只能是B回來(lái)。但是B在彼岸說(shuō)明第n步前已經(jīng)有一步使得B過(guò)了橋。根據(jù)結(jié)論六和結(jié)論三，那一步一定是A和B同行，然后A回來(lái)。我們就可以寫(xiě)出Z的過(guò)橋模式（設(shè)另一位旅行者是Y，他必不同于A和B）：

　　　　　　　　　　……
　　　　　　　　　 A B →
　　　　　　　　　　 A ←
　　　　　　　　　　……
　　　第n步：　　　Y Z →
　　第n+1步：　　　　B ←
　　　　　　　　　　……

同結(jié)論七中的證明一樣，我們可以修改這個(gè)方案為

　　　　　　　　　　……
　　　　　　　　　　……
　　第n-2步：　　　A B →　
　　第n-1步：　　　　A ←　
　　　第n步：　　　Y Z →
　　第n+1步：　　　　B ←
　　　　　　　　　　……

看了這個(gè)方案片斷大家也許會(huì)有似曾相識(shí)的感覺(jué)。事實(shí)上，這就是本文開(kāi)始四位旅行者問(wèn)題中需時(shí)5分鐘和8分鐘的旅行者過(guò)橋的模式。這個(gè)模式是“由A和B護(hù)送到對(duì)岸，A和B返回”，稱(chēng)作“模式二”。

結(jié)論八：一定有這樣一種符合結(jié)論二—七的最佳方案，在這個(gè)方案里，所有除了最快和次快的旅行者都以上面兩個(gè)模式過(guò)橋，并且再不回來(lái)。 六、最慢兩人的過(guò)橋方式