Question

設S＝{1，2，3，…，280}．求最小的自然數n使得S的每個有n個元素的子集都含有5個兩兩互素的數．

Answer 1

解析：令A_i＝｛S中一切可被i整除的自然數｝，i＝2，3，5，7．記A＝A₂∪A₃∪A₅∪A₇，利用容斥原理，容易算出A中元素的個數是216．由于在A中任取5個數必有兩個數在同一個A_i之中，從而他們不互素．于是n≥217．

另一方面，令

B₁＝(1和S中的一切素數｝

B₂＝(2²，3²，5²，7²，11²，13²｝

B₃＝｛2×131，3×89，5×53，7×37，11×23，13×19｝

B₄＝｛2×127，3×83，5×47，7×31，11×19，13×17｝

B₅＝{2×113，3×79，5×43，7×29，11×17}

B₆＝{2×109，3×73，5×41，7×23，11×13}

易知B₁中元素的個數為60．令B＝B₁∪B₂∪B₃∪B₄∪B₅∪B₆，則B中元素的個數為88，S－B中元素的個數為192．在S中任取217個數，由于217－192＝25＞4×6，于是存在i(1≤i≤6)，使得這217個數中有5個數在Bi中．顯然這5個數是兩兩互素的，所以n≤217．

于是n＝217．