Question

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

Answer 1

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

另一方面，令

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

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

于是n＝217．