Question

【題目】1998名運(yùn)動(dòng)員的號(hào)碼依次為1至1998的自然數(shù)．現(xiàn)在要從中選出若干名運(yùn)動(dòng)員參加儀仗隊(duì)，使得剩下的運(yùn)動(dòng)員中沒有一個(gè)人的號(hào)碼等于另外兩人的號(hào)碼的乘積．那么，選為儀仗隊(duì)的運(yùn)動(dòng)員最少有多少人?

Answer 1

【答案】43人

【解析】我們很自然的想到把用得比較多的乘數(shù)去掉，因?yàn)樗鼈儏⑴c的乘式比較多，把它們?nèi)サ粲兄�于使剩下的�?gòu)不成乘式，比較小的數(shù)肯定是用得最多的，因?yàn)樗鼈兊谋稊?shù)最多，所以考慮先把它們?nèi)サ簦�但關(guān)鍵是除到何處?

考慮到44的平方為1936，所以去到44就夠了，因?yàn)槿绻�剩下的�?gòu)成了乘式，那么乘式中最小的數(shù)一定小于等于44，所以可以保證剩下的構(gòu)不成乘式．因?yàn)閷?duì)結(jié)果沒有影響，所以可以將1保留，于是去掉2，3，4，…，44這43個(gè)數(shù)．

但是，是不是去掉43個(gè)數(shù)為最小的方法呢?構(gòu)造2×97，3×96，4×95，…，44×45，發(fā)現(xiàn)這43組數(shù)全不相同而且結(jié)果都比1998小，所以要去掉這些乘式就至少要去掉43個(gè)數(shù)，所以43位最小值，即為所求.