|
海盜分金問題 Description:
傳說，從前有五個海盜搶得了100枚金幣.他們通過了一個如何確定選用誰的分配方案的安排.即：
1.抽簽決定各人的號碼（1，2，3，4，5）；
2.先由1號提出分配方案，然后5個人表決.當(dāng)且僅當(dāng)超過半數(shù)人同意時(shí)，方案才算被通過，否則他將被扔入大海喂鯊魚；
3.當(dāng)1號死后，再由2號提方案，4個人表決，當(dāng)且僅當(dāng)超過半數(shù)同意時(shí)，方案才算通過，否則2號同樣將被扔入大海喂鯊魚；
4.往下依次類推……
根據(jù)上面的這個故事，現(xiàn)在提出如下的一個問題.即：
我們假定每個海盜都是很聰明的人，并且都能夠很理智地判斷自己的得失，從而做出最佳的選擇，那么第一個海盜應(yīng)當(dāng)提出怎樣的分配方案才能夠使自己不被扔入大海喂鯊魚，而且收益還能達(dá)到最大化呢？
Solution:
倒推，從后往前推，人數(shù)依次增加
如果１－３號強(qiáng)盜都喂了鯊魚，只剩４號和５號的話，５號一定投反對票讓４號喂鯊魚，以獨(dú)吞全部金幣。所以，４號惟有支持３號才能保命。３號知道這一點(diǎn)，就會提（１００，０，０）的分配方案，對４號、５號一毛不拔而將全部金幣歸為已有，因?yàn)樗溃刺栆粺o所獲但還是會投贊成票，再加上自己一票，他的方案即可通過。
２號推知到３號的方案，就會提出（９８，０，１，１）的方案，即放棄３號，而給予４號和５號各一枚金幣。由于該方案對于４號和５號來說比在３號分配時(shí)更為有利，他們將支持他而不希望他出局而由３號來分配。這樣，２號將拿走９８枚金幣。
２號的方案會被１號所洞悉，１號并將提出（９７，０，１，２，０）或（９７，０，１，０，２）的方案，即放棄２號，而給３號一枚金幣，同時(shí)給４號（或５號）２枚金幣。由于１號的這一方案對于３號和４號（或５號）來說，相比２號分配時(shí)更優(yōu)，他們將投１號的贊成票，再加上１號自己的票，１號的方案可獲通過，９７枚金幣可輕松落入囊中。這無疑是１號能夠獲取最大收益的方案了！
帽子/瘋狗問題
Description:
一群人開舞會，每人頭上都戴著一頂帽子。帽子只有黑白兩種，黑的至少有一頂。每個人都能看到其他人帽子的顏色，卻不知自己的。主持人先讓大家看看別人頭上戴的什么帽子，然后關(guān)燈，如果有人認(rèn)為自己戴的是黑帽子，就打自己一個耳光。第一次關(guān)燈，沒有聲音。于是再開燈，大家再看一遍，關(guān)燈時(shí)仍然鴉雀無聲。一直到第三次關(guān)燈，才有劈劈啪啪打耳光的聲音響起。問有多少人戴著黑帽子？
Solution:
遞推歸納
假如只有一個人戴黑帽子，那他看到所有人都戴白帽，在第一次關(guān)燈時(shí)就應(yīng)自打耳光，所以應(yīng)該不止一個人戴黑帽子；如果有兩頂黑帽子，第一次兩人都只看到對方頭上的黑帽子，不敢確定自己的顏色，但到第二次關(guān)燈，這兩人應(yīng)該明白，如果自己戴著白帽，那對方早在上一次就應(yīng)打耳光了，因此自己戴的也是黑帽子――― 于是也會有耳光響起；可事實(shí)是第三次才響起耳光聲，說明全場不止兩頂黑帽，依此類推，應(yīng)該是關(guān)幾次燈，有幾頂黑帽。
稱球問題
Description:
一共12 個一樣的小球， 其中只有一個重量與其它不一樣( 未知輕重) ，給你一個天平， 只稱三次， 找出那個不同重量的球？
如果一共13 個一樣的小球， 其中只有一個重量與其它不一樣( 未知輕重) ，給你一個天平， 只稱三次， 找出那個不同重量的球？
Solution:
充分利用所有信息
12個情形:將球編號1~12，分為1-4,5-8,9-12三堆
左1-4－右5-8
若平衡，壞球在9-12,左1-3－右9-11
若不平衡且5-8重，壞球1-8
左1,6,7,8－右5,9,10,11
右重->壞球是1或5
平衡->壞球?yàn)?-4且比標(biāo)準(zhǔn)球輕
左重->壞球在拿到左邊的6-8且比標(biāo)準(zhǔn)球重
三種情形：再稱一次得解
若不平衡且1-4重與上同理
13 個球情形：解法類似 , 分為三組,1-4,5-8,9-12
左1-4 －右5-8
不平衡情形與12 球同
平衡時(shí)左1-3 －右9-11
不平衡時(shí)與12 球同，平衡時(shí)壞球在12/13 ，左1 －右12
平衡，壞球13
不平衡, 壞球12
注意：題目只需要找出重量不同的球即可
分金條問題
Description:
你讓某些人為你工作了七天， 你要用一根金條作為報(bào)酬。這根金條要被分成七塊。你必須在每天的活干完后交給他們一塊。如果你只能將這根金條切割兩次，你怎樣給這些工人分？
Solution:
聯(lián)想：二進(jìn)制:1,2,4 其中若干個的和可構(gòu)成1,7 中任何一個數(shù)
1/7 ，2/7 ，4/7 ，第一天給1/7 ，第二天拿2/7 換1/7………………
猴子搬香蕉問題
Description:
一個小猴子邊上有100 根香蕉，它要走過50 米才能到家，每次它最多搬50 根香蕉，每走1 米就要吃掉一根，請問它最多能把多少根香蕉搬到家里。
Solution:
猜想＋驗(yàn)證
猜想：
設(shè)小猴從0 走到50, 到A 點(diǎn)時(shí)候他可以直接抱香蕉回家了, 可是到A 點(diǎn)時(shí)候他至少消耗了3A 的香蕉( 到A, 回0, 到A), 一個限制就是小猴只能抱50 只香蕉, 那么在A 點(diǎn)小猴最多49 只香蕉.100-3A=49, 所以A=17. 這樣折騰完到家的時(shí)候香蕉剩100-3A-(50-A)=50-2A=16.
驗(yàn)證:
以上為最優(yōu)情形，只需驗(yàn)證這種情形可以達(dá)到即可
飛機(jī)加油問題
Description:
每個飛機(jī)只有一個油箱， 飛機(jī)之間可以相互加油（注意是相互，沒有加油機(jī)） 一箱油可供一架飛機(jī)繞地球飛半圈。
為使至少一架飛機(jī)繞地球一圈回到起飛時(shí)的飛機(jī)場，至少需要出動幾架飛機(jī)？（所有飛機(jī)從同一機(jī)場起飛，而且必須安全返回機(jī)場，不允許中途降落，中間沒有飛機(jī)場）
Solution:
猜想+驗(yàn)證
猜想：
至少需要出動5 架飛機(jī)。思路是這樣的，一架飛機(jī)要想完成繞地球一周的飛行，至少需要別的飛機(jī)給它提供1 箱油。最劃算的辦法顯然是，派飛機(jī)和它結(jié)伴飛行前四分之一周以及后四分之一周，（因?yàn)檫@兩段路程距離基地近所花代價(jià)小。）由它獨(dú)立飛行中間的半程。必須保證兩個加油點(diǎn)，前四分之一處，加滿，后四分之一點(diǎn)，及時(shí)補(bǔ)充。那么必須有兩架飛機(jī)與目標(biāo)機(jī)結(jié)伴飛行四分之一周，這兩架飛機(jī)需要做折返飛行，正好花費(fèi)2 箱油。所以補(bǔ)充油的任務(wù)實(shí)際上該由另外兩架飛機(jī)完成。這兩架飛機(jī)飛八分之一周，做折返飛，正好富余1 箱油。因此，5 架飛機(jī)剛好完成任務(wù)。到了此時(shí)，問題只考慮了一半。能夠提供多少油并不意味著就能夠全部接受，受到結(jié)伴飛行的距離，即騰出的油箱空間所限制。而以下做法正好可以滿足此條件。
驗(yàn)證:
3 架飛機(jī)同時(shí)從機(jī)場出發(fā)，飛行八分之一周，各耗油四分之一。此時(shí)某架飛機(jī)給其余兩架補(bǔ)滿油，自己返回基地。另一機(jī)和目標(biāo)機(jī)結(jié)伴，飛至四分之一周，給目標(biāo)機(jī)補(bǔ)滿油，自己返回。目標(biāo)機(jī)獨(dú)自飛行半周，與從基地反向出發(fā)的一機(jī)相遇，2 機(jī)將油平分，飛至最后八分之一處，與從基地反向出發(fā)的另一機(jī)相遇，各分四分之一油，返回。
硬幣游戲
Description:
16 個硬幣，A 和B 輪流拿走一些，每次拿走的個數(shù)只能是1 ，2 ，4 中的一個數(shù)。
誰最后拿硬幣誰輸。
問：A 或B 有無策略保證自己贏？
博弈類問題，分清兩概念
必勝態(tài)：有一種方法導(dǎo)致下一狀態(tài)為必?cái)B(tài)
必?cái)B(tài)：每一種方法導(dǎo)致下一狀態(tài)為必勝態(tài)
解決辦法：遞推
1: 必?cái)?
2: 必勝：取1 ，導(dǎo)致變?yōu)? 狀態(tài)( 必?cái)?
3: 必勝：取2-> 必?cái)B(tài)
4: 必?cái)。喝? 或2 或4 均導(dǎo)致必?cái)B(tài)或直接失敗
以些類推知16 為必?cái)B(tài)，即后手必勝
剩2 個時(shí), 取1 個必勝;
剩3 個時(shí), 取2 個必勝;
剩4 個時(shí), 如果對手足夠聰明則必?cái)?
剩5 個時(shí), 去1 個必勝...
記作 2(1) 3(2) 4(x) 5(1) 6(2) 7(x) 8(1) ...
從中找出規(guī)律:
當(dāng)剩余個數(shù)K=3N-2,N 為自然數(shù)時(shí), 只要對手足夠聰明則必?cái)?
當(dāng)K=3N-1 時(shí), 有必勝策略: 取1 個;
當(dāng)K=3N 時(shí), 有必勝策略: 取2 個;
所以, 當(dāng)16 個時(shí), 后取者有必勝策略.
倒水問題
經(jīng)典形式：
“ 假設(shè)有一個池塘，里面有無窮多的水。現(xiàn)有2 個空水壺，容積分別為
5 升和6 升。問題是如何只用這2 個水壺從池塘里取得3 升的水。”
Solution:
形式化倒水問題：無窮多水，容量a,b(a<=b) 的水壺倒出c(c<=b) 升水。
結(jié)論：c%***(a,b) == 0 時(shí)有解，可用擴(kuò)展的Euclid 定理加以證明：即存在整數(shù)x,y ，使得ax+by=***(a,b).
通用解法:( 容量A,B 的水壺倒C 升水)
int t = 0;
while(t != c){
Do(fill A),Do(pour A B);
t = t+A;
if(t >= B){
t = t – B;
Do(empty B), Do(pour A B);
}
}
本題解答(5,6->3)
Oper a b t (A=5,B=6)
Fill A, Pour A B 0 5 5
Fill A, Pour A B 4 6 10
Empty B, Pour A B 0 4 4
Fill A, Pour A B 3 6 9
Empty B, Pour A B 0 3 3 (success)
倒水問題推廣
也可以說是倒酒：）有三個酒杯，其中兩個大酒杯每個可以裝8兩酒，一個可以裝3兩酒。現(xiàn)在兩個大酒杯都裝滿了酒，只用這三個杯子怎么把酒平均的分給4個人喝？
Solution:
Try and guess
用一個三位數(shù)表示三個杯，880 ，前兩個為8 升的杯最后一個3 升。開始：880_853A 喝掉3 升變?yōu)椋?50_823_B 喝掉2 升為：803_830_533_560_263_281A 喝掉1 升(A 已經(jīng)喝4 升完畢）為：280_253_550_523_820_802_703_730_433_460_163_181CD 各喝一升為：080_053_350_323CD 各喝3 升B 喝2 升，分水結(jié)束，ABCD 四人各喝4 升。
帽子問題 Description:
有一個牢房，有3個犯人關(guān)在其中。因?yàn)椴ＡШ芎瘢?個人只能互相看見，不能聽到對方說話的聲音。”
有一天，國王想了一個辦法，給他們每個人頭上都戴了一頂帽子，只叫他們知道帽子的顏色不是白的就是黑的，不叫他們知道自己所戴帽子的是什么顏色的。在這種情況下，國王宣布兩條如下：
1．誰能看到其他兩個犯人戴的都是白帽子，就可以釋放誰；
2．誰知道自己戴的是黑帽子，就釋放誰。
其實(shí)，國王給他們戴的都是黑帽子。他們因?yàn)楸唤墸床灰娮约毫T了。于是他們3個人互相盯著不說話。可是不久，心眼靈的A用推理的方法，認(rèn)定自己戴的是黑帽子。您想，他是怎樣推斷的?
Solution:
邏輯學(xué)，假設(shè)思維
現(xiàn)在假設(shè)3個犯人是A、B和我
那么我的推斷是：
第一種：我戴的是白帽子
那么A會這么想：如果自己戴的是白帽子，那么B就會看到2個白帽子，那么他根據(jù)國王的第一條就馬上會被釋放，但是B現(xiàn)在沒有被釋放，說明我戴的不是白的，是黑的，哈哈，我知道自己是黑的拉，我可以要求國王釋放我拉
結(jié)論：如果我戴的是白帽子，那么根據(jù)A犯人的想法得出：A和B必然有一個會被釋放，但是現(xiàn)在2個人都沒有被釋放，所以我一定不是白的，而是黑的，所以我會知道自己是黑的，要求國王釋放我，這樣，我就被放了
同理，A和B根據(jù)別人的想法也都算出自己是黑帽子，這樣3個犯人同時(shí)被釋放
年齡問題
Description:
一普查員問一女人,“ 你有多少個孩子, 他們多少歲?” 女人回答:“ 我有三個孩子, 他們的歲數(shù)相乘是36, 歲數(shù)相加就等於隔離間屋的門牌號碼.” 普查員立刻走到隔鄰, 看了一看, 回來說:” 我還需要多少資料.” 女人回答:“ 我現(xiàn)在很忙, 我最大的孩子正在樓上睡覺.” 普查員說:” 謝謝, 我己知道了
問題: 那三個孩子的歲數(shù)是多少。
Solution:
9，2，2
分析，設(shè)三個人的年齡組成自然數(shù)組合(x,y,z)，一共三個條件，
條件一：三個人歲數(shù)乘起來為36；選出滿足x*y*z=36的組合;
條件二：知道三個人歲數(shù)之和后還是不能確定它們的年齡；從上面的到的組合中找出xyz之和有相同的組合；
只有 (9,2,2)=13,(6,6,1)=13
條件三：三個孩子中有一個年齡比其他兩個大。符合條件的組合只有(9，2，2)
 |