Question

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

Answer 1

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

另一方面，令

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

于是n＝217．