化简后  则有
2）任两位学生的“面试组”没有三位面试老师相同的情形
和最多一位面试老师相同的情形类似，此时每个学生的面试组中四个教师（四个点）必须满足任两个之间没有相同的三个教师（三个点）。而任意三个点正好是四面体的一个面。于是最多两位面试老师相同的问题可以看作是在完全图 中选取N个四面体使两两之间没有公共面。每个四面体有四个面，而 中有个面，得 ，即
解得至少需要 个教师
3.3运用组合数学知识求解
运用组合数学中平衡不完全区组设计（BIBD）[1]的概念和方法对问题进行求解。
3.3.1平衡不完全区组设计（BIBD）：
设 是v个元素的集。B1,B2,…Bb,是b个k-子集组成的族（也叫做区组）合于下列条件：
1. 每一元素在b个区组的恰恰r个出现；
2. 每两个元在b个区组的恰恰 个中同时出现；
3. k
则称为均衡不完全区间设计，简记为（b,v,r,k,）或BIBD（v，k，）
3.3.2（b,v,r,k,）中参数的基本关系和两个必要条件：
基本关系：; ;
必要条件：; ;
证明：从v个不同的元素中任意取k个元素构成 k-子集组合数为：
…………………………(1)
此时任意一个元素出现的次数为
 …………(2)
任意一个元素同时出现的区组中次数为:
 ……………(3)
如果要求从任意一对元素出现在区间中的次数为λ次，（λ≤λ0），则不难看出, k-子集数要减少为原来的λ/λ0即：
 ……………………………(4)
此时任意一个元素出现的次数也相应的减少为原来的λ/λ0,即：
 ……………………(5)
(4)(5)是(b,v,r,k,）参数的基本关系，由(4)(5)立即可以推出两个必要条件。
如果将每个教师都看成一个点，共有M个点，教师集合 ，每个学生的面试组是从中选取4个点构成的4长区组。任意两个不同老师（ 中的两个点）都在4长区组出现且仅出现一次，即分配方案中中的两个点在N个区组中恰恰＝1次出现；对任意老师i来说，他与其它老师两两组合的2-子集共有(M-1)种，若学生j的“面试组”出现老师i，在该组中与i老师两两组合共有3种情形，则该老师面试的学生数为(M-1)/3，由于老师i是任意选择的，所以其它所有老师面试的学生数也为(M-1)/3。则中的每个点在N个区组中出现的次数相同；由于N>1，显然，老师数M＞４，即k
在本问题中任两位学生的“面试组”没有两位面试老师相同的情形是BIBD（M，4，1）；任两位学生的“面试组”没有三位面试老师相同的情形是BIBD（M，4，2）。根据BIBD的参数必要条件得到教师和学生人数的关系。
3.3.3 定理3：没有两位面试老师相同时 ；没有三位面试老师相同时
证明：根据BIBD（M，4，1）的参数必要条件得到：
计算得出：
在非理想状态下，老师的资源受约束条件的限制而没有得到最大限度的利用，所以老师的数量比上式计算出的值大。综合以上情况，得到；
根据BIBD（M，4，2）的参数必要条件得到：
得到M(M-1)(M-2)=24N。
解得
在非理想状态下M的下界为上式等号右边的式子。
4.结论
从问题的分析与求解中看出虽然数据拟合、图论和组合数学中平衡不完全区组设计（BIBD）的三种方法虽然方法不同，处理角度各异。但都能找到面试中教师人数的上界。都是好方法。尤其是图论和BIBD的方法显得尤为简单。
参考文献
[1] Brualdi, 冯舜玺，罗平，卢开澄等．组合数学．北京：机械工业出版社，2004，231～239
[2] Douglas B West,李建中，骆吉洲．图论导引．北京：机械工业出版社，2006，171～183
The least numbers of teacher in the recruitstudents problem
Zhang hao
1.School of Mathematics and ComputerScience; Nanjing Normal University; Nanjing 210097
2.Institute of mathematica ; NanjingInstitute of Technology; 211167
2/2 首页 上一页 1 2 |
