沒有盡頭的任務

前言

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

內(nèi)容概要

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

書籍目錄

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

章節(jié)摘錄

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

編輯推薦

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

圖書封面

圖書標簽Tags

無

評論、評分、閱讀與下載

---

    沒有盡頭的任務 PDF格式下載

---