设S={1,2,3,...,280}.求最小的自然数n,使得S的每个有n个元素的子集含有5个两两互素的数.

Question

设S={1,2,3,...,280}.求最小的自然数n,使得S的每个有n个元素的子集含有5个两两互素的数.

Answer 1

令Ai＝｛S中一切可被i整除的自然数｝,i＝2,3,5,7．记A＝A2∪A3∪A5∪A7,利用容斥原理,容易算出A中元素的个数是216．由于在A中任取5个数必有两个数在同一个Ai之中,从而他们不互素．于是n≥217．
另一方面,令
B1＝(1和S中的一切素数｝
B2＝(22,32,52,72,112,132｝
B3＝｛2×131,3×89,5×53,7×37,11×23,13×19｝
B4＝｛2×127,3×83,5×47,7×31,11×19,13×17｝
B5＝{2×113,3×79,5×43,7×29,11×17}
B6＝{2×109,3×73,5×41,7×23,11×13}
易知B1中元素的个数为60．令B＝B1∪B2∪B3∪B4∪B5∪B6,则B中元素的个数为88,S－B中元素的个数为192．在S中任取217个数,由于217－192＝25＞4×6,于是存在i(1≤i≤6),使得这217个数中有5个数在Bi中．显然这5个数是两两互素的,所以n≤217．
于是n＝217．