Question

【题目】设、是两个正整数（允许与相等），、是两个由若干个实数组成的集合，且，（允许），集合满足：若、、、，且，则或且，或（且）.定义一个集合.试求出的最小可能值（表示集合的元素个数）.

Answer 1

【答案】

【解析】

记，.

列表如下（见表1）.

表1

在表1中，与的交汇处所填的数为，共形成个数.现在要从这个数中删去数值相等的数，使得剩下的数两两不等.显然每一行个数两两不等，每一列的个数也两两不等.

引理：在表1中任何两行之中（共个数）不可能有两对数分别对应相等.

引理的证明：用反证法.

考虑、 这两行，假设，

且（且），那么，

即.

再由题设中的性质得，或

且或（且）.

由前者得到，从而，，这与前面假定矛盾.

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

从而，，,

这与前面假定矛盾.

回到原题.

由引理知，任何两行中至多删去一个数（在两个相等的数中只删去其中的一个数），

所以，表1中至多删去个数.使得至少剩下的个数两两不等，即.

（1）当时，取，且，具有题设中的性质，这时有，所以，的最小值是（当时）.

（2）当时，考虑表2.

表2

注意到所在的行与所在的列组成一个正方形（用黑框标出），余下是一个的矩形该矩形的第列上的各个数分别是.

记，，则由（1）的结论知

（当时）.

另外，可以举例说明上面不等式的等号可以成立.所以，的最小值为（当时）.

综上所述，可知

注：当时，.