§5锁具装箱问题 1994年，中国大学生数学建模竞赛B题的 标题是“锁具装箱问题”，题目如下： 某厂生产一种弹子锁具，每把钥匙五个槽， 每槽高度是{1,2,3,4,5,6}中任取的一个 数，且至少有三个不同的高度，相邻两槽高差 不能为5，满足上述条件的所有互不相同的锁 具称为一批。又知两把锁具对应的五个槽中有4 个相同，另一槽高差为1，则两个锁具可以互开， 其余情况不可能互开
§5 锁具装箱问题 1994年，中国大学生数学建模竞赛 B 题的 标题是“锁具装箱问题”，题目如下： 某厂生产一种弹子锁具，每把钥匙五个槽， 每槽高度是{1，2，3，4，5，6}中任取的一个 数，且至少有三个不同的高度，相邻两槽高差 不能为 5， 满足上述条件的所有互不相同的锁 具称为一批。又知两把锁具对应的五个槽中有 4 个相同，另一槽高差为1，则两个锁具可以互开， 其余情况不可能互开
原来，销售部门在一批锁具中随意 取60个装一箱出售，团体顾客往往购买 一箱到几十箱，售出的锁具出现互开情 形时会遭顽客抱怨
原来，销售部门在一批锁具中随意 取60个装一箱出售，团体顾客往往购买 一箱到几十箱，售出的锁具出现互开情 形时会遭顾客抱怨
1)每一批锁具有多少个？装多少箱？ 2)如何给箱子以标志，出售时如何利用这些标 志，排除或减少抱怨？ 3)团体顾客购买多少箱，保证一定不出现抱怨？ 4)按照原来的装箱方法，如何定量地衡量团体 顾客的抱怨程度？
4) 按照原来的装箱方法，如何定量地衡量团体 顾客的抱怨程度？ 1) 每一批锁具有多少个？装多少箱？ 2) 如何给箱子以标志，出售时如何利用这些标 志，排除或减少抱怨？ 3) 团体顾客购买多少箱，保证一定不出现抱怨？
引理1 N=kk2k3k4k5是一个5位数，且至 少有三个互不相同的数字，相邻数字 之差不等于5，其中k∈K={1,2,3,4,5,6, i=1,2,3,4,5,则这种五位数共计5880个。 证 令X={kk2k3k4k5|k∈K,i=1,2,3,4,5), ACX,BCX
N =k1k2k3k4k5 是一个5位数，且至 少有三个互不相同的数字，相邻数字 之差不等于5，其中 k∈K={1, 2, 3, 4, 5, 6}， i = 1, 2, 3, 4, 5，则这种五位数共计5880个。 A Ì X , B Ì X 证 令 X={k1k2k3k4k5| ki ∈ K , i =1, 2, 3, 4, 5}， 引理1
其中，A内的五位数中互不相同 的数字少于3个，B中的五位数存 在相邻数字，其差为5。则所求五位数 的个数为： XI-AUBI=IXI-Al-BI+ANBI 1X1=65=7776,1A=C(6,2)(25-2)+6=456 /B=1470, |A∩B1=25-2=30
其中，A 内的五位数中互不相同 的数字少于 3个，B中的五位数存 在相邻数字，其差为 5。则所求五位数 的个数为： |X|-|A∪B|= |X|-|A|-|B|+|A∩B| |A|=C(6, 2)(25 |X|=65=7776 ， -2)+6=456 |A∩B|=25 |B|=1470， -2= 30
于是 X-AUB|=7776-456-1470+30=5880 即引理1中所称的五位数共计5880个。 结论1每批锁具共计5880个，共装98箱。 定义设V={,2,,V588o,其中V是引 理1中所述的五位数，令 E=vvl v v,eV,i≠j,1≤ij≤5880，Ivrvl=10*, k∈{0,1,2,3,4}
结论1 每批锁具共计5880个，共装98箱。 即引理1中所称的五位数共计5880个。 |X|-|A∪B|=7776-456-1470+30=5880 于是 定义 设 V={v1 , v2 , … , v5880}，其中vi 是引 理1中所述的五位数，令 E={vivj| vi , vj∈V, i≠j, 1≤i, j≤5880, |vi -vj|=10k ， k∈{0, 1, 2, 3, 4}}
以V为项点集，E为边集的图G(V,目 称为互开图。 任互开图上，两顶点相邻当且仅当相应的两个 锁具可以互开。 引理2设X={xX=kk2kk4kEV(G,Bk=0 (mod2)},Y=V(G)-X,则X与Y是互开图中的 独立集，且|X=Y川。 证由于X=kk2k3k4k5,且Bk=0(mod2) 故任给X,X2EX,必有|X1-X2≠10k,即，2 不相邻。所以X是独立集。类似地可以证明Y也 是独立集
在互开图上，两顶点相邻当且仅当相应的两个 锁具可以互开。 以V为顶点集，E为边集的图 G(V, E) 称为互开图。 证 由于 x= k1k2k3k4k5 ，且∑ki=0 (mod 2) ， 故任给 x1 , x2 ∈X，必有 | x1 -x2| ≠10k ，即x1 , x2 不相邻。所以 X 是独立集。类似地可以证明 Y 也 是独立集。 引理2 设 X={x| x= k1k2k3k4k5 ∈V(G)，∑ki=0 (mod 2) }，Y= V(G)- X，则 X 与 Y是互开图中的 独立集，且 |X|=|Y|
任给kk2k3k4k5EY,则 (7-k)(7-k2)(7-k3)(7-k4)(7-k)∈X 即 XI≤Y|,同理可证|Y|≤|XI,故IX=Y 推论1互开图G(V,日是以X与Y为顶 点划分的二部图。 引理3互开图G(V,目有完美匹配。 利用匈牙利算法可以得到互开图的一个完美匹配
任给 k1k2k3k4k5 ∈ Y，则 (7-k1 ) (7-k2 ) (7-k3 ) (7-k4 ) (7-k5 ) ∈X 即 推论1 互开图 G(V, E) 是以 X 与 Y 为顶 点划分的二部图。 |X|≤|Y|，同理可证|Y|≤|X|，故 |X|=|Y|。 引理3 互开图G(V, E) 有完美匹配。 利用匈牙利算法可以得到互开图的一个完美匹配
检洛2对于G(曰，心(G)=2940。 证 由于G是二部图，由Konig定理，其最 大匹配中边的条数等于B(G),由引理3， G有完美匹配，故最大匹配中的边数为 2940,所以B(G=2940,又 x(G)+B(G)=5880, x(G)=5880-B(G)=2940 由以上讨论，我们得到如下结论：
推论2 对于 G(V, E) ，α(G)=2940. 故最大匹配中的边数为 证 由于G 是二部图，由 König 定理，其最 大匹配中边的条数等于β(G)，由引理3， G 有完美匹配， 2940，所以 β(G)=2940，又 α(G) + β(G)=5880， α(G) =5880 –β(G) =2940 由以上讨论，我们得到如下结论：
结论2对于同一批锁具，把每把钥匙 的槽高之和求出来，和为偶数者每60把锁 具装入一箱，且把箱上写0；和为奇数者每 60把装入一箱，且把箱上写1；0字号49箱，1 字号49箱。若顾客购买量不超过49箱，向他出售 全是0号的锁箱或全是1号的锁箱，保证不会出现 抱怨现象。 若一顾客购买量不少于50箱，则应对其严明买走 的锁具出现互开现象不可避免
结论2 对于同一批锁具，把每把钥匙 的槽高之和求出来，和为偶数者每60把锁 具装入一箱，且把箱上写 0 ；和为奇数者每 60把装入一箱，且把箱上写 1 ；0 字号 49箱，1 字号49箱。若顾客购买量不超过49箱，向他出售 全是0号的锁箱或全是1号的锁箱，保证不会出现 抱怨现象。 若一顾客购买量不少于50箱，则应对其严明买走 的锁具出现互开现象不可避免