Question

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

Answer 1

【答案】100

【解析】

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

例子：令，

.

則中共有個(gè)不同的元素.

而

共有個(gè)不同的元素.

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

用反證法證明.

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

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

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

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

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

則.

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

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