第2周-數(shù)學(xué)的巧妙運(yùn)用

數(shù)學(xué)的巧妙運(yùn)用例1棋子顏色的變化

任意拿出黑白兩種顏色的棋子共n個(gè),排成如圖所示的一個(gè)圓圈.然后在兩顆顏色相同的棋子中間放一顆黑色棋子,在兩顆顏色不同的棋子中間放一顆白色棋子,放完后撤掉原來(lái)所放的棋子.再重復(fù)以上的過(guò)程,這樣放下一圈后就拿走前次的一圈棋子,問(wèn)這樣重復(fù)進(jìn)行下去各棋子的顏色會(huì)怎樣變化呢?n=8有結(jié)論：設(shè)黑子用+1表示，白子用-1表示。記8顆分別為a1,a2,…,a8,(

ai=+1,-1)第0次：a1a2a2a3a4a5a6a7a8第1次：a1a2a2a3a3a4…a7a8a8a1第2次：a1a22a3a2a32

a4…a8a12

a2.。。。.。。。.第8次：a1a28a328

a456a570a656a728a88

a1,…至多經(jīng)過(guò)8次變換，棋子的顏色全變黑。問(wèn)題：對(duì)任意整數(shù)n，棋子的顏色能全變黑嗎？例2某人由A處到B處去，途中需到河邊取些水，如下圖。問(wèn)走那條路最近？（用盡可能簡(jiǎn)單的辦法求解。）dAB河例3將形狀質(zhì)量相同的磚塊一一向右往外疊放，欲盡可能地延伸到遠(yuǎn)方，問(wèn)最遠(yuǎn)可以延伸多大距離。設(shè)磚塊是均質(zhì)的，長(zhǎng)度與重量均為1，其重心在中點(diǎn)1/2磚長(zhǎng)處，現(xiàn)用歸納法推導(dǎo)。Zn(n－1)n(n＋1)由第n塊磚受到的兩個(gè)力的力矩相等，有1/2-Zn=(n－1)Zn故Zn=1/(2n)，從而上面n塊磚向右推出的總距離為，故磚塊向右可疊至任意遠(yuǎn)，這一結(jié)果有點(diǎn)出人意料。通常，1公斤面，1公斤餡，包100個(gè)湯圓，有一次餡多了0.4kg，問(wèn)能否將湯圓包大一些或小一些將這些餡仍用1kg面用完?問(wèn)題圓面積為S的一個(gè)皮，包成體積為V的湯圓,若分成n個(gè)皮，每個(gè)圓面積為s，包成體積為vV和nv哪個(gè)大?討論題:包湯圓Ssss…Vvvv(共n個(gè))定性分析V比nv大多少?定量分析討論題:包湯圓假設(shè)1.皮的厚度一樣2.湯圓的形狀一樣模型應(yīng)用若100個(gè)湯圓（餃子）包1公斤餡,則50個(gè)湯圓(餃子)可以包公斤餡R~大皮半徑V是nv是倍1.4r~小皮半徑兩個(gè)k1（和k2）一樣(1),(2),(3)

奇偶校驗(yàn)方法及相關(guān)問(wèn)題

證明：

采用反證法，設(shè)，其中p、q互素，則有p2=2q2。因?yàn)?|p2，故2|p。記p=2p1，可得4p12=2q2，即2p12=q2，故又有2|q，與p、q互素矛盾。例4證明是無(wú)理數(shù)。同樣方法可以證明：若m是大于1的素?cái)?shù)，n是大于1的整數(shù)，則必為無(wú)理數(shù)。例5擬用40塊方形瓷磚鋪設(shè)如下圖所示的地面，但商店只有長(zhǎng)方形瓷磚，其大小為方形的兩塊。問(wèn)購(gòu)買(mǎi)20塊長(zhǎng)方形瓷磚后，是否可能不裁開(kāi)而直接鋪好地面？解

將圖11.4中的(a)(b)黑白相間染色。顯然，如長(zhǎng)方形瓷磚不裁開(kāi)，只能用來(lái)復(fù)蓋相鄰的兩格，故復(fù)蓋的兩格必為一白一黑。下圖(a)中共有21個(gè)黑格和19個(gè)白格，故不可能直接鋪好，下圖(b)中黑白格各為20個(gè)，大家很容易找到直接鋪設(shè)的方法。圖(a)圖(b)討論題擬將一批尺寸為1×2×4的的商品裝入尺寸為6×6×6的正方體包裝箱中，怎樣才能使所裝的商品最多?討論題擬將一批尺寸為1×2×4的的商品裝入尺寸為6×6×6的正方體包裝箱中，怎樣才能使所裝的商品最多?

解

