希望大家能夠大呼過癮~
? 1. 給一個(gè)瞎子52張撲克牌，并告訴他里面恰好有10張牌是正面朝上的。要求這個(gè)瞎子把牌分成兩堆，使得每堆牌里正面朝上的牌的張數(shù)一樣多。瞎子應(yīng)該怎么做？
答案：把撲克牌分成兩堆，一堆10張，一堆42張。然后，把小的那一堆里的所有牌全部翻過來。???
? 2. 如何用一枚硬幣等概率地產(chǎn)生一個(gè)1到3之間的隨機(jī)整數(shù)？如果這枚硬幣是不公正的呢？
答案：如果是公正的硬幣，則投擲兩次，“正反”為1，“反正”為2，“正正”為3，“反反”重來。
如果是不公正的硬幣，注意到出現(xiàn)“正反”和“反正”的概率一樣，因此令“正反反正”、“反正正反”、“正反正反”分別為1、2、3，其余情況重來。另一種更妙的辦法是，投擲三次硬幣，“正反反”為1，“反正反”為2，“反反正”為
? 3，其余情況重來。
3. 30枚面值不全相同的硬幣擺成一排，甲、乙兩個(gè)人輪流選擇這排硬幣的其中一端，并取走最外邊的那枚硬幣。如果你先取硬幣，能保證得到的錢不會(huì)比對(duì)手少嗎？
答案：先取者可以讓自己總是取奇數(shù)位置上的硬幣或者總是取偶數(shù)位置上的硬幣。數(shù)一數(shù)是奇數(shù)位置上的面值總和多還是偶數(shù)位置上的面值總和多，然后總是取這些位置上的硬幣就可以了。
? 4. 一個(gè)環(huán)形軌道上有n個(gè)加油站，所有加油站的油量總和正好夠車跑一圈。證明，總能找到其中一個(gè)加油站，使得初始時(shí)油箱為空的汽車從這里出發(fā)，能夠順利環(huán)行一圈回到起點(diǎn)。
答案：總存在一個(gè)加油站，僅用它的油就足夠跑到下一個(gè)加油站（否則所有加油站的油量加起來將不夠全程）。把下一個(gè)加油站的所有油都提前搬到這個(gè)加油站來，并把油已被搬走的加油站無視掉。在剩下的加油站中繼續(xù)尋找油量足以到達(dá)下個(gè)加油站的地方，不斷合并加油站，直到只剩一個(gè)加油站為止。顯然從這里出發(fā)就能順利跑完全程。
另一種證明方法：先讓汽車油箱里裝好足夠多的油，隨便從哪個(gè)加油站出發(fā)試跑一圈。車每到一個(gè)加油站時(shí)，記錄此時(shí)油箱里剩下的油量，然后把那個(gè)加油站的油全部裝上。試跑完一圈后，檢查剛才路上到哪個(gè)加油站時(shí)剩的油量最少，那么空著油箱從那里出發(fā)顯然一定能跑完全程。
? 5. 初始時(shí)，兩個(gè)口袋里各有一個(gè)球。把后面的n-2個(gè)球依次放入口袋，放進(jìn)哪個(gè)口袋其概率與各口袋已有的球數(shù)成正比。這樣下來，球數(shù)較少的那個(gè)口袋平均期望有多少個(gè)球？
答案：先考慮一個(gè)看似無關(guān)的問題——怎樣產(chǎn)生一個(gè)1到n的隨機(jī)排列。首先，在紙上寫下數(shù)字1；然后，把2寫在1的左邊或者右邊；然后，把3寫在最左邊，最右邊，或者插進(jìn)1和2之間……總之，把數(shù)字i等概率地放進(jìn)由前面i-1個(gè)數(shù)產(chǎn)生的（包括最左端和最右端在內(nèi)的）共i個(gè)空位中的一個(gè)。這樣生成的顯然是一個(gè)完全隨機(jī)的排列。
我們換一個(gè)角度來看題目描述的過程：假想用一根繩子把兩個(gè)球拴在一起，把這根繩子標(biāo)號(hào)為1。接下來，把其中一個(gè)小球分裂成兩個(gè)小球，這兩個(gè)小球用標(biāo)號(hào)為2的繩子相連。總之，把“放進(jìn)第i個(gè)球”的操作想象成把其中一個(gè)球分裂成兩個(gè)用標(biāo)有i-1的繩子相連的小球。聯(lián)想我們前面的討論，這些繩子的標(biāo)號(hào)事實(shí)上是一個(gè)隨機(jī)的全排列，也就是說最開始繩子1的位置最后等可能地出現(xiàn)在每個(gè)地方。也就是說，它兩邊的小球個(gè)數(shù)(1,n-1)、(2,n-2)、(3,n-3)、……、(n-1,1)這n-1種情況等可能地發(fā)生。因此，小袋子里的球數(shù)大約為n/4個(gè)。準(zhǔn)確地說，當(dāng)n為奇數(shù)時(shí)，小袋子里的球數(shù)為(n+1)/4；當(dāng)n為偶數(shù)時(shí)，小袋子里的球數(shù)為n^2/(4n-4)。
?
? 6. 考慮一個(gè)n*n的棋盤，把有公共邊的兩個(gè)格子叫做相鄰的格子。初始時(shí)，有些格子里有病毒。每一秒鐘后，只要一個(gè)格子至少有兩個(gè)相鄰格子染上了病毒，那么他自己也會(huì)被感染。為了讓所有的格子都被感染，初始時(shí)最少需要有幾個(gè)帶病毒的格子？給出一種方案并證明最優(yōu)性。
答案：至少要n個(gè)，比如一條對(duì)角線上的n個(gè)格子。n個(gè)格子也是必需的。當(dāng)一個(gè)新的格子被感染后，全體被感染的格子所組成的圖形的周長將減少0個(gè)、2個(gè)或4個(gè)單位（具體減少了多少要看它周圍被感染的格子有多少個(gè)）。又因?yàn)楫?dāng)所有格子都被感染后，圖形的周長為4n，因此初始時(shí)至少要有n個(gè)被感染的格子。
? 7. 在一個(gè)m*n的棋盤上，有k個(gè)格子里放有棋子。是否總能對(duì)所有棋子進(jìn)行紅藍(lán)二染色，使得每行每列的紅色棋子和藍(lán)色棋子最多差一個(gè)？
答案：可以。建一個(gè)二分圖G(X,Y)，其中X有m個(gè)頂點(diǎn)代表了棋盤的m個(gè)行，Y有n個(gè)頂點(diǎn)代表了棋盤的n個(gè)列。第i行第j列有棋子就在X(i)和Y(j)之間連一條邊。先找出圖G里的所有環(huán)（由于是二分圖，環(huán)的長度一定是偶數(shù)），把環(huán)里的邊紅藍(lán)交替染色。剩下的沒染色的圖一定是一些樹。對(duì)每棵樹遞歸地進(jìn)行操作：去掉一個(gè)葉子節(jié)點(diǎn)和對(duì)應(yīng)邊，把剩下的樹進(jìn)行合法的紅藍(lán)二染色，再把剛才去掉的頂點(diǎn)和邊加回去，給這個(gè)邊適當(dāng)?shù)念伾詽M足要求。
? 8. 任意給一個(gè)8*8的01矩陣，你每次只能選一個(gè)3*3或者4*4的子矩陣并把里面的元素全部取反。是否總有辦法把矩陣?yán)锏乃袛?shù)全部變?yōu)?？
答案：不能。大矩陣中有36個(gè)3*3的小矩陣和25個(gè)4*4的小矩陣，因此總共有61種可能的操作。顯然，給定一個(gè)操作序列，這些操作的先后順序是無關(guān)緊要的；另外，在一個(gè)操作序列中使用兩種或兩種以上相同的操作也是無用的。因此，實(shí)質(zhì)不同的操作序列只有2^61種。但8*8的01矩陣一共有2^64種，因此不是每種情況都有辦法達(dá)到目的。
? 9. 五個(gè)洞排成一排，其中一個(gè)洞里藏有一只狐貍。每個(gè)夜晚，狐貍都會(huì)跳到一個(gè)相鄰的洞里；每個(gè)白天，你都只允許檢查其中一個(gè)洞。怎樣才能保證狐貍最終會(huì)被抓?。?br />答案：按照2, 3, 4, 2, 3, 4的順序檢查狐貍洞可以保證抓住狐貍。為了說明這個(gè)方案是可行的，用集合F表示狐貍可能出現(xiàn)的位置，初始時(shí)F = {1, 2, 3, 4, 5}。如果它不在2號(hào)洞，則第二天狐貍已經(jīng)跑到了F = {2, 3, 4, 5}。如果此時(shí)它不在3號(hào)洞，則第三天狐貍一定跑到了F = {1, 3, 4, 5}。如果此時(shí)它不在4號(hào)洞，則再過一晚后F = {2, 4}。如果此時(shí)它不在2號(hào)洞，則再過一天F = {3, 5}。如果此時(shí)它不在3號(hào)洞，再過一天它就一定跑到4號(hào)洞了。
方案不是唯一的，下面這些方案都是可行的：
2, 3, 4, 4, 3, 2
4, 3, 2, 2, 3, 4
4, 3, 2, 4, 3, 2
? 10. 一個(gè)經(jīng)典老題是說，把一個(gè)3*3*3的立方體切成27個(gè)單位立方體，若每一刀切完后都允許重新擺放各個(gè)小塊的位置，最少可以用幾刀？答案仍然是6刀，因?yàn)檎虚g那個(gè)單位立方體的6個(gè)面都是后來才切出來的，因此怎么也需要6刀。考慮這個(gè)問題：若把一個(gè)n*n*n的立方體切成一個(gè)個(gè)單位立方體，最少需要幾刀？
答案：事實(shí)上，從一個(gè)更強(qiáng)的命題出發(fā)反而能使問題變得更簡單。對(duì)于一個(gè)a*b*c的長方體，我們需要f(a)+f(b)+f(c)刀，其中f(x)=?log(x)/log(2)?。只需要注意到，在整個(gè)過程中的任何一步，切完當(dāng)前最大的塊所需要的刀數(shù)也就等于整個(gè)過程還需要的刀數(shù)，因?yàn)槠渌K需要的刀數(shù)都不會(huì)超過最大塊所需刀數(shù)，它們都可以與最大塊一道并行處理。這表明，我們的最優(yōu)決策即是讓當(dāng)前的最大塊盡可能的小，也就是說要把當(dāng)前的最大塊盡可能相等地切成兩半。利用數(shù)學(xué)歸納法，我們可以很快得到本段開頭的結(jié)論。
腦袋暈了
感覺智力明顯下降了……
像看到了高中時(shí)候的數(shù)學(xué)題，或許很多人都忘記了。或許這樣的智力題對(duì)與一些人來講有點(diǎn)不公平。
