Рассмотрим числа 1,2, ..., 1000. Покажите, что среди любых 501 из них существуют два числа, которые разделяют другой.

Question

Я столкнулся с этим вопросом в книге «Приглашение к дискретной математике» Матууска и Несритрила. Я новичок в таких проблемах. Я подошел к этой проблеме таким образом: Два числа, выбранные из любых чисел 501, состоят из делителя и дивиденда. Число больше 500 не может быть делителем. Поэтому нам нужно хотя бы одно число в диапазоне 1-500 включительно. И мы фактически получим число в этом диапазоне, учитывая тот факт, что нам нужно выбрать 501 номеров из 1000 номеров.

Я разделил выбор любых 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^к (2m + 1), где к, м ≥ 0.

поскольку каждое число меньше, чем 1001, м должно быть меньше 500.

Так, так как вы выбираете 501 номеров, два из чисел должны иметь такое же значение, т.

Эти два числа могут быть записаны как 2^k1 (2m + 1) и 2^k2 (2m + 1).

Либо k1 ≤ k2, либо k2 ≤ k1, поэтому без ограничения общности предположим, что k1 ≤ k2.

Затем 2^k1 (2m + 1) делит 2^k2 (2m + 1), что и требовалось доказать.