有500个互不相同的正整数，已知它们之中没有任何两个数恰好是整除关系。那么请判断最大的那个整数，至少是几?
对于k个正整数，如果他们中没有任何两个数是整除关系，让我们称这些数构成一个最简k-组合P，其中最大的那个整数记为m_P. 令a_k=min(m_P | 对于所有的最简k-组合P). 我们的问题就是求a_500. 很显然{k, k+1, ..., 2k-1}是这样一个组合，因为这个集合里面最小的数是k,最大的是2k-1,不到k的两倍，所以不可能有任何的倍数关系。因此 a_k <= 2k-1. 我们希望证明a_k=2k-1。如果我们能够证明对于{1,2,..., 2k-2}中任意k个数，至少都会有两个数，其中一个是另一个的倍数，我们的结论就可以成立了，因为这等于说a_k>2k-2。 这可以用归纳法。当k=2的时候，2k-2=2. {1，2}这个集合中只有1，2两个数，其中一个是另一个的两倍。 如果命题对于k成立，也就是说{1,2,...,2k-2}中任意k个数，至少都能找出两个数来，其中一个是另一个的倍数，那么对于k+1的情形：{1，2，..., 2k-2, 2k-1, 2k} 中，如果有（k+1）个数，它们之中任何两个数都没有倍数关系的话，那么这k+1个数不能只包含{2k-1, 2k}中的一个，否则剩下的k个数全部都在{1，2，..., 2k-2}中，而且两两互无倍数关系，这和归纳假设矛盾。 所以他们必须同时包含2k-1和2k. 剩下的k-1个数在{1，2，。。。，2k-2}中，而且两两互无倍数关系。但是也不能有任何一个能整除2k, 换句话说，就是这k-1个数既不包括k,也不包括k的任何因数。那么，如果我们将这k-1个数和k合在一起，构成一个新的k-元组，它们也应该两两互无倍数关系，因为他们之中没有数可以整除k,也没有数能被k整除（最大的只有2k-2, 不到k的两倍）。又和归纳假设矛盾。 所以不存在这样的k+1个数。于是命题得证。 a_500=2*500-1=999. |
1001 |
第500个质数而已 |
| 欢迎光临 珍珠湾ART (http://zzwav.com/) | Powered by Discuz! X3 |