計(jì)算機(jī)20xx組合數(shù)學(xué)—ch-資料下載頁(yè)
2025-05-14 22:52本頁(yè)面
【正文】 :軍團(tuán) , 軍官對(duì)應(yīng)數(shù)偶 (i, j), i, j?[1,6] 問(wèn)題等價(jià)于構(gòu)造數(shù)偶 (i,j)排成的 6階方陣 , 使得 1) 數(shù)偶第一個(gè)數(shù)字構(gòu)成拉丁方 。 2) 數(shù)偶第二個(gè)數(shù)字構(gòu)成拉丁方 。 3) 每個(gè)數(shù)偶只出現(xiàn)一次 . 兩個(gè)拉丁方稱(chēng)為互相正交，即正交拉丁方 . 定義 :設(shè) A=(aij)n n,B=(bij)n n是兩個(gè) n n拉丁方 . 令 C=((aij, bij))n n,若 C的 n2對(duì)數(shù)偶互不相同 , 則稱(chēng) A與 B正交 . ???????????????????????????????)2,1()1,3()3,2()1,2()3,1()2,3()3,3()2,2()1,1(213132321132213321 上述是兩個(gè) 3階正交拉丁方。 2階哪？ 36軍官問(wèn)題即不存在 6階正交拉丁方。 6猜想不對(duì)。 對(duì)于只有 9個(gè)軍官的類(lèi)似問(wèn)題有解： 48 167。 涂色問(wèn)題 ? 在實(shí)際應(yīng)用中，很多計(jì)數(shù)問(wèn)題都可抽象成涂色問(wèn)題。 ?作為典型的組合計(jì)數(shù)問(wèn)題，根據(jù)涂色問(wèn)題難度的不同，將反映出各種不同的計(jì)數(shù)技術(shù)。 49 例 對(duì)正三角形的三個(gè)頂點(diǎn)涂以紅、藍(lán)（ r和 b）兩種顏色，求有多少種不同的涂色方案？ 解 由于只有兩種顏色，我們可以采用枚舉方法分類(lèi)討論。 50 ? 涂色方案可分成四類(lèi)： （ 1）三點(diǎn)全涂紅色，只有一種方案 rrr （ 2）三點(diǎn)全涂藍(lán)色，只有一種方案 bbb （ 3）兩點(diǎn)涂紅色，一點(diǎn)涂藍(lán)色，因藍(lán)色可分別涂于三個(gè)頂點(diǎn)之一，故有 3種方案 brr， rbr， rrb （ 4）由對(duì)稱(chēng)性可知，兩點(diǎn)涂藍(lán)色，一點(diǎn)染紅的方案也有 3種： 51 紅色 , 藍(lán)色 52 如果考慮正三角形可以旋轉(zhuǎn)，則(3),(4),(5)顯然是同一個(gè)涂色方案，(6),(7),(8)也是同一個(gè)涂色方案，這樣涂色方案數(shù)就變成了 4種。 如果變成了空間的四面體了，即加上空間的旋轉(zhuǎn)之后，涂色方法的計(jì)算將更加復(fù)雜。 要涂色的點(diǎn)和可選顏色的數(shù)目如再增加的話，枚舉方法就不奏效了 例 :棋盤(pán)的完美覆蓋 m n棋盤(pán) : m行 n列方格 , b牌 :1行 b個(gè)的方格條 m n棋盤(pán)被 b牌的一個(gè) 完美覆蓋 是 b牌在棋盤(pán)上的一個(gè)排列 , 滿足 : (1) 每個(gè)格子恰好只被一張牌覆蓋 。 (2) 每條 b牌覆蓋 b個(gè)方格 . 定理 : m n棋盤(pán)有 b牌的完美覆蓋 ?b|m或 b|n. 3?4棋盤(pán) 6?6棋盤(pán)有 4牌的完美覆蓋嗎 ? 有 2牌的完美覆蓋 . 需要特殊技巧解決問(wèn)題 例 有 101名選手參加羽毛球比賽，如果采用單循環(huán)淘汰制，問(wèn)產(chǎn)生冠軍需要進(jìn)行多少場(chǎng)比賽？ 方法一： 50+25+13+6+3+2+1=100場(chǎng)比賽 方法二： 由于每場(chǎng)比賽都要產(chǎn)生一個(gè)失敗者，而每個(gè)失敗者只能失敗一次，因此比賽的場(chǎng)數(shù)與失敗者的人數(shù)相等，除冠軍外其他 100人都失敗過(guò)，因此產(chǎn)生冠軍需要 100場(chǎng)比賽。 例 有一個(gè)邊長(zhǎng)為 3的立方體木塊，要把它切割成27個(gè)邊長(zhǎng)為 1的小立方體，如果在切割的過(guò)程中可以重新排列被切割的木塊，問(wèn)至少需要多少次才能完成任務(wù)？ 解： 首先可以看到，通過(guò) 6次是可以完成整個(gè)切割的，上圖就是這樣的一種方案。其次，我們證明少于 6次是不能完成切割的。由于處于原立方體中心的一個(gè)小立方體的每個(gè)面都是由切割產(chǎn)生的，每次切割只能產(chǎn)生一個(gè)面，所以切割次數(shù)不能少于它的面數(shù)，因此至少 6次才能完成切割。
試題試卷相關(guān)推薦
鄂ICP備17016276號(hào)-1