●許康華 (富陽(yáng)市第二中學(xué) 浙江富陽(yáng) 311400) ●何文明 (富陽(yáng)中學(xué) 浙江富陽(yáng) 311400)

設(shè) A={a1，a2，…，am}，B={b1，b2，…，bn}是 2個(gè)有限集合，集合{(ai，bj)|1≤i≤m，1≤j≤n}，叫做集合A與B的笛卡爾乘積，并記為A×B.

設(shè)S是A×B的一個(gè)子集，我們可用2種方法計(jì)算|S|.

對(duì)于給定的ai∈A，S中所有含有 ai的對(duì)子(ai，b)的集合記為 S(ai，·).顯然，當(dāng) ai≠aj時(shí)，S(ai，·)∩S(aj，·)= φ，

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

另一方面，對(duì)于給定的bj∈B，定義S(·，bj)為S中所有含有bj的對(duì)子(a，bj)的集合，同理有

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

這個(gè)等式叫做富比尼(Fubini)原理，又叫做算兩次原理.

本文主要介紹用算兩次的方法來解決組合數(shù)中的一些競(jìng)賽題：對(duì)同一對(duì)象從2種不同的角度去進(jìn)行計(jì)算，從而尋找到解決問題的途徑.在算兩次中，常要考慮的計(jì)算對(duì)象有：數(shù)、點(diǎn)、元素、交點(diǎn)、對(duì)子、子集等.

例1 一所大學(xué)有10 001名學(xué)生，一些學(xué)生一起參加并成立了幾個(gè)俱樂部(一個(gè)學(xué)生可以屬于不同的俱樂部)，有些俱樂部一起加入并成立了幾個(gè)社團(tuán)(一個(gè)俱樂部可以屬于不同的社團(tuán)).已知共有k個(gè)社團(tuán)，假設(shè)滿足下列條件：

(1)每一對(duì)學(xué)生(即任意2個(gè)學(xué)生)都恰屬于一個(gè)俱樂部;

(2)對(duì)于每個(gè)學(xué)生和每個(gè)社團(tuán)，這個(gè)學(xué)生恰屬于這個(gè)社團(tuán)的一個(gè)俱樂部;

(3)每個(gè)俱樂部有奇數(shù)個(gè)學(xué)生，且有2m+1個(gè)學(xué)生的俱樂部恰屬于m個(gè)社團(tuán)，其中m是正整數(shù)，求k的所有可能值.

(2004年第45屆IMO預(yù)選題)

解用n代替10 001，a，R，S分別表示一個(gè)學(xué)生、一個(gè)俱樂部和一個(gè)社團(tuán)，我們稱滿足a∈R，R∈S的有序三元組(a，R，S)為“可接受的”.

固定一個(gè)學(xué)生a和一個(gè)社團(tuán)S，由條件(2)，可知有唯一的俱樂部R，使得(a，R，s)是可接受的三元組.又因?yàn)橛行蚨M(a，S)有nk種取法，所以可接受的三元組共有nk個(gè).

(1998年第39屆IMO試題)

證明如果2個(gè)裁判對(duì)某個(gè)參賽者有相同的評(píng)判，我們稱其為一個(gè)“對(duì)子”.

一方面，著眼于裁判：由題設(shè)，任意2個(gè)裁判最多對(duì)k個(gè)參賽者有相同的評(píng)判，即任意2個(gè)裁判最多產(chǎn)生k個(gè)“對(duì)子”，可得

“對(duì)子”的總數(shù)≤kC2b.

另一方面，著眼于參賽者：對(duì)任意一個(gè)參賽者，設(shè)有A個(gè)裁判判他通過，而B個(gè)裁判判他不及格，其中A+B=b.則對(duì)于這個(gè)參賽者，有關(guān)他的“對(duì)子”個(gè)數(shù)為

例3 設(shè)A是一個(gè)有n個(gè)元素的集合，A的m個(gè)子集 A1，A2，…，Am兩兩互不包含，試證：

(1993年全國(guó)高中數(shù)學(xué)聯(lián)賽試題)

一方面，將A的n個(gè)元素作全排列，其不同的排列總數(shù)有n!個(gè).

另一方面，將子集Ai的|Ai|個(gè)元素排在前|Ai|個(gè)位置，子集Ai的余集的元素排在后n-|Ai|個(gè)位置，即成排列

這樣的排列共有|Ai|!(n-|Ai|)!個(gè)，它們?nèi)谌帕袛?shù)n!中.

以下只要說明，以 m個(gè)集合 A1，A2，…，Am中的元素排在前面，它們的對(duì)應(yīng)余集中的元素排在后面的各個(gè)排列之間，在題設(shè)條件之下，沒有2個(gè)是相同的.

這就證明了結(jié)論(1).

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

當(dāng)然這一切，我都沒有告訴黃玲。我們時(shí)常一起上班，一起下班走那段昏暗的小巷子。旁邊的大樓都已經(jīng)竣工，這使我想起那次被搶劫的遭遇，對(duì)黃玲說，其實(shí)如果那天你不出現(xiàn)，我就撒手了，他們只是兩個(gè)月沒領(lǐng)到工資的民工，不是什么壞人。

關(guān)于Sperner定理及其推廣，可參見單墫教授的《集合及其子集》.

例4 有n個(gè)人，已知他們中的任意2個(gè)人至多通電話1次，他們中的任意n-2個(gè)人之間通電話的總次數(shù)相等，都是3k次，其中k是自然數(shù).求n的所有可能值.

(2000年全國(guó)高中數(shù)學(xué)聯(lián)賽試題)

其中l(wèi)為自然數(shù)，即

例5 一群科學(xué)家在一個(gè)研究所工作.在某天的8小時(shí)工作時(shí)間內(nèi)，每個(gè)科學(xué)家都至少去過一次咖啡廳.已知對(duì)于每2個(gè)科學(xué)家，恰有他們中的一個(gè)出現(xiàn)在咖啡廳中的時(shí)間總和至少為x(x＞4)小時(shí).求出在研究所中工作的科學(xué)家人數(shù)的最大可能值(依賴于x).

若 n 為偶數(shù)，n=2l，則

若 n為奇數(shù)，n=2l+1，則

下面舉例說明不等式可以取到等號(hào).

(2005年第46屆IMO試題)

若記nr(0≤r≤6)為恰好答對(duì)r道試題的參賽者的人數(shù)，則

考慮到對(duì)于一個(gè)恰好答對(duì)r道試題的參賽者，他對(duì)式(3)中的和S的貢獻(xiàn)為(當(dāng) r＜2時(shí)，=0)，所以

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

由題設(shè)，得n6=0，因此式(5)為此這些pij不可能全相等.于是，其中有14個(gè)為λ，1個(gè)為λ+1.

設(shè)(i0，j0)，使得pi0j0=λ+1.答對(duì)5道題的參賽者稱為“優(yōu)勝者”.

不失一般性，不妨設(shè)優(yōu)勝者沒有答對(duì)第6題，且 i0，j0不為 1，于是

考慮和式

因?yàn)槌齼?yōu)勝者外每個(gè)參賽者都恰好答對(duì)了4題，所以若有x個(gè)參賽者答對(duì)了第6題，則他們中的每一個(gè)對(duì)S'的貢獻(xiàn)是3;有y個(gè)參賽者答對(duì)了第1題(除優(yōu)勝者外)，他們中的每一個(gè)對(duì)S″的貢獻(xiàn)為3，而優(yōu)勝者對(duì)S″的貢獻(xiàn)為4，于是

而pi0j0不在S″中出現(xiàn)，所以

故S'為5λ 或5λ +1.從而