1、鎖具裝箱問題（1994年B題） 某廠生產(chǎn)一種彈子鎖具，每個鎖具的鑰匙有 5 個槽，每個槽的高度從1，2，3，4，5，66個數(shù)（單位略）中任取一數(shù)。由于工藝及其它原因，制造鎖具時對5 個槽的高度還有兩個限制： 至少有3 個不同的數(shù)； 相鄰兩槽的高度之差不能為5。 滿足以上條件制造出來的所有互不相同的鎖具稱為一批。 從顧客的利益出發(fā)，自然希望在每批鎖具中“一把鑰匙開一把鎖”。但是在當(dāng)前工藝條件下，對于同一批中兩個鎖是否能夠互開，有以下試驗結(jié)果： 若二者相對應(yīng)的5 個槽的高度中有4 個相同，另一個槽的高度差為1，則可能互開； 在其它情形下，不可能互開。 原來，銷售部門在一批鎖具中隨意的取60 個裝一

2、箱出售。團體顧客往往購買幾箱到幾十箱，他們抱怨購得的鎖具會出現(xiàn)互開的情形。現(xiàn)聘你為顧問，回答并解決以下的問題： 1） 每一批鎖具有多少個，裝多少箱。 2） 為銷售部門提出一種方案，包括如何裝箱（仍是 60 個鎖具一箱），如何給箱子以標(biāo)志，出售時如何利用這些標(biāo)志，使團體顧客不再或減少抱怨。 3） 采取你提出的方案，團體顧客的購買量不超過多少箱，就可以保證一定不會出現(xiàn)互開的情形。 4） 按照原來的裝箱辦法，如何定量地衡量團體顧客抱怨互開的程度（試對購買一、二箱者給出具體結(jié)果）。 1、 每一批鎖具有多少個，裝多少箱。, 5,6 , 5 , 4 , 3 , 2 , 1),(V54321154321中至

3、少有三個相異且hhhhhhhhhhhhhiii5 , 4 , 3 , 2 , 1,6 , 5 , 4 , 3 , 2 , 1),(C54321ihhhhhhi,6 , 5 , 4 , 3 , 2 , 1),(A5432154321中至多有兩個相異且hhhhhhhhhhhi5),(B154321iihhihhhhh使，存在BACV4321BDDDD5),(D154321iiihhhhhhhi=1,2,3,4i=1,2,3,4 2、為銷售部門提出一種方案，包括如何裝箱（仍是 60 個鎖具一箱），如何給箱子以標(biāo)志，出售時如何利用這些標(biāo)志，使團體顧客不再或減少抱怨 構(gòu)造圖G，以一批鎖具的全體為頂點，兩

4、頂點連邊當(dāng)且僅當(dāng)對應(yīng)的鎖具互開。稱圖G為互開圖。 命題：互開圖為二部圖，其劃分為),(X5154321是奇數(shù)iihhhhhh),(Y5154321是偶數(shù)iihhhhhh 結(jié)論：對同一批鎖具，將槽高之和為奇數(shù)、偶數(shù)的分別裝箱，并做“奇”（或1）“偶”（或0）的標(biāo)志，只要購買不超過？箱時，可保證不會出現(xiàn)互開的情況。裝箱、標(biāo)志和銷售方案 每批鎖具按槽高之和I分組，顯然I=8,9,.,27，即共分20組。設(shè)各組的鎖具個數(shù)為J(I)，通過編程算出J(I)的具體值。 兩鎖具互開，則二者必分別屬于I值相鄰的兩組。將I值為偶數(shù)的各組按上表順序裝49箱，并用I值標(biāo)記，如：箱號箱號1 12 23 34 4.484

5、84949標(biāo)志標(biāo)志08100810001000101012101200120012.0024002424262426第一箱裝第一箱裝I=8I=8的的2020個，I=10I=10的的4040個，標(biāo)志個，標(biāo)志08100810；第二箱裝第二箱裝I=60I=60的的6060個，標(biāo)志個，標(biāo)志00100010；其余類推。對；其余類推。對I I為奇數(shù)的類似標(biāo)志。為奇數(shù)的類似標(biāo)志。 出售時，當(dāng)購買不超過49箱時，只售出標(biāo)志為偶數(shù)者，且標(biāo)志要互不相同?；蛘咂媾级加袝r，其奇標(biāo)志與偶標(biāo)志的前兩位，后兩位，不能相差1。任意裝箱造成的抱怨度 從一批鎖具中隨機取60個裝一箱，120個裝一箱，.，抱怨度可用所購的一箱或兩箱鎖具中平均有多少對互開來衡量。 由于互開圖的邊數(shù)為？，而完全圖K5880的邊數(shù)為？，故任兩鎖具互開的概率為？，所以一箱鎖具的平均互開對數(shù)為？。 兩箱鎖具的互開對數(shù)為？ 一般地，k箱鎖具的平均互開對數(shù)為？任意裝箱造成的抱怨度 從一批鎖具中隨機取60個裝一箱，120個裝一箱，.，抱怨度可用所購的一箱或兩箱鎖具中平均有多少對互開來衡量。 由于互開圖的邊數(shù)為22778，而完全圖K5880的邊數(shù)為 ，故任兩鎖具