logic - 考虑数字 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,m ≥ 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)，这就是要证明的。