1994年b題鎖具裝箱問題的參考解答

1、1994 年 B 題鎖具裝箱問題的參考解答 題鎖具裝箱問題的參考解答一、 一、每批鎖的把數(shù) 每批鎖的把數(shù)鎖具裝箱的第一問完全是一個數(shù)學問題，可以用不同的方法去解決.1.排列組合法 排列組合法首先可以求出有 5 個槽、每個槽有 6 個高度的所有可能的個數(shù)為 n1=65=777.6.為了滿足題目中提出的至少有三個不同的高度，且相鄰高差不應(yīng)為 5 的要求，我們應(yīng)該減去不滿足要求的鎖具。僅有一個槽高的鎖具數(shù)目為 n2= . 6 C 16 ?僅

2、有二個槽高的鎖具數(shù)目為 n3= (25-2)=450 2 6 C下面要考察相鄰槽高之差為 5 的鎖具，為了方便，記相鄰槽高之差為 5 的鎖具集合記為A，將 A 分解為以下 4 種集合：A1： 16abc 或 61abcA2： a16bc 或 a61bcA3： ab16c 或 ab61cA4： abc 16 或 abc61其中 a,b,c 可

3、以取 1,2,3,4,5,6 這幾個自然數(shù)中的任一個.顯然 ..若記 n( B)為集合 B 中 A A i41 i ? ? ?元素的個數(shù)，則由集合論的知識得. ? ? ?? ? ? ? ? ? ? ?? ? ? ?41 i 4 j i 1 4 k j i 14 3 2 1 k j i j i i ) A A A A ( n ) A A A ( n ) A A ( n ) A ( n ) A ( n432 6 2 ) A ( n ) A

4、( n ) A ( n ) A ( n 34 3 2 1 ? ? ? ? ? ?A1A2 的槽數(shù)高為 161ab 或 616ab,故 n(A1A2)=2×62=72，同理 n(A2A3)=n(A3A4)=72.A1A3 為1616a,或 1661a,或 6116a,或 6161a,故 n(A1A3)=24 同理 n(A1A4)=24,n(A2A4)=24.A1A2A3 的槽高為 1616a 或 6161a,故 n(A1A2A3

5、)=2×6=12.同理 n(A2A3A4)=12.A1A2A4 的槽高為 16116,或16161,或 61616 或 61661,故 n(A1A2A4)=4 同理 n(A1A3A4)=4.A1A2A3A4 的槽高為 16161 或61616，故 n(A1A2A3A4)=2.故 n4=n(A)=432×4-3×72-24×3+12×2+4×2-2=1470.5 個槽中僅有兩個高

6、度，且相鄰高差為 5 的鎖具個數(shù)為 n5=25-2=30.最后可以得到一批鎖具的個數(shù)為n1-n2-n3-n4-n5=5880所以每批鎖具有 5880 把，可以裝 98 箱。1．計算機求解 計算機求解設(shè) 5 個槽高為 i1,i2,i2,i4,i5,對它們從 1 到 6 進行循環(huán)。為除掉高差為 5 的情況，可以用max{|i1-i2|,|i2-i3|,|i3-i4|,|i4-i5|}>4.5進行判斷。為除去僅一個槽高的情況,可以用|i

7、1-i2|+|i2-i3|+|i3-i4|+|i4-i5|}0.5 時令 a2=i2,否則當|i2-i3|>0.5 時令奇類中鎖具數(shù)=偶類中鎖具數(shù)= 2940 25880 ?故奇類和偶類中的鎖具數(shù)都為 1940 件.(3)裝箱的標記基于以下討論,我們可得到如下方案:①生產(chǎn)鎖具過程中記錄每個鑰匙槽的高度,從而確定 H 的奇偶性,將生產(chǎn)出來的鎖具分奇類和偶類.①將奇類和偶類分別裝為 49 箱并做”奇”和”偶”的標志.這樣,銷售部門可以