將正方體剖分成27個(gè)2×2×2的小正方體，并按下圖所示黑白相間地染色。再將每一2×2×2的小正方體剖分成1×1×1的小正方體。易見(jiàn)，27個(gè)2×2×2的正方體中，有14個(gè)是黑的，13個(gè)是白的（或13黑14白），故經(jīng)兩次剖分，共計(jì)有112個(gè)1×1×1的黑色小正方體和104個(gè)1×1×1的白色小正方體。雖然包裝箱的體積恰好是商品體積的27倍，但容易看到，不論將商品放置在何處，它都將占據(jù)4個(gè)黑色和4個(gè)白色的1×1×1小正方體的位置，故商品不可能充滿包裝箱。解

將正方體剖分成27個(gè)2×2×2的小正方體，并按下圖所示黑白相間地染色。解

將正方體剖分成27個(gè)2×2×2的小正方體，并按下圖所示黑白相間地染色。解

將正方體剖分成27個(gè)2×2×2的小正方體，并按下圖所示黑白相間地染色。解

將正方體剖分成27個(gè)2×2×2的小正方體，并按下圖所示黑白相間地染色。解

將正方體剖分成27個(gè)2×2×2的小正方體，并按下圖所示黑白相間地染色。再將每一2×2×2的小正方體剖分成1×1×1的小正方體。例1在每一次人數(shù)不少于6人的聚會(huì)中必可找出這樣的3人，他們或者彼此均認(rèn)識(shí)或者彼此均不認(rèn)識(shí)。

利用圖的方法來(lái)描述該問(wèn)題。將人看成頂點(diǎn)，兩人彼此都認(rèn)識(shí)用實(shí)線連，否則虛線。證明：

圖論法及相識(shí)問(wèn)題（拉姆齊問(wèn)題）

問(wèn)題轉(zhuǎn)化為在一個(gè)6階圖中必存在實(shí)線三角形或虛線三角形。請(qǐng)大家一起畫(huà)圖證明υ2

υ1

υ3

υ4

υ6

υ5

υ1

υ2

υ3υ4

任取一頂點(diǎn)，不妨υ1考察υ2υ3、υ2υ4和υ3υ4υ2υ3、υ2υ4和υ3υ4只能是虛線，否則得證但這樣三角形υ2υ3υ4的三邊均為虛線不妨取υ1υ2、

υ1υ3、

υ1υ4實(shí)線與υ1相連的邊必然有：實(shí)線條數(shù)不小于3或虛線條數(shù)不小于3拉姆齊問(wèn)題也可這樣敘述：6階2色完全圖中必含有3階單色完全圖。其他類似可推出的結(jié)果：命題任一6階2色完全圖中至少含有兩個(gè)3階單色完全圖。

證明：前面證明必存在3階單色完全圖，不妨設(shè)υ1υ2υ3

為紅色完全圖υ1υ5、υ2υ5、υ3υ5中至少有兩條黑色、故υ1υ5與υ2υ5中至少有一條是黑色若υ4υ5υ6也是紅色三角形，命題已得證

故至少一邊與υ1υ2υ3的邊異色，不妨設(shè)υ4υ5黑色υ1υ4、υ2υ4、υ3υ4至少應(yīng)有兩條黑色，不妨設(shè)υ1υ4、υ2υ4黑色所以存在第二個(gè)3階單色完全圖。υ2

υ1

υ3

υ4

υ6

υ5

討論題17位學(xué)者中每人都和其他人通信討論3個(gè)方向的課題。任意兩人間只討論其中一個(gè)方向的課題，則其中必可找出3位學(xué)者，他們之間討論的是同一方向的課題。討論題:任意的9個(gè)人中一定有3個(gè)人互相認(rèn)識(shí)或者有4個(gè)人互相不認(rèn)識(shí)。著名的Euler“七橋問(wèn)題”

東普魯士哥尼斯堡(原蘇聯(lián)加里寧格勒)有一條布勒爾河，這條河有兩條支流，在城中心匯合成大河，河中有一小島，現(xiàn)有七座橋?qū)⑺c陸地連接（圖1-2）

1735年左右，哥尼斯堡大學(xué)生傍晚散步時(shí)，總想一次走過(guò)七座橋，要求每座橋只準(zhǔn)走一遍，試來(lái)試去總未成功，于是，他們寫(xiě)信求教瑞士的大數(shù)學(xué)家Euler，他用了幾天時(shí)間反復(fù)思考、想象，終于在1736年發(fā)表了圖論的第一篇論文“哥尼斯堡的七座橋”解決了這個(gè)問(wèn)題

在文中歐拉創(chuàng)造性地將每一塊陸地用一個(gè)點(diǎn)代替，而將每一座橋用連接相應(yīng)兩點(diǎn)的一條線來(lái)代替，從而得到了一個(gè)“圖”這樣，此問(wèn)題就變?yōu)椤皬膱D的某個(gè)頂點(diǎn)出發(fā)，經(jīng)過(guò)每條線只一次最后回到原來(lái)的地方”。由于每一次通過(guò)點(diǎn)的邊總是兩條，即進(jìn)入和離開(kāi)該點(diǎn)，如果七橋問(wèn)題有解，則圖中與每個(gè)點(diǎn)相連的邊應(yīng)該為偶數(shù)條，而圖中與各點(diǎn)相連的邊都是奇數(shù)條，因而七橋問(wèn)題無(wú)解。無(wú)向圖的歐拉通路、歐拉圖

