Question

Докажите,что в множестве из 3000 натурального чисел найдется хотя бы одна пара чисел,разности между которыми делится на 2019

Answer 1

Принцип Дирихле ( "клетки" - "кролики").

"клетки" - это остатки от деления на 2019,

"кролики" - это 3000 чисел.

"клеток"  2019

"кроликов"  3000

Следовательно, из  3000 чисел по крайней мере два  дают одинаковые остатки при  делении на 2019, т.е. разность этих чисел кратна 2019, т.е. делится на 2019.

Answer 2

Для доказательства данного утверждения воспользуемся принципом Дирихле (принципом ящиков).

Предположим, что утверждение неверно, то есть в множестве из 3000 натуральных чисел нет пары чисел, разность между которыми делится на 2019.

Рассмотрим остатки всех чисел из этого множества при делении на 2019. Так как возможных остатков при делении на 2019 всего 2019 (от 0 до 2018), а чисел в множестве 3000, то по принципу ящиков, как минимум, два числа из этого множества должны иметь одинаковый остаток при делении на 2019.

Пусть эти два числа будут A и B (A > B). Тогда разность между ними будет равна A - B, и она также будет иметь остаток при делении на 2019 (так как сумма и разность чисел с одинаковым остатком при делении на 2019 снова будут иметь остаток при делении на 2019).

Таким образом, мы нашли пару чисел A и B из множества, разность между которыми делится на 2019. Это противоречит предположению о том, что такой пары нет.

Следовательно, наше предположение неверно, и в множестве из 3000 натуральных чисел обязательно найдется хотя бы одна пара чисел, разность между которыми делится на 2019.