Question

【題目】設(shè)、是兩個正整數(shù)（允許與相等），、是兩個由若干個實數(shù)組成的集合，且，（允許），集合滿足：若、、、，且，則或且，或（且）.定義一個集合.試求出的最小可能值（表示集合的元素個數(shù)）.

Answer 1

【答案】

【解析】

記，.

列表如下（見表1）.

表1

在表1中，與的交匯處所填的數(shù)為，共形成個數(shù).現(xiàn)在要從這個數(shù)中刪去數(shù)值相等的數(shù)，使得剩下的數(shù)兩兩不等.顯然每一行個數(shù)兩兩不等，每一列的個數(shù)也兩兩不等.

引理：在表1中任何兩行之中（共個數(shù)）不可能有兩對數(shù)分別對應(yīng)相等.

引理的證明：用反證法.

考慮、 這兩行，假設(shè)，

且（且），那么，

即.

再由題設(shè)中的性質(zhì)得，或

且或（且）.

由前者得到，從而，，這與前面假定矛盾.

由后者得到且.（因為，所以，）.

從而，，,

這與前面假定矛盾.

回到原題.

由引理知，任何兩行中至多刪去一個數(shù)（在兩個相等的數(shù)中只刪去其中的一個數(shù)），

所以，表1中至多刪去個數(shù).使得至少剩下的個數(shù)兩兩不等，即.

（1）當(dāng)時，取，且，具有題設(shè)中的性質(zhì)，這時有，所以，的最小值是（當(dāng)時）.

（2）當(dāng)時，考慮表2.

表2

注意到所在的行與所在的列組成一個正方形（用黑框標(biāo)出），余下是一個的矩形該矩形的第列上的各個數(shù)分別是.

記，，則由（1）的結(jié)論知

（當(dāng)時）.

另外，可以舉例說明上面不等式的等號可以成立.所以，的最小值為（當(dāng)時）.

綜上所述，可知

注：當(dāng)時，.