例谈算两次思想在组合学中的应用

●许康华 (富阳市第二中学 浙江富阳 311400) ●何文明 (富阳中学 浙江富阳 311400)

设 A={a1，a2，…，am}，B={b1，b2，…，bn}是 2个有限集合，集合{(ai，bj)|1≤i≤m，1≤j≤n}，叫做集合A与B的笛卡尔乘积，并记为A×B.

设S是A×B的一个子集，我们可用2种方法计算|S|.

对于给定的ai∈A，S中所有含有 ai的对子(ai，b)的集合记为 S(ai，·).显然，当 ai≠aj时，S(ai，·)∩S(aj，·)= φ，

且 S=S(a1，·)∪S(a2，·)∪…∪S(am，·)，因此

另一方面，对于给定的bj∈B，定义S(·，bj)为S中所有含有bj的对子(a，bj)的集合，同理有

由式(1)，式(2)，得

这个等式叫做富比尼(Fubini)原理，又叫做算两次原理.

本文主要介绍用算两次的方法来解决组合数中的一些竞赛题：对同一对象从2种不同的角度去进行计算，从而寻找到解决问题的途径.在算两次中，常要考虑的计算对象有：数、点、元素、交点、对子、子集等.

例1 一所大学有10 001名学生，一些学生一起参加并成立了几个俱乐部(一个学生可以属于不同的俱乐部)，有些俱乐部一起加入并成立了几个社团(一个俱乐部可以属于不同的社团).已知共有k个社团，假设满足下列条件：

(1)每一对学生(即任意2个学生)都恰属于一个俱乐部;

(2)对于每个学生和每个社团，这个学生恰属于这个社团的一个俱乐部;

(3)每个俱乐部有奇数个学生，且有2m+1个学生的俱乐部恰属于m个社团，其中m是正整数，求k的所有可能值.

(2004年第45届IMO预选题)

解用n代替10 001，a，R，S分别表示一个学生、一个俱乐部和一个社团，我们称满足a∈R，R∈S的有序三元组(a，R，S)为“可接受的”.

固定一个学生a和一个社团S，由条件(2)，可知有唯一的俱乐部R，使得(a，R，s)是可接受的三元组.又因为有序二元组(a，S)有nk种取法，所以可接受的三元组共有nk个.

(1998年第39届IMO试题)

证明如果2个裁判对某个参赛者有相同的评判，我们称其为一个“对子”.

一方面，着眼于裁判：由题设，任意2个裁判最多对k个参赛者有相同的评判，即任意2个裁判最多产生k个“对子”，可得

“对子”的总数≤kC2b.

另一方面，着眼于参赛者：对任意一个参赛者，设有A个裁判判他通过，而B个裁判判他不及格，其中A+B=b.则对于这个参赛者，有关他的“对子”个数为

例3 设A是一个有n个元素的集合，A的m个子集 A1，A2，…，Am两两互不包含，试证：

(1993年全国高中数学联赛试题)

一方面，将A的n个元素作全排列，其不同的排列总数有n!个.

另一方面，将子集Ai的|Ai|个元素排在前|Ai|个位置，子集Ai的余集的元素排在后n-|Ai|个位置，即成排列

这样的排列共有|Ai|!(n-|Ai|)!个，它们全包含在全排列数n!中.

以下只要说明，以 m个集合 A1，A2，…，Am中的元素排在前面，它们的对应余集中的元素排在后面的各个排列之间，在题设条件之下，没有2个是相同的.

这就证明了结论(1).

注：本题源自著名的 Sperner定理(Sperner，1928)：

当然这一切，我都没有告诉黄玲。我们时常一起上班，一起下班走那段昏暗的小巷子。旁边的大楼都已经竣工，这使我想起那次被抢劫的遭遇，对黄玲说，其实如果那天你不出现，我就撒手了，他们只是两个月没领到工资的民工，不是什么坏人。

关于Sperner定理及其推广，可参见单墫教授的《集合及其子集》.

例4 有n个人，已知他们中的任意2个人至多通电话1次，他们中的任意n-2个人之间通电话的总次数相等，都是3k次，其中k是自然数.求n的所有可能值.

(2000年全国高中数学联赛试题)

其中l为自然数，即

例5 一群科学家在一个研究所工作.在某天的8小时工作时间内，每个科学家都至少去过一次咖啡厅.已知对于每2个科学家，恰有他们中的一个出现在咖啡厅中的时间总和至少为x(x＞4)小时.求出在研究所中工作的科学家人数的最大可能值(依赖于x).

若 n 为偶数，n=2l，则

若 n为奇数，n=2l+1，则

下面举例说明不等式可以取到等号.

(2005年第46届IMO试题)

若记nr(0≤r≤6)为恰好答对r道试题的参赛者的人数，则

考虑到对于一个恰好答对r道试题的参赛者，他对式(3)中的和S的贡献为(当 r＜2时，=0)，所以

由式(3)，式(4)，可得

由题设，得n6=0，因此式(5)为此这些pij不可能全相等.于是，其中有14个为λ，1个为λ+1.

设(i0，j0)，使得pi0j0=λ+1.答对5道题的参赛者称为“优胜者”.

不失一般性，不妨设优胜者没有答对第6题，且 i0，j0不为 1，于是

考虑和式

因为除优胜者外每个参赛者都恰好答对了4题，所以若有x个参赛者答对了第6题，则他们中的每一个对S'的贡献是3;有y个参赛者答对了第1题(除优胜者外)，他们中的每一个对S″的贡献为3，而优胜者对S″的贡献为4，于是

而pi0j0不在S″中出现，所以

故S'为5λ 或5λ +1.从而