Question

給定整數，證明：存在n個互不相同的正整數組成的集合S，使得對S的任意兩個不同的非空子集A，B，數
 與 
是互素的合數．（這里與分別表示有限數集的所有元素之和及元素個數．）

Answer 1

見解析

我們用表示有限數集X中元素的算術平均．
第一步，我們證明，正整數的n元集合具有下述性質：對的任意兩個不同的非空子集A，B，有．
證明：對任意，，設正整數k滿足
，                        ①
并設l是使的最小正整數．我們首先證明必有．
事實上，設是A中最大的數，則由，易知A中至多有個元素，即，故．又由的定義知，故由①知．特別地有．
此外，顯然，故由l的定義可知．于是我們有．
若，則；否則有，則

．
由于是A中最大元，故上式表明．結合即知．
現在，若有的兩個不同的非空子集A，B，使得，則由上述證明知，故，但這等式兩邊分別是A，B的元素和，利用易知必須A=B，矛盾．
第二步，設K是一個固定的正整數，，我們證明，對任何正整數x，正整數的n元集合具有下述性質：對的任意兩個不同的非空子集A，B，數與是兩個互素的整數．
事實上，由的定義易知，有的兩個子集，滿足，，且
．           ②
顯然及都是整數，故由上式知與都是正整數．
現在設正整數d是與的一個公約數，則是d的倍數，
故由②可知，但由K的選取及的構作可知，是小于K的非零整數，故它是的約數，從而．再結合及②可知d=1，故與互素．
第三步，我們證明，可選擇正整數x，使得中的數都是合數．由于素數有無窮多個，
故可選擇n個互不相同且均大于K的素數．將中元素記為，
則，且（對），
故由中國剩余定理可知，同余方程組
，
有正整數解．
任取這樣一個解x，則相應的集合中每一項顯然都是合數．結合第二步的結果，這一n元集合滿足問題的全部要求．