Question

Помогите пж Из первых ста натуральных чисел выбрали пятьдесят одно число (все числа различны). Докажите, что среди выбранных обязательно найдутся два числа, отличающиеся ровно на 1.

Answer 1

Допустим, что таких чисел нет и числа в наборе отличаются друг от друга минимум на 2. Для этого достаточно последовательно выбрать 51 нечетное число (1,3,5,...) и так далее, либо 51 четное число (2,4,6,...) и т. д. Но нечетных чисел в первой сотне только 50, так же, как и четных. Получаем противоречие. Следовательно минимум два числа в наборе отличаются друг от друга на 1.

Answer 2

Для доказательства этого утверждения можно воспользоваться методом Дирихле, который гласит, что если распределить n+1 объектов по n ящикам, то в каком-то ящике будет не менее 2 объектов.

В данном случае, мы имеем 101 объект - первые сто натуральных чисел и выбранные из них 51 число. Распределим эти числа по ящикам в следующий способ: в первый ящик поместим числа, оканчивающиеся на 0 или 1, во второй - на 2 или 3, в третий - на 4 или 5, и так далее, в последний ящик - на 98 или 99.

Таким образом, мы получим 51 ящик, каждый из которых содержит 2 числа. При этом, если два выбранных числа отличаются на 1, то они обязательно попадут в один ящик. Значит, если ни один ящик не содержит двух таких чисел, то все выбранные числа должны принадлежать разным ящикам. Но тогда какой-то один ящик будет содержать два числа, а это противоречит методу Дирихле.

Таким образом, мы доказали, что среди выбранных чисел обязательно найдутся два числа, отличающиеся ровно на 1.