第25題磨光變換.

1、第25題磨光變換畫一個圓，沿圓周均勻放上8個圍棋子，放法隨機，然后按以下規(guī) 則調(diào)整。 若原來相鄰兩棋子顏色相同，貝恠它們所在孤的中點處放上一個 黑子。(2) 若原來相鄰兩棋子顏色相異，則在它們所在弧的中點處放上一個 白子。(3) 上述操作完畢后，取走原先放著的 8個棋子。調(diào)整后得到沿圓周均勻分布的新的 8個棋子。問：能否經(jīng)過有限次調(diào)整后，使 8個棋子全部都成黑子？若行，則 至多要調(diào)整幾次。分析：先特例探索圖 25-1圖25-1是經(jīng)過8次調(diào)整后使8個棋子全部都變成黑子的特例。經(jīng)過多次嘗試后發(fā)現(xiàn)：每次嘗試都能經(jīng)過不多于8次調(diào)整后，使8個棋子全部變成黑子。由此產(chǎn)生了如下猜測：對任一種放法都可經(jīng)過不多

2、于8次調(diào)整后，使8個棋子全部變成黑 子。如何判別上述猜測的真?zhèn)文?？因為不同分布是有限的，至多不超過 28即256種，所以我們可以采 用窮舉法，列舉所有可能放法，一一驗證。這種方法可行，但工作量很 大。是否還有更簡便的方法，利用一些數(shù)學(xué)工具，將這個問題轉(zhuǎn)化為一 個數(shù)學(xué)問題呢？倘若能建立起黑、白子與特定的2個數(shù)字間的對應(yīng)，使調(diào)整后的結(jié) 果與對應(yīng)數(shù)字的相應(yīng)運算結(jié)果相對應(yīng)。那么黑白子的調(diào)整可以轉(zhuǎn)化為對 應(yīng)數(shù)字的運算。從而可以通過數(shù)字運算來解決原有問題。經(jīng)過聯(lián)想與對比發(fā)現(xiàn)只要將黑子與 1對應(yīng)，白子與-1相對應(yīng)，即黑 子一- 1;白子一- -1那么黑白子的變換就相當(dāng)于對土 /進行乘法運算。正如下表所示:變

3、換黒白黑白白白黑對應(yīng)以上對應(yīng)就將原問題轉(zhuǎn)化成一個數(shù)學(xué)問題。解：先建立集合黑子，白子與集合-1,1間對應(yīng)黑子一- 1白子一- -1那么黑白子的調(diào)整可轉(zhuǎn)化成對應(yīng)數(shù)字的乘法運算。設(shè)第一次均勻放置在第i位上的棋子對應(yīng)數(shù)為xi(i=1，2, 3, 4, 5,6, 7, 8)，則 Xi -1, 10用表藥門表示各次棋子調(diào)整狀態(tài)對應(yīng)數(shù)(在岀現(xiàn)時，因為故省略不寫 k = 1, 2, 3f 4, 5, 6, 7, 8)表25 1狀態(tài)i234初始態(tài)xix2網(wǎng)策一次調(diào)整態(tài)丸緬沁昭5第二歡調(diào)整老第三次調(diào)整態(tài)第四坎週整臺第五次調(diào)整態(tài)屯轡那1調(diào)整倉第七次調(diào)整態(tài)IlXii-l 1認i1-1 1仏ii_i 1認i1 1第八次

4、調(diào)整恵1111續(xù)表置狀態(tài)、5678初賠態(tài)x7策一次調(diào)整態(tài)哪1第二校調(diào)整窸嘰第三次調(diào)楚態(tài)施勺勺第四次調(diào)整懇歹1第五次凋整態(tài)i x51x2巧停3嗨第六次調(diào)整態(tài)切陶花陶V3X5X7第七次調(diào)整悲TTjT ii 1nnrUL 111 XjJIU XjUL 1第兒次調(diào)整態(tài)11118由上表可知：不管初始狀態(tài)如何，至多經(jīng)過 8次調(diào)整后能使8子變 成全黑。回顧：從上表中還可以得到以下結(jié)論：(1) 經(jīng)過七次調(diào)整后，必成同色；(2) 經(jīng)過六次調(diào)整后，必成同色或黑白相間。此外能利用上表構(gòu)造經(jīng)過3次至6次調(diào)整變成全黑狀態(tài)的實例。下面構(gòu)造經(jīng)六次調(diào)整成全黑狀態(tài)的實例。要達到此目的，只要使第四次調(diào)整態(tài)為黑白相間狀態(tài)。為此可取

