Рассмотрим числа 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^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), что и нужно было доказать.