【原】初中竞赛题选讲 第三百五十七题解答

本题目选自 2020土耳其数学奥林匹克 第二轮

已知正整数，集合.若正整数满足, 对的任一元子集, 其中必存在元素,使得 ,求的最小值.

解:考虑问题的反面, 即求的最大值, 使得存在的元子集,满足中任意两个元素,均不满足.

显然,集合 满足上述条件.

下面证明即为的最大值.

首先, 对于不超过的任意正整数, 显然. 若,我们将结为一对. 若,则必存在正整数, 使得,这样的至少有个.(实际上至少有个,但个足以解决本问题)

那么我们从开始, 到为止, 逐个将每个不超过的任意正整数与某个大于且不超过其平方的倍数结对;

当时,取与结对即可;显然不会重复;

当时,由于大于且不超过其平方的倍数至少有个,但我们一共只需要结个对子,故我们一定可以选到一个之前没有用过的数, 与结对;

当完成结对之后,显然我们从每个对子中,只能选取一个数; 而显然不能选, 那么我们至多可以选择个数.

于是题目所求的最小值为.