Question

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

Answer 1

【答案】

【解析】

記，.

列表如下（見表1）.

表1

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

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

引理的證明：用反證法.

考慮、 這兩行，假設，

且（且），那么，

即.

再由題設中的性質得，或

且或（且）.

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

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

從而，，,

這與前面假定矛盾.

回到原題.

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

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

（1）當時，取，且，具有題設中的性質，這時有，所以，的最小值是（當時）.

（2）當時，考慮表2.

表2

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

記，，則由（1）的結論知

（當時）.

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

綜上所述，可知

注：當時，.