求助:(请写出解答详细的过程和原因)
从1,2,3,……,100这100个自然数中,任意取出n个数,在这n个数中总能找到4个数,它们每两个数都互质。求n的最小值。(请写出解答详细的过程和原因)
参考答案:首先
1和所有数互质
其次
n的最小值显然是大于50的 因为可以取100内所有的偶数 恰50个 且其中没有互质的数
(这不是必要的步骤 但可以帮助我们缩小n最小值的可能范围)
接下来考虑100以内
以2为约数的 有50个
以3为约数的 有33个 去掉前面50个中有的数 还剩17个
以5为约数的 有20个 去掉前面已经出现的数 还剩7个
以上一共50+17+7 = 74个数
因为只有2 3 5是质数
所以这74个数中是找不出4个数 使得它们两两互质的
同时还要能看到 100以内 剩下的26个数中任选一个数都与这74个数互质!
(比如说1、7、13、29 都在剩下的26个数里,而14、35都是属于74个数里面的数)
所以n的最小值是75
也就是说任取75个数 必然可以从中找出4个两两互质的数。