考虑数字1,2，...，1000。证明在其中的501个中存在两个数字，一个除以另一个。

Question

我在Matousek和Nesetril的“邀请离散数学”一书中遇到了这个问题。我对这些问题很陌生。我以这种方式处理了这个问题： 从501号码中选择的两个数字由除数和分红组成。大于500的数字不能是除数。所以我们至少需要一个1-500的数字。我们实际上会得到一个这个范围的数字，因为我们需要从1000个数字中选择501个数字。

我分501个的任何数量的选择分为以下情况：

案例1 - 我们选择501-1000包容性和包容性的1-500之间的任意数字之间的所有数字。在这种情况下，该陈述很容易证明，因为1-500之间的所有数字都至少有一个在501-1000范围内的股息，并且选择了整个范围。 案例2-我们选择1-500之间的所有数字和501-1000（含）之间的任何一个数字。在这种情况下，这个陈述很容易被证明，因为在1-500范围内有许多对，作为除数和对方的红利。 案例3-我们选择1-500范围内的一些数字和501-1000范围内的一些数字。我无法证明对于1-500范围内的某个数字，所选的股息是有的。

Answer 1

这个问题可能是题外话了SO，但这里有一个证明，它利用了pidgeonhole原则：

每个号码可以在形式2^k为写（2M + 1）其中k，米≥0

因为每个数小于1001，m必须小于500

那么既然你选择501个号码，两个号码必须具有相同的M值为。

这两个数字可以写成2^k1（2m + 1）和2^k2（2m + 1）。

或者k1≤k2或者k2≤k1，所以不失一般性，假设k1≤k2。

然后2^k1（2m + 1）除2^k2（2m + 1），这就是要证明的。