1994年B题锁具装箱问题的参考解答

1、1994年B题锁具装箱问题的参考解答一、 每批锁的把数锁具装箱的第一问完全是一个数学问题，可以用不同的方法去解决.1. 排列组合法 首先可以求出有5个槽、每个槽有6个高度的所有可能的个数为n1=65=777.6.为了满足题目中提出的至少有三个不同的高度，且相邻高差不应为5的要求，我们应该减去不满足要求的锁具。仅有一个槽高的锁具数目为 n2=.仅有二个槽高的锁具数目为 n3=(25-2)=450下面要考察相邻槽高之差为5的锁具，为了方便，记相邻槽高之差为5的锁具集合记为A，将A分解为以下4种集合：A1： 16abc 或 61abcA2： a16bc 或 a61bcA3： ab16c 或 ab61

2、cA4： abc 16 或 abc61其中a,b,c可以取1,2,3,4,5,6这几个自然数中的任一个.显然.若记n( B)为集合B中元素的个数，则由集合论的知识得.A1A2的槽数高为161ab或616ab,故n(A1A2)=262=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)=26=12.同理n(A2A3A4)=12.A1A2A4的槽高为16116,或16161,或61616或61661,故n

3、(A1A2A4)=4同理n(A1A3A4)=4.A1A2A3A4的槽高为16161或61616，故n(A1A2A3A4)=2.故n4=n(A)=4324-372-243+122+42-2=1470. 5个槽中仅有两个高度，且相邻高差为5的锁具个数为n5=25-2=30.最后可以得到一批锁具的个数为n1-n2-n3-n4-n5=5880所以每批锁具有5880把，可以装98箱。1 计算机求解 设5个槽高为i1,i2,i2,i4,i5,对它们从1到6进行循环。为除掉高差为5的情况，可以用max|i1-i2|,|i2-i3|,|i3-i4|,|i4-i5|4.5进行判断。为除去仅一个槽高的情况,可以用

4、|i1-i2|+|i2-i3|+|i3-i4|+|i4-i5|0.5时令a2=i2,否则当|i2-i3|0.5时令a2=i3,利用|i3-a1|i3-a2|+|i4-a1|i4-a2|+|i5-a1|+|i5-a2|M|置H=GMMM MMM,这时MM表示M和M的对称差(见图12-1) H的每个顶点在H中具有的度不是1就是2.因为它最多只能和M的一条边以及M的边多于M的边.因而必定有H的一条路组成的分支P开始于M的边且终止于M的边,因此P的起点和终点在H中被M所饱和,在图G中就是M非饱和的.于是P是G的一条M可扩路. 设A V1是二分图G=(V,E)的一个子集,N(A)是V2中与A相边的节点的

5、集合,则存在从V1到V2的完全匹配的条件是:定理12.3 G有从V1到V2完全匹配的充要条件是对V1的任意一个子集A V1均有|N(A)|A|证 必要性:设M是V1到V2的完全匹配,则M饱和V1的所有顶点,即对xV1,有yV2,使xyM,故任取A V1，与A相邻的顶点不会少|A|，即|N（A）|A。 充分性：设条件成立，但无从V1到V2的完全匹配，设M*是G最大匹配，则至少有一个V1它是M*的非饱和点，令P是通过M*交错路与相连接的所有顶点集，由定理12.2, 是P中唯一的M*非饱和顶点(见图12-2),令X=PV1 Y= PV2显然,X与Y匹配|Y|=|X|-1而且 N(X) Y,(事实上N(X)=Y)因为N(X)中的每个顶点均由一个M*交错路连接到,但是N(X)=|X|-10，此时顾客的抱怨被避免；当4