Question

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

Answer 1

【答案】100

【解析】

所給集合的元素個數的最小值為100.

例子：令，

.

則中共有個不同的元素.

而

共有個不同的元素.

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

用反證法證明.

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

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

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

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

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

則.

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

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