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

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

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

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

證明：

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

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

解

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

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

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

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

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

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

利用圖的方法來描述該問題。將人看成頂點，兩人彼此都認識用實線連，否則虛線。證明：

圖論法及相識問題（拉姆齊問題）

問題轉(zhuǎn)化為在一個6階圖中必存在實線三角形或虛線三角形。請大家一起畫圖證明υ2

υ1

υ3

υ4

υ6

υ5

υ1

υ2

υ3υ4

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

υ1υ3、

υ1υ4實線與υ1相連的邊必然有：實線條數(shù)不小于3或虛線條數(shù)不小于3拉姆齊問題也可這樣敘述：6階2色完全圖中必含有3階單色完全圖。其他類似可推出的結(jié)果：命題任一6階2色完全圖中至少含有兩個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黑色所以存在第二個3階單色完全圖。υ2

υ1

υ3

υ4

υ6

υ5

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

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

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

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

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

例人狼羊菜過河問題狀態(tài)轉(zhuǎ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)}問題轉(zhuǎn)化為：由初始狀態(tài)(1,1,1,1)出發(fā)，經(jīng)奇數(shù)次上述運算轉(zhuǎn)化為狀態(tài)(0,0,0,0)的過程。規(guī)定運算：分量1+1=0,1+0=0+1=1,0+0=0如(1,1,1,1)+(1,0,1,0)=(0,1,0,1)其實際意義：人狼羊菜原均在左岸，人帶羊過河，左岸為新狀態(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例夫妻過河問題

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

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

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

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

x個男子、y個女子在北岸，其中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對夫妻。

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

(0,1)(0