Question

【題目】設是20個兩兩不同的正整數(shù)，且集合中有201個不同的元素.求集合中不同元素個數(shù)的最小可能值.

Answer 1

【答案】100

【解析】

所給集合的元素個數(shù)的最小值為100.

例子：令，

.

則中共有個不同的元素.

而

共有個不同的元素.

下面證明：所給集合的不同元素的個數(shù)不小于100.

用反證法證明.

若存在一個使所給集合的元素個數(shù)小于100的集合.計算的“好子集”的個數(shù)，這里，，且.

對中滿足的數(shù)對（共190對），考慮它們的差，由假設知至多有99個不同的差，故必有至少91個數(shù)對，使得存在，滿足，，且.對這樣的91個數(shù)對，它與其對應的、形成的一個四元集，可以得到的一個好子集，且至多兩個數(shù)對形成相同的子集（只能是或）.故S的好子集至少有46個.

另一方面，的好子集的個數(shù)等于，這里，為中滿足，的數(shù)對的個數(shù).

注意到，對每個，中的每個元素至多出現(xiàn)在上面的一個數(shù)對中（事實上，當時，出現(xiàn)在數(shù)對中，其余情況出現(xiàn)在中），于是，.從而，在時，.故.

由于集合中有201個不同的元素，故使得的正整數(shù)有201個.設為這樣的組成的集合，利用中有對滿足，有20對滿足，故.

則.

這與前面所得到的結(jié)論：的好子集至少有46個矛盾.

因此，所給的集合中，至少有100個不同的元素.