数学竞赛每日一练 第10期解答

证明

先证明一个引理：设

则有1≤𝑖<𝑗≤𝑛+1，使得𝑎_(𝑖)∣𝑎_(𝑗)．

引理的证明

反证法，若结论不成立，则对任意1≤𝑖<𝑗≤𝑛+1，有𝑎_(𝑗)不是𝑎_(𝑖)的倍数．

设𝑎_(𝑖)=𝑏_(𝑖)2^(𝑛_(𝑖))，其中𝑏_(𝑖)为奇数，𝑛_(𝑖)为自然数，则𝑏_(𝑖)≠𝑏_(𝑗)（𝑖≠𝑗）．但因为𝑏_(𝑖)只能取1，3，5，⋅，2𝑛−1至多𝑛个数，矛盾，故得证．

原命题的证明

我们计算这些数𝑎_(1)，𝑎_(2)，⋯，𝑎_(𝑘)在集合{1,2,⋯,𝑛}中倍数的个数．对每个1≤𝑖≤𝑘，𝑎_(𝑖)的倍数个数是[(𝑛)/(𝑎_(𝑖))]．对任何1≤𝑖≠𝑗≤𝑘，𝑎_(𝑖)的此类倍数与𝑎_(𝑗)的此类倍数没有重复，因为它们至少是[𝑎_(𝑖),𝑎_(𝑗)]>𝑛．

∴𝑎_(1)，𝑎_(2)，⋯，𝑎_(𝑘)的倍数总数为∑_(𝑖=1)^(𝑘)[(𝑛)/(𝑎_(𝑖))]．

公式：\therefore n\geq \sum\limits_{i=1}^k\left[\dfrac{n}{a_i}\right]>\sum\limits_{i=1}^k\dfrac{n}{a_i}-k

即

欲证

只需证𝑘_(𝑛)≤(3)/(2)𝑛，即𝑘≤(𝑛)/(2)．

若𝑘>(𝑛)/(2)，由引理得，存在1≤𝑖<𝑗≤𝑘，使得𝑎_(𝑖)∣𝑎_(𝑗)，则[𝑎_(𝑖),𝑎_(𝑗)]=𝑎_(𝑗)<𝑛，矛盾！

从而原命题获证．