8、根據(jù)所做標記只選同類的箱子售給團體顧客.只要他們一次購買的箱數(shù)不超過 49 箱(即 2940 個鎖具),我們就可以保證他們的鎖具不會有互開現(xiàn)象,他們也就不會抱怨了.但按槽高之和的奇偶分類是不是最優(yōu)方案,即能否找到更好的分類裝箱方案,使不可互開的鎖具個數(shù)大于 2940.所給方案最優(yōu)性的證明可以通過圖論知識和計算機實現(xiàn).2.圖論基礎(chǔ)知識 圖論基礎(chǔ)知識(1)圖的概念圖 G 是節(jié)點集 V 和邊集 E 組成的偶對,即 G-(V,E).圖是描述現(xiàn)實

9、世界中事物及其聯(lián)系的一種數(shù)學形式,它有著廣泛的應(yīng)用背景和重要的理論價值.近年來隨著計算機的普及獲得了迅速的發(fā)展.二分圖(bipartite graph)是一種特殊圖 G=(V,E),它的節(jié)點集可以分為兩個互不相交的點集 V1 和 V2,且它的任一條邊必是邊接 V1 和 V2 中的兩個節(jié)點.即 V=V1∪V2,V1≠⊙,V2≠⊙,V1∩V2=⊙,且若 e=(υ1, υ2)∈E,則υ1∈v1, υ1∈V2.二分圖研究的一個重要方面是匹配（

10、matching）問題，它在“婚姻”問題、指派問題、 “相異代表系”問題等方面有著非常重要的實際意義。 二分圖 G=（V，E）的邊集 E 的一個子集 M E 稱為它的一個匹配是指 M 中的任意兩條邊都沒有公共節(jié)點。M 中邊的個數(shù)定義為 M 的基數(shù),,記為|M|.M 中的邊所連接的所有節(jié)點稱為關(guān)于 M 的飽和節(jié)點,若υ∈V 且沒有 M 中的邊與υ相連,則稱υ為關(guān)于 M 的非飽和節(jié)點,設(shè) M 是二分圖 G=(V,E)的一個匹配,若不能增添

11、 E 中邊使 M 仍然為 G 的匹配,則稱 M為 G 的一個極大匹配.所有 G 的極大匹配中基數(shù)最大的匹配稱 G 的最大匹配.在實際應(yīng)用及圖論研究中最感興趣的問題是二分圖的完全匹配(complete matching)和完善匹配(perfect matching).若 M 是 G 的一個匹配,且 V1(或 V2)中的所有節(jié)點關(guān)于 M 飽和,則稱 M 是 G 的一個完全匹配.若 V 中的所有節(jié)點關(guān)于匹配 M 飽和,則稱 M 是 G 的一

12、個完美匹配.完美匹配存在的一個必要條件是節(jié)點集 V1 與 V2 的基數(shù)相等,即|V1|=|V2|.(2)匹配存在性的幾個主要定理先引入交錯路的概念.設(shè) M 是二分圖 G=(V,E)的一個匹配,P 是 G 中的一條路徑,如果 P的邊交錯在 M 和 E\M 中出現(xiàn),則稱 P 是 G 中的一條 M-交錯路.起點和終點都是 G 關(guān)于 M 的非飽和點的交錯路稱為一條 M-可擴路.匹配 M 是圖 G 的最大匹配條件由下面的定理給出:定理 定理 12

13、.2 M 是 G 的最大匹配的充分必要條件是 G 不含 M-可擴路。 證 設(shè) M 是 G 的匹配,并假設(shè) G 包含 M 可擴路υ0υ1…υ2m+1,定義 M＇E 為M＇=(M\{υ1υ2, υ3υ4…, υ2m-1υ2m})∪{υ0υ1, υ2υ3…, υ2mυ2m-1 }.則 M＇是 G 匹配,且| M＇|=|M|+1.因而 M 就不是最大匹配.反之,假設(shè) M 不是最大匹配,且令 M＇是 G 的最大匹配,則| M＇|>|M|