1樓：令黃蜂
第 31 68 14題
有2n個人排隊進電影院，票價是50美分。在這2n個人當中，其中n個人只有50美分，另外n個人有1美元（紙票子）。愚蠢的電影院開始賣票時1分錢也沒有。
問：有多少種排隊方法使得每當乙個擁有1美元買票時，電影院都有50美分找錢
注：1美元=100美分擁有1美元的人，擁有的是紙幣，沒法破成2個50美分
本題可用遞迴演算法，但時間複雜度為2的n次方，也可以用動態規劃法，時間複雜度為n的平方，實現起來相對要簡單得多，但最方便的就是直接運用公式：排隊的種數=(2n)!/[n!
(n+1)!]。
如果不考慮電影院能否找錢，那麼一共有(2n)!/[n!n!
]種排隊方法（即從2n個人中取出n個人的組合數），對於每一種排隊方法，如果他會導致電影院無法找錢，則稱為不合格的，這種的排隊方法有(2n)!/[(n-1)!(n+1)!
]（從2n個人中取出n-1個人的組合數）種，所以合格的排隊種數就是(2n)!/[n!n!
]- (2n)!/[(n-1)!(n+1)!
] =(2n)!/[n!(n+1)!
]。至於為什麼不合格數是(2n)!/[(n-1)!
(n+1)!]，說起來太複雜，這裡就不講了。
共有三類藥，分別重1g,2g,3g，放到若干個瓶子中，現在能確定每個瓶子中只有其中一種藥，且每瓶中的藥片足夠多，能只稱一次就知道各個瓶子中都是盛的哪類藥嗎？如果有4類藥呢？5類呢？
n類呢(n可數)？如果是共有m個瓶子盛著n類藥呢(m，n為正整數，藥的質量各不相同但各種藥的質量已知)？你能只稱一次就知道每瓶的藥是什麼嗎？
注：當然是有代價的，稱過的藥我們就不用了
第乙個瓶子拿出一片，第二個瓶子拿出四片，第三個拿出十六片，……第m個拿出n+1的m-1次方片。把所有這些藥片放在一起稱重量。
有3頂紅帽子，4頂黑帽子，5頂白帽子。讓10個人從矮到高站成一隊，給他們每個人頭上戴一頂帽子。每個人都看不見自己戴的帽子的顏色，卻只能看見站在前面那些人的帽子顏色。
（所以最後乙個人可以看見前面9個人頭上帽子的顏色，而最前面那個人誰的帽子都看不見。現在從最後那個人開始，問他是不是知道自己戴的帽子顏色，如果他回答說不知道，就繼續問他前面那個人。假設最前面那個人一定會知道自己戴的是黑帽子。
為什麼？
「有3頂黑帽子，2頂白帽子。讓三個人從前到後站成一排，給他們每個人頭上戴一頂帽子。每個人都看不見自己戴的帽子的顏色，卻只能看見站在前面那些人的帽子顏色。
（所以最後乙個人可以看見前面兩個人頭上帽子的顏色，中間那個人看得見前面那個人的帽子顏色但看不見在他後面那個人的帽子顏色，而最前面那個人誰的帽子都看不見。現在從最後那個人開始，問他是不是知道自己戴的帽子顏色，如果他回答說不知道，就繼續問他前面那個人。事實上他們三個戴的都是黑帽子，那麼最前面那個人一定會知道自己戴的是黑帽子。
為什麼？」
答案是，最前面的那個人聽見後面兩個人都說了「不知道」，他假設自己戴的是白帽子，於是中間那個人就看見他戴的白帽子。那麼中間那個人會作如下推理：「假設我戴了白帽子，那麼最後那個人就會看見前面兩頂白帽子，但總共只有兩頂白帽子，他就應該明白他自己戴的是黑帽子，現在他說不知道，就說明我戴了白帽子這個假定是錯的，所以我戴了黑帽子。
」問題是中間那人也說不知道，所以最前面那個人知道自己戴白帽子的假定是錯的，所以他推斷出自己戴了黑帽子。
我們把這個問題推廣成如下的形式：
「有若干種顏色的帽子，每種若干頂。假設有若干個人從前到後站成一排，給他們每個人頭上戴一頂帽子。每個人都看不見自己戴的帽子的顏色，而且每個人都看得見在他前面所有人頭上帽子的顏色，卻看不見在他後面任何人頭上帽子的顏色。
現在從最後那個人開始，
問他是不是知道自己戴的帽子顏色，如果他回答說不知道，就繼續問他前面那個人。一直往前問，那麼一定有乙個人知道自己所戴的帽子顏色。」
當然要假設一些條件：
1)首先，帽子的總數一定要大於人數，否則帽子都不夠戴。
2)「有若干種顏色的帽子，每種若干頂，有若干人」這個資訊是佇列中所有人都事先知道的，而且所有人都知道所有人都知道此事，所有人都知道所有人都知道所有人都知道此事，等等等等。但在這個條件中的「若干」不一定非要具體一一給出數字來。
這個資訊具體地可以是象上面經典的形式，列舉出每種顏色帽子的數目「有3頂黑帽子，2頂白帽子，3個人」，也可以是「有紅黃綠三種顏色的帽子各1頂2頂3 頂，但具體不知道哪種顏色是幾頂，有6個人」，甚至連具體人數也可以不知道，「有不知多少人排成一排，有黑白兩種帽子，每種帽子的數目都比人數少1」，這時候那個排在最後的人並不知道自己排在最後——直到開始問他時發現在他回答前沒有別人被問到，他才知道他在最後。在這個帖子接下去的部分當我出題的時候我將只寫出「有若干種顏色的帽子，每種若干頂，有若干人」這個預設條件，因為這部分確定了，題目也就確定了。
3)剩下的沒有戴在大家頭上的帽子當然都被藏起來了，隊伍裡的人誰都不知道都剩下些什麼帽子。
4)所有人都不是色盲，不但不是，而且只要兩種顏色不同，他們就能分別出來。當然他們的視力也很好，能看到前方任意遠的地方。他們極其聰明，邏輯推理是極好的。
總而言之，只要理論上根據邏輯推導得出來，他們就一定推導得出來。相反地如果他們推不出自己頭上帽子的顏色，任何人都不會試圖去猜或者作弊偷看—— 不知為不知。
5)後面的人不能和前面的人說悄悄話或者打暗號。
當然，不是所有的預設條件都能給出乙個合理的題目。比如有99頂黑帽子，99頂白帽子，2個人，無論怎麼戴，都不可能有人知道自己頭上帽子的顏色。另外，只要不是只有一種顏色的帽子，在只由乙個人組成的隊伍裡，這個人也是不可能說出自己帽子的顏色的。
但是下面這幾題是合理的題目：
1)3頂紅帽子，4頂黑帽子，5頂白帽子，10個人。
2)3頂紅帽子，4頂黑帽子，5頂白帽子，8個人。
3)n頂黑帽子，n-1頂白帽子，n個人（n>0）。
4)1頂顏色1的帽子，2頂顏色2的帽子，……，99頂顏色99的帽子，100頂顏色100的帽子，共5000個人。
5)有紅黃綠三種顏色的帽子各1頂2頂3頂，但具體不知道哪種顏色是幾頂，有6個人。
6)有不知多少人（至少兩人）排成一排，有黑白兩種帽子，每種帽子的數目都比人數少1。
大家可以先不看***的分析，試著做做這幾題。
如果按照上面3頂黑帽2頂白帽時的推理方法去做，那麼10個人就可以把我們累死，別說5000個人了。但是3)中的n是個抽象的數，考慮一下怎麼解決這個問題，對解決一般的問題大有好處。
假設現在n個人都已經戴好了帽子，問排在最後的那乙個人他頭上的帽子是什麼顏色，什麼時候他會回答「知道」？很顯然，只有在他看見前面n-1個人都戴著白帽時才可能，因為這時所有的n-1頂白帽都已用光，在他自己的腦袋上只能頂著黑帽子，只要前面有一頂黑帽子，那麼他就無法排除自己頭上是黑帽子的可能 ——即使他看見前面所有人都是黑帽，他還是有可能戴著第n頂黑帽。
現在假設最後那個人的回答是「不知道」，那麼輪到問倒數第二人。根據最後面那位的回答，他能推斷出什麼呢？如果他看見的都是白帽，那麼他立刻可以推斷出自己戴的是黑帽——要是他也戴著白帽，那麼最後那人應該看見一片白帽，問到他時他就該回答「知道」了。
但是如果倒數第二人看見前面至少有一頂黑帽，他就無法作出判斷——他有可能戴著白帽，但是他前面的那些黑帽使得最後那人無法回答「知道」；他自然也有可能戴著黑帽。
這樣的推理可以繼續下去，但是我們已經看出了苗頭。最後那個人可以回答「知道」當且僅當他看見的全是白帽，所以他回答「不知道」當且僅當他至少看見了一頂黑帽。這就是所有帽子顏色問題的關鍵！
如果最後乙個人回答「不知道」，那麼他至少看見了一頂黑帽，所以如果倒數第二人看見的都是白帽，那麼最後那個人看見的至少一頂黑帽在**呢？不會在別處，只能在倒數第二人自己的頭上。這樣的推理繼續下去，對於佇列中的每乙個人來說就成了：
「在我後面的所有人都看見了至少一頂黑帽，否則的話他們就會按照相同的判斷斷定自己戴的是黑帽，所以如果我看見前面的人戴的全是白帽的話，我頭上一定戴著我身後那個人看見的那頂黑帽。」
我們知道最前面的那個人什麼帽子都看不見，就不用說看見黑帽了，所以如果他身後的所有人都回答說「不知道」，那麼按照上面的推理，他可以確定自己戴的是黑帽，因為他身後的人必定看見了一頂黑帽——只能是第乙個人他自己頭上的那頂。事實上很明顯，第乙個說出自己頭上是什麼顏色帽子的那個人，就是從隊首數起的第乙個戴黑帽子的人，也就是那個從隊尾數起第乙個看見前面所有人都戴白帽子的人。
這樣的推理也許讓人覺得有點迴圈論證的味道，因為上面那段推理中包含了「如果別人也使用相同的推理」這樣的意思，在邏輯上這樣的自指式命題有點危險。但是其實這裡沒有迴圈論證，這是類似數學歸納法的推理，每個人的推理都建立在他後面那些人的推理上，而對於最後乙個人來說，他的身後沒有人，所以他的推理不依賴於其他人的推理就可以成立，是歸納中的第乙個推理。稍微思考一下，我們就可以把上面的論證改得適合於任何多種顏色的推論：
「如果我們可以從假設斷定某種顏色的帽子一定會在佇列**現，從隊尾數起第乙個看不見這種顏色的帽子的人就立刻可以根據和此論證相同的論證來作出判斷，他戴的是這種顏色的帽子。現在所有我身後的人都回答不知道，所以我身後的人也看見了此種顏色的帽子。如果在我前面我見不到此顏色的帽子，那麼一定是我戴著這種顏色的帽子。
」當然第乙個人的初始推理相當簡單：「佇列中一定有人戴這種顏色的帽子，現在我看不見前面有人戴這顏色的帽子，那它只能是戴在我的頭上了。」
對於題1)事情就變得很明顯，3頂紅帽子，4頂黑帽子，5頂白帽子給10個人戴，佇列中每種顏色至少都該有一頂，於是從隊尾數起第乙個看不見某種顏色的帽子的人就能夠斷定他自己戴著這種顏色的帽子，通過這點我們也可以看到，最多問到從隊首數起的第三人時，就應該有人回答「知道」了，因為從隊首數起的第三人最多只能看見兩頂帽子，所以最多看見兩種顏色，如果他後面的人都回答「不知道」，那麼他前面一定有兩種顏色的帽子，而他頭上戴的一定是他看不見的那種顏色的帽子。
題2)也一樣，3頂紅帽子，4頂黑帽子，5頂白帽子給8個人戴，那麼佇列中一定至少有一頂白帽子，因為其它顏色加起來一共才7頂，所以佇列中一定會有人回答「知道」。
題4)的規模大了一點，但是道理和2)完全一樣。100種顏色的5050頂帽子給5000人戴，前面99種顏色的帽子數量是 1+……+99=4950，所以佇列中一定有第100種顏色的帽子（至少有50頂），所以如果自己身後的人都回答「不知道」，那麼那個看不見顏色100帽子的人就可以斷定自己戴著這種顏色的帽子。
至於5)、6)「有紅黃綠三種顏色的帽子各1頂2頂3頂，但具體不知道哪種顏色是幾頂，有6個人」以及「有不知多少人排成一排，有黑白兩種帽子，每種帽子的數目都比人數少1」，原理完全相同，我就不具體分析了。
最後要指出的一點是，上面我們只是論證了，如果我們可以根據各種顏色帽子的數量和佇列中的人數判斷出在佇列中至少有一頂某種顏色的帽子，那麼一定有一人可以判斷出自己頭上的帽子的顏色。因為如果所有身後的人都回答「不知道」的話，那個從隊尾數起第乙個看不見這種顏色的帽子的人就可以判斷自己戴了此顏色的帽子。但是這並不是說在詢問中一定是由他來回答「知道」的，因為還可能有其他的方法來判斷自己頭上帽子的顏色。
比如說在題2)中，如果佇列如下：（箭頭表示佇列中人臉朝的方向）
白白黑黑黑黑紅紅紅白→
那麼在隊尾第一人就立刻可以回答他頭上的是白帽，因為他看見了所有的3頂紅帽子和4頂黑帽子，能留給他自己戴的只能是白帽子了
幾個數學題，這幾個數學題怎麼做？
1 從甲地到乙地的長途汽車原需行駛7小時，開通高速公路之後，路程近了30千公尺，而車速平均每小時增加30千公尺，只需4個小時即可到達，求甲乙兩地之間高速公路的路程。2 小趙為班級購買筆記本作晚會上的獎品，回來時向生活委員交賬說 一共買了36本，有兩種規格，單價分別為元和2.6元，去時我拿了100元，...
問大家幾個數學題，問大家幾個數學題 5
簡單來說，整式就是 數 與 表示數的字母 通過 加 減 乘 等運算 也可以不進行任何運算 得到的式子。需要注意的是 1 因為 數 與 數 經過任意次代數運算後，得到的仍然是 數 所以，我們將只包含 數 的代數式也稱為 數 2 分數也是數，所以，字母除以數的情形可以看作是字母與這個數的倒數的乘法 3 ...
幾個數學題可提出加分， 注意 幾個數學題 可提出加分
1.an 1 0.5 n 1 n 2 an 0.5n n 1 a1 0.5 1 1 1 1 an 0.5n n 1 1 an 0.5n 2 0.5n 1 2.m a 2 1 a 2 2 4 由x 2 2 2知n 1 2 x 2 2 1 2 2 4 則m n a 3且m 0時取等。3.a 1 0.5 ...