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．