（即一筆畫(huà)問(wèn)題）經(jīng)過(guò)圖中每條邊一次且僅一次并且行遍圖中每個(gè)頂點(diǎn)的通路(回路),稱為歐拉通路或歐拉跡(歐拉回路或歐拉閉跡).存在歐拉回路的圖,稱為歐拉圖.定理無(wú)向圖G具有歐拉通路,當(dāng)且僅當(dāng)G是連通圖且有零個(gè)或兩個(gè)奇度頂點(diǎn).若無(wú)奇度頂點(diǎn),則通路為回路;若有兩個(gè)奇度頂點(diǎn),則它們是每條歐拉通路的端點(diǎn).推論無(wú)向圖G為歐拉圖(具有歐拉回路)當(dāng)且僅當(dāng)G是連通的,且G中無(wú)奇度頂點(diǎn).圖中,(1-3)不是歐拉圖,(4)是歐拉圖.例是歐拉圖；不是歐拉圖，但存在歐拉通路；即不是歐拉圖，也不存在歐拉通路。問(wèn)題：人、狼、羊、菜均要過(guò)河，船需要人劃，另外至多還能載一物，而當(dāng)人不在時(shí)，狼要吃羊，羊要吃菜。問(wèn)人、狼、羊、菜怎樣過(guò)河，試設(shè)計(jì)一個(gè)安全渡河方案，并使渡河次數(shù)盡可能地少。窮舉法

例人狼羊菜過(guò)河問(wèn)題狀態(tài)轉(zhuǎn)移問(wèn)題1）允許狀態(tài)集合S人、狼、羊、菜依次用四維向量表示它們的狀態(tài)，在左岸用1表示，在右岸用0表示。如（0，1，0,1)表示人、羊在右岸，狼、菜在左岸。人在左岸(1,1,1,1),(1,1,1,0),(1,1,0,1),(1,0,1,1),(1,0,1,0)人在右岸(0,0,0,0),(0,0,0,1),(0,0,1,0),(0,1,0,0),(0,1,0,1)2)允許決策集（劃船方式）D用四維向量表示決策，如（1，1，0，0）表示人帶狼擺渡。D={(1,0,0,0),(1,1,0,0),(1,0,1,0),(1,0,0,1)}問(wèn)題轉(zhuǎn)化為：由初始狀態(tài)(1,1,1,1)出發(fā)，經(jīng)奇數(shù)次上述運(yùn)算轉(zhuǎn)化為狀態(tài)(0,0,0,0)的過(guò)程。規(guī)定運(yùn)算：分量1+1=0,1+0=0+1=1,0+0=0如(1,1,1,1)+(1,0,1,0)=(0,1,0,1)其實(shí)際意義：人狼羊菜原均在左岸，人帶羊過(guò)河，左岸為新?tīng)顟B(tài)，即僅剩狼和菜。s(i+1)=s(i)+d(i)1,1,1,1(1,0,1,0)0,1,0,1(1,0,0,0)1,1,0,1(1,1,0,0)0,0,0,1(1,0,0,1)0,1,0,0(1,0,1,0)1,0,1,1(1,0,1,0)1,1,1,0(1,0,0,1)(1,1,0,0)0,0,1,0(1,0,0,0)1,0,1,0(1,0,1,0)0,0,0,0例夫妻過(guò)河問(wèn)題

問(wèn)題：有3對(duì)夫妻過(guò)河，船最多能載2人，條件是任一女子不能在其丈夫不在的情況下與其它男子在一起，如何安排三對(duì)夫妻過(guò)河？

此類問(wèn)題是古典的趣味數(shù)學(xué)問(wèn)題，用窮舉方法可以解決，但怎樣建立數(shù)學(xué)模型用計(jì)算機(jī)解決？

模型構(gòu)成：假設(shè)由北岸往南岸渡河，用向量（x，y）表示有(x,y)為狀態(tài)向量；

由條件知，有些狀態(tài)是可取的，有些是不可取的，

x個(gè)男子、y個(gè)女子在北岸，其中0≤x,y≤3，

稱向量如狀態(tài)(2,3)是不可取的，

而狀態(tài)(3,1)是可取的。1)可取狀態(tài)：

總共有10種可取狀態(tài)具體如下：

(3,3)(3,2)(3,1)(3,0)(1,1)(0,0)(0,1)(0,2)(0,3)(2,2)

其中(i,i)表示i對(duì)夫妻。

用S表示可取狀態(tài)的集合，稱為允許狀態(tài)集合。2)可取運(yùn)載：

(0,1)(0