会做这道题的孩子，基本功很扎实（19年10月28日）

家长是孩子最好的老师，

这是奥数君第1009天给出奥数题讲解。

今天的题目是综合应用题，

所用知识不超过小学5年级。

题目（4星难度）：

有n个不大于2019且互不相同的正整数，在其中任意选4个数，一定有2个数的最大公约数不是1。请问n的最大值是多少？

辅导方法：

将题目写给小朋友，

让他自行思考解答，

若20分钟仍然没有思路，

再由家长进行提示性讲解。

讲解思路：

这道题属于综合应用题，

不仅用到数论的基础知识，

还要用到鸽笼原理和容斥原理。

看到“4个数中一定有2个数”这句话，

就要想起鸽笼原理，

即n+1只鸽子放进n个鸽笼，

一定有1个笼子中至少2只鸽子。

这道题其实是鸽笼原理的反向应用，

就是从3个鸽笼中挑4只鸽子，

则一定有2只鸽子原本在同一个鸽笼。

总的解题思路是:

首先考虑鸽笼如何构造，

接着考虑n最大时鸽笼需满足的条件，

最后求出n的最大值。

步骤1：

先思考第一个问题，

鸽笼应如何构造？

每个鸽笼其实是一个分组，

题目中的条件是最大公约数，

2个数的最大公约数不是1，

即每个分组中所有数最大公约数不是1，

因此对每个分组来说，

都存在某个大于1的自然数a，

使该分组中所有数都是a的整数倍，

这就是鸽笼的构造原则。

步骤2：

再思考第二个问题，

n何时才能最大？

结合步骤1的结论，要让n最大，

就是要让3个分组中不同的数尽量多，

应使每个分组的最大公约数都尽量小，

且最大公约数之间彼此互质，

故选择最大公约数分别为2，3，5。

因此第一个分组是2的整数倍，

第二个分组是3的整数倍，

第三个分组是5的整数倍。

步骤3：

综合上述几个步骤，

考虑原题目的答案。

在步骤2的基础上进一步思考，

由于在1到2019的正整数中，

2的整数倍有1009个，

3的整数倍有673，

5的整数倍有403个，

这也是3个分组中的正整数个数。

但注意到这3个分组中有重复，

要计算3个分组中不同的数的个数，

可以应用容斥原理。

由于2和3的公倍数有336个，

2和5的公倍数有201个，

3和5的公倍数有134个，

2、3、5的公倍数有67个。

因此三个分组中不同的数有

1009+673+403-336-201-134+67

=1481个。

所以n的最大值是1481。

思考题（4星难度）：

原题目改个条件。

有n个不大于2019且互不相同的正整数，在其中任意选3个数，一定有2个数的最大公约数不是1。请问n的最大值是多少？

微信回复“20191028”可获得思考题答案。

注：过4个月之后，关键词回复可能失效。

谢谢你这么好看还给我点“在看”。

同类题目链接：