5、Xi X5=X3 - X7 = 1，且 X2 X6=X4 X8=-1 ；于是可取 X2=X4二 1，Xl=X3=X5=X6=X7=X8=1。即當(dāng)原始狀態(tài)呈圖25-2時，一定可以經(jīng)過六次調(diào)整后，變成全黑狀 態(tài)。團 25-2上述“調(diào)整”用數(shù)學(xué)術(shù)語來說就稱作變換。若變換具有縮小差別達到平衡的性質(zhì)，則稱這種變換為“磨光變換”上述結(jié)論可表示成“當(dāng)n=8時，變換是磨光變換”。這個問題是有它的實際背景的。很多自然現(xiàn)象都可以說是在進行某 種局部調(diào)整。例如水總是由高處向低處流；電子總是從高電位移到低電位。很多 自然現(xiàn)象都可通過局部調(diào)整來達到一種平衡狀態(tài)。從而相應(yīng)變換就具有“磨光”性質(zhì)。上述問題是否可以從8子推廣

6、到n子呢？即沿圓周均勻放n個不同 色的子，作相同變換，這時是否也具有磨光性質(zhì)？我們需要分析：當(dāng) n 為何值時，肯定沒有；當(dāng)n為何值時，可能沒有；當(dāng)n為何值時，肯定 有。下面分兩種情況進行討論。(1)n為奇數(shù)時：當(dāng)n=3時，原狀態(tài)不同色時肯定不能磨光。于是，猜測n為奇數(shù)時，肯定不能磨光。實際上，由于初始態(tài)中既有黑子，又有白子所以經(jīng)過一次變換，由 規(guī)則(2)可知仍有白子。又因為總的子數(shù)是奇數(shù)，原始狀態(tài)不可能是黑白 相間的。故原始態(tài)中一定有同色子相鄰的情況，經(jīng)過一次變換，由規(guī)則(1) 可知仍有黑子。所以經(jīng)過一次變換后的態(tài)圖中仍有白子， 且不是全白 這一性質(zhì)在變換過程中一直保持。因此 n為奇數(shù)時變換不

7、可能具有磨光 性質(zhì)。(2)n為偶數(shù)時：不難證明n=2、4時，肯定能磨光。n=6時證明遇困難，于是我們設(shè) 法找反例。圖25-3是n=6時，磨光的反例。因為第一次調(diào)整態(tài)圖與第五次調(diào)整態(tài)圖是對偶圖 (即黑白色相反)， 所以第六次調(diào)整圖同第二次調(diào)整圖，第七次調(diào)整態(tài)圖同第三次調(diào)整態(tài) 圖，即出現(xiàn)循環(huán)，所以這一特例不能磨光。因為存在n=6時，可以磨光的特例。所以n=6時不一定能磨光。因此當(dāng)n為偶數(shù)時也不一定能 磨光。是否存在特殊性質(zhì)的偶數(shù)k，使n=k時一定能磨光呢？利用楊輝三角 形的性質(zhì)，可以證明：當(dāng)k=2m(m N)時一定能磨光。由于證明復(fù)雜這里就 不詳加討論。綜上討論可知：如果原始狀態(tài)的n子不同色，那么

8、(1)當(dāng)n為奇數(shù)時，一定不能磨光； 當(dāng)n為2m(m N)型偶數(shù)時，一定能磨光；(3) 當(dāng)n為不呈2m(m N)型偶數(shù)時，存在著不能磨光的可能。注：在解決這一問題過程中用1, -1所構(gòu)成的集合，與它們間的乘法 這一數(shù)學(xué)結(jié)構(gòu)，將原問題中的主要特征，主要關(guān)系抽象出來，歸結(jié)成為 數(shù)學(xué)問題，然后通過解決該數(shù)學(xué)問題，從而解決原實際問題。這種利用 一定的數(shù)學(xué)結(jié)構(gòu)來解決實際問題的方法，稱為“數(shù)學(xué)模型的方法”。其 中所用的數(shù)學(xué)結(jié)構(gòu)，稱為數(shù)學(xué)模型。數(shù)學(xué)模型的方法簡稱MM&法(Mathematical Modelli ng Method) 。我們所學(xué)過的各種數(shù)學(xué)概念：如實數(shù)、函數(shù)、集合、各種方程、公 式都可以作為數(shù)

9、學(xué)模型。具體講一次函數(shù)是勻速直線運動的數(shù)學(xué)模型。一般的正弦函數(shù)是簡 諧振動的數(shù)學(xué)模型。二元一次方程是雞兔同籠問題的數(shù)學(xué)模型。數(shù)學(xué)史上著名的“哥尼斯堡七橋問題”就是由著名數(shù)學(xué)家歐拉，用 數(shù)學(xué)模型方法解決的，并由此導(dǎo)致了新興數(shù)學(xué)分支一一圖論的誕生。18世紀(jì)，東普魯士有個城市叫哥尼斯堡(即現(xiàn)在的加里寧格勒)，帕 瑞格爾河從城中穿過，河中有兩個島A與D,河上有七座橋連結(jié)這兩個島 及河的兩岸B、C。如圖25-4所示。圖 25-4河中心的島A上有一所古老的哥尼斯堡大學(xué)。每天傍晚，大學(xué)生總 要在這七座大橋之間散步。當(dāng)時的大學(xué)生們熱衷于解決這樣二個難題：(1) 一個散步者能否經(jīng)過每座橋恰好一次，既無重復(fù)也無遺

10、漏。能否經(jīng)過每座橋恰好一次，并且最后能夠回到原來出發(fā)點。大學(xué)生們百思不解，百試不成。寫信求助于當(dāng)時大數(shù)學(xué)家歐拉，1736 年歐拉終于解決了這個問題。歐拉運用的就是數(shù)學(xué)模型法。他先將七橋問題抽象化成為一個數(shù)學(xué) 問題。他把島和陸地抽象成一個點，把橋抽象成一條線，從而將原來地圖 抽象成圖25-5圖形。圖 2S-5于是，原問題 轉(zhuǎn)化成圖25-5能否不重復(fù)地一筆畫出來。原問題 轉(zhuǎn)化成圖25-5能否從某一頂點出發(fā)，不重復(fù)地一筆畫出來，且最后又回 到起點。歐拉進一步考察一筆畫問題時發(fā)現(xiàn)：一筆畫總有起點和終點。它的 中途經(jīng)過的點有進線必有相應(yīng)出線，所以所有這樣點必有偶數(shù)條線和其 它點相連，只有起點和終點可以例外。為此一個圖形可以一筆畫成的必 要條件是與其他點有奇數(shù)條線相連的點只能 0個或2個?，F(xiàn)圖25-5中點 A、B、C D與其它點的連線都是奇數(shù)條。由此歐拉得出七橋問題(1)，(2) 都無解結(jié)論。七橋問題求解過程，可用框圖表示如下：用數(shù)學(xué)模型方法解決問題的基本步驟為： 從實際問題中抽象出數(shù)學(xué)模型，將原問題歸結(jié)為數(shù)學(xué)問題。(2) 在數(shù)學(xué)模型上進行推理或演算，求得數(shù)學(xué)問題的解。(3) 把研究數(shù)學(xué)模型所得結(jié)論返回實際問題中去進行檢驗、修正，直 至得到實際問題的解答。EJ 25-6團 25-7練習(xí)251證明n=8時，圍棋子在圓周上的均勻隨機分布有且只有 36種。2