沒(méi)有盡頭的任務(wù)

前言

　　我的最大樂(lè)趣之一是為《科學(xué)美國(guó)人》雜志撰寫專欄文章，這幾乎成了我的專利，從1956年12月有關(guān)六邊形折紙的一篇文章開(kāi)始，直到1986年5月刊出的最小斯坦納樹(shù)，長(zhǎng)達(dá)30年之久?！　?duì)我來(lái)說(shuō)，撰寫這一專欄是個(gè)了不起的學(xué)習(xí)過(guò)程。我畢業(yè)于芝加哥大學(xué)，主攻哲學(xué)，并沒(méi)有讀過(guò)數(shù)學(xué)專業(yè)，但我一貫熱愛(ài)數(shù)學(xué)，當(dāng)時(shí)沒(méi)有把它作為專業(yè)，時(shí)常后悔不已。讀者只要對(duì)這個(gè)專欄早期刊出的文章粗略地瞥上一眼，就不難看出，隨著我的數(shù)學(xué)知識(shí)不斷長(zhǎng)進(jìn)，后期的文章顯得更加成熟得多。令我更難忘懷的是因此而認(rèn)識(shí)了許多真正杰出的數(shù)學(xué)家，他們慷慨無(wú)私地提供了寶貴資料，成為我的終生至交?！　”緯?shū)是第15本，也是最后一本集子。同這系列的其他各本書(shū)一樣，我已盡了最大努力去改正錯(cuò)誤，擴(kuò)展知識(shí)，在本書(shū)結(jié)尾處增添補(bǔ)充材料，追加插圖，力求跟上時(shí)代步伐，并提供更詳盡而充實(shí)的、經(jīng)過(guò)鄭重選擇的參考文獻(xiàn)?！　●R丁·加德納

內(nèi)容概要

有3位傳教士與3個(gè)食人者在河的右岸，打算利用一只小劃子擺渡到左岸去。劃子很小，一次至多只能搭載2個(gè)人。食人者毫無(wú)人性，不論在左岸還是右岸，只要人數(shù)占優(yōu)(多出一人就行)，傳教士就會(huì)被他們殺死吃掉。
所有人都能安然渡河嗎?如果能，試問(wèn)最少要渡幾次？ 《沒(méi)有盡頭的任務(wù)》一書(shū)為我們講解的就是此類趣味數(shù)學(xué)知識(shí)，主要供青少年閱讀。
《沒(méi)有盡頭的任務(wù)》由馬丁·加德納編寫。

書(shū)籍目錄

序言
第1章 平面宇宙的奇跡
第2章 保加利亞單人牌戲以及其他一些似乎沒(méi)有盡頭的任務(wù)
第3章 雞蛋趣話，第一部分
第4章 雞蛋趣話，第二部分
第5章 紐結(jié)的拓?fù)鋵W(xué)
第6章 帝國(guó)的地圖
第7章 有向圖與吃人者
第8章 晚宴客人，女中學(xué)生與戴手銬的囚犯
第9章 大魔群與其他散在單群
第10章 出租車幾何學(xué)
第11章 鴿巢的力量
進(jìn)階讀物

章節(jié)摘錄

　　假如你手頭有個(gè)籃子，裝著100只雞蛋，另外還有許許多多盛放雞蛋的紙板箱。你的任務(wù)是要把所有的雞蛋放進(jìn)紙板箱里。每一步（每一次動(dòng)作）或者是把一只雞蛋放進(jìn)紙板箱，或者是把一只雞蛋從紙板箱里拿出來(lái)重新放回籃子里。規(guī)則是：接連兩次把雞蛋放進(jìn)紙板箱之后，就必須從紙板箱里取出一只雞蛋，重新放回到籃子里。盡管這種方法效率極低，荒謬透頂，但顯然，最后所有的雞蛋都能裝進(jìn)紙板箱里去?！　‖F(xiàn)在假定籃子里可以盛放任意多個(gè)有限數(shù)的雞蛋。如果一開(kāi)始你要了許許多多雞蛋，那么完成這個(gè)任務(wù)就將變得十分艱巨。不過(guò)，最初的雞蛋數(shù)一旦確定下來(lái)，完成這個(gè)任務(wù)的所需步數(shù)也就有了一個(gè)有限數(shù)的確定上限。　　如果規(guī)則允許你在任何時(shí)候都可以把任意數(shù)目的雞蛋放回籃子里，情況就會(huì)發(fā)生根本的變化。這時(shí)，完成這一任務(wù)所需的步數(shù)就不再有一個(gè)上限，甚至開(kāi)始時(shí)籃子里只有兩個(gè)雞蛋，也是如此。所以，把有限數(shù)的雞蛋進(jìn)行裝箱的任務(wù)將會(huì)按照規(guī)則的不同，或必定可以完成，或沒(méi)完沒(méi)了。也可以由你選擇，使這個(gè)任務(wù)在有限步數(shù)內(nèi)完成，或無(wú)限地進(jìn)行下去。　　我們現(xiàn)在來(lái)考慮幾個(gè)有趣的數(shù)學(xué)游戲，它們有以下特點(diǎn)。從直觀上看，你似乎能夠把完成任務(wù)之日永遠(yuǎn)地拖延下去，但實(shí)際上在有限多步之后任務(wù)必然完成，這個(gè)結(jié)局無(wú)法避免。　　我們的第一個(gè)例子是從哲學(xué)家兼作家和邏輯學(xué)家斯穆?lián)P（Raymond M.Smu11yan）的一篇文章里找來(lái)的。設(shè)想你有無(wú)窮多個(gè)打落袋用的臺(tái)球，每個(gè)球上都標(biāo)有一個(gè)正整數(shù)，而且對(duì)于每一個(gè)正整數(shù)，都有無(wú)窮多個(gè)臺(tái)球以此數(shù)作其標(biāo)號(hào)。你還有一只箱子，其中盛有有限多個(gè)標(biāo)記著數(shù)字的臺(tái)球。你的目標(biāo)是要把箱子出空。每一步要求你從箱子里取出一只臺(tái)球，同時(shí)換上任意有限多只標(biāo)號(hào)比它小的臺(tái)球。1號(hào)臺(tái)球是唯一的例外，因?yàn)闆](méi)有比1更小的號(hào)碼，所以對(duì)每個(gè)1號(hào)臺(tái)球來(lái)說(shuō)，沒(méi)有臺(tái)球來(lái)替換它，只能是有出無(wú)人了?！　〔浑y用有限多步就把箱子出空。這只要把每個(gè)標(biāo)號(hào)比1大的臺(tái)球用一個(gè)1號(hào)臺(tái)球來(lái)替換，直到箱子里剩下來(lái)的全是1號(hào)臺(tái)球，然后再每次取出一個(gè)1號(hào)臺(tái)球就行了。不過(guò)，規(guī)則允許你用任意有限數(shù)目標(biāo)號(hào)較小的臺(tái)球來(lái)替換一個(gè)標(biāo)號(hào)大于1的臺(tái)球。譬如說(shuō)，你可以取出一個(gè)標(biāo)號(hào)為1000的臺(tái)球，而換上十億個(gè)標(biāo)號(hào)為999的臺(tái)球，再加上一百億個(gè)標(biāo)號(hào)為998的臺(tái)球，再加上一百億億個(gè)標(biāo)號(hào)為997的臺(tái)球，再加上……。這樣一來(lái)，箱子里臺(tái)球的總數(shù)在每一步都增加得超乎你的想象。試問(wèn)，你是否能夠永遠(yuǎn)拖延下去，使箱子不會(huì)出空呢？實(shí)際上，箱子終有出空之日，這個(gè)結(jié)局是無(wú)法避免的，盡管乍看起來(lái)這似乎令人難以置信?！　≌?qǐng)注意，比起雞蛋游戲來(lái)，出空箱子所需的步數(shù)要龐大得多，不僅是開(kāi)始時(shí)的臺(tái)球數(shù)沒(méi)有限制，而且每次取出一個(gè)標(biāo)號(hào)大于1的臺(tái)球之后，用來(lái)替換它的臺(tái)球的數(shù)目也沒(méi)有限制。借用康韋（John Horton Conway）的話來(lái)說(shuō)，這個(gè)過(guò)程乃是“無(wú)界的無(wú)界”。在此游戲的每一個(gè)階段，只要箱子里還有著一個(gè)標(biāo)號(hào)大于1的臺(tái)球，就不可能預(yù)見(jiàn)要把箱子里1號(hào)臺(tái)球之外的臺(tái)球全部取出究竟需要多少步。（如果所有臺(tái)球的標(biāo)號(hào)全都是1，出空箱子的步數(shù)當(dāng)然就和1號(hào)臺(tái)球的個(gè)數(shù)一樣多。）不過(guò)，無(wú)論你替換臺(tái)球的辦法多么高明，在經(jīng)歷了有限多步之后，箱子終究是會(huì)出空的。當(dāng)然，我們必須假設(shè)，盡管不一定要求你長(zhǎng)生不老，然而也需要你活得足夠長(zhǎng)來(lái)完成這項(xiàng)任務(wù)?！　∷鼓?lián)P將這個(gè)驚人結(jié)果發(fā)表在他的一篇論文《樹(shù)圖與臺(tái)球游戲》中，此文刊載于《紐約科學(xué)院年報(bào)》（第321卷，86—90頁(yè)，1979年）上，文中給出了好幾個(gè)證明，其中有一個(gè)是用歸納法來(lái)簡(jiǎn)單論證的。斯穆?lián)P的論述好得無(wú)以復(fù)加，我沒(méi)有本事改進(jìn)，還是照用他的原話為好：　　如果箱子里的臺(tái)球全是標(biāo)號(hào)1，那么顯然我們輸定了。假設(shè)箱子里臺(tái)球的標(biāo)號(hào)最大是2，那么，一開(kāi)始我們有著有限多個(gè)2號(hào)臺(tái)球和有限多個(gè)1號(hào)臺(tái)球。我們不可能一直老是把1號(hào)球扔出去，因而遲早我們總要把其中的一個(gè)2號(hào)球拿走。這樣一來(lái)，箱子里的2號(hào)球就少了一個(gè)（不過(guò)，箱子里卻可能包含比開(kāi)始時(shí)要多得多的1號(hào)臺(tái)球）?，F(xiàn)在，我們還是不能老是在把1號(hào)球扔出去，因此遲早我們總還是要扔出另一個(gè)2號(hào)球?？梢钥闯?，經(jīng)過(guò)有限多步之后，我們必然要扔出最后一只2號(hào)臺(tái)球，這時(shí)我們又回到了箱子里只有1號(hào)臺(tái)球的情形。我們已經(jīng)知道，這種情形肯定是要失敗的。這就證明了，當(dāng)臺(tái)球的最大標(biāo)號(hào)為2時(shí)，過(guò)程必將中止。那么，最大標(biāo)號(hào)為3時(shí)又如何呢？我們不能一直不斷地把標(biāo)號(hào)為2的球扔出去（我們剛剛證明了這一點(diǎn)），因此我們遲早總要扔出去一個(gè)3號(hào)球。所以，到頭來(lái)我們必定要扔出去最后一個(gè)3號(hào)球。這就把問(wèn)題歸結(jié)到上面的、最大標(biāo)號(hào)為2的情形，而這種情形我們已經(jīng)解決了?！　∷鼓?lián)P還用樹(shù)圖作為這個(gè)游戲的模型來(lái)證明它必定終止。所謂“樹(shù)”就是指一組線段，每條線段聯(lián)結(jié)兩個(gè)點(diǎn)，而且每一個(gè)點(diǎn)都通過(guò)唯一的一串線段聯(lián)結(jié)到某一點(diǎn)，該點(diǎn)稱為樹(shù)的根。臺(tái)球游戲的第一步（用臺(tái)球裝箱）可通過(guò)模型來(lái)刻畫：把每只球表示為一個(gè)點(diǎn)，點(diǎn)的號(hào)碼等同于球的號(hào)碼，再用一根線段通向樹(shù)根。當(dāng)一只球被許多只標(biāo)號(hào)較低的球替換時(shí)，球上的原有標(biāo)號(hào)將被抹去，而代之以號(hào)數(shù)較大的點(diǎn)，然后這些點(diǎn)都聯(lián)結(jié)到那個(gè)被移去的球所代表的點(diǎn)。就這樣，樹(shù)圖將會(huì)逐步地向上增長(zhǎng)，而其“端點(diǎn)”（不是“根”、而且只是用一根線段與別的點(diǎn)相聯(lián)結(jié)的點(diǎn)）就表示在該階段箱子里的臺(tái)球?！　　?/pre>




編輯推薦
　　《科學(xué)美國(guó)人趣味數(shù)學(xué)集錦：沒(méi)有盡頭的任務(wù)》一書(shū)從馬丁·加德納為《科學(xué)美國(guó)人》雜志撰寫的專欄文章中精選而成。這些文章均系趣味數(shù)學(xué)問(wèn)題，內(nèi)容涉及：平面宇宙的奇跡、保加利亞單人牌戲以及其他一些似乎沒(méi)有盡頭的任務(wù)、紐結(jié)的拓?fù)鋵W(xué)、有向圖與吃人者等。主要供青少年閱讀。





圖書(shū)封面



圖書(shū)標(biāo)簽Tags
無(wú)




評(píng)論、評(píng)分、閱讀與下載



還沒(méi)讀過(guò)(95)
勉強(qiáng)可看(691)
一般般(117)
內(nèi)容豐富(4889)
強(qiáng)力推薦(400)


 


    沒(méi)有盡頭的任務(wù) PDF格式下載