Для удобства я сделал одну и ту же задачу на 2-х языках UA/RU UA: Доведіть, що з будь-яких 15 цілих чисел можна вибрати два, різниця яких ділиться на 14.
RU: Докажите, что из любых 15 целых чисел можно выбрать два, разница которых делится на 14.

178

323

Посмотреть ответы 2

Ответы на вопрос:

zhludovaanasta

Алгебра

4,6(89 оценок)

Для решения данной задачи можно воспользоваться 3мя фактами:

1) Всего существует 14 разных возможных остатков от деления на 14: 0, 1, 2, ..., 12, 13.

2) Если разность двух чисел кратна n, то остатки этих чисел от деления на n равны.

Док-во: Пусть x1 = an + b, а х2 = сn + d (a, c, n- целые; b, d- натуральные, меньше n, так как это остатки х1 и х2 соответственно от деления на n). Дан факт, что x1 - x2 кратно n, то есть, имеет вид z*n, где z- целое число.

x1 - x2 = z * n

an + b - cn - d = zn

b - d = zn - an + cn

b - d = n (z - a + c). Правая часть кратна n, значит и выражение (b - d) кратно n. Возьмем данное выражение по модулю n

b - d ≡ 0 (mod n)

b ≡ d (mod n), ч.т.д.

3) Необобщенная Теорема Дирихле гласит: "Если взять n кроликов и посадить их в (n-1) клеток, то обязательно найдется хотя бы 1 клетка, в которой будет хотя бы 2 кролика".

Док-во от противного: Пусть, при данном условии, не найдется ни одна клетка с хотя бы двумя кроликами. Тогда, поскольку клеток (n-1), а кролик в одной клетке может быть максимум 1, то максимум может быть 1*(n-1) = n-1 кроликов, а у нас их n. Противоречие.

Итого, получаем такой вывод, что вместо кроликов можно взять данные нам числа, а вместо клеток- остатки от деления на 14. Тогда, если не найдется клеток, в которых будет хотя бы 2 числа, то максимум в одной клетке может быть 1 число, а клеток 14. Тогда максимум может быть 14 чисел, а у нас их 15. Противоречие.

Полученное противоречие показывает, что среди 15ти целых чисел всегда найдутся 2, разность которых кратна 14ти.

Женя11134

Алгебра

4,5(58 оценок)

Как говорила мне мама подумай сам

Реши свою проблему, спроси otvet5GPT

Быстро
Мгновенный ответ на твой вопрос
Точно
Бот обладает знаниями во всех сферах
Бесплатно
Задай вопрос и получи ответ бесплатно

Задай свой вопрос

Популярно: Алгебра

Есть вопросы?

Как otvet5GPT работает?

otvet5GPT использует большую языковую модель вместе с базой данных GPT для обеспечения высококачественных образовательных результатов. otvet5GPT действует как доступный академический ресурс вне класса.
Сколько это стоит?

Проект находиться на стадии тестирования и все услуги бесплатны.
Могу ли я использовать otvet5GPT в школе?

Конечно! Нейросеть может помочь вам делать конспекты лекций, придумывать идеи в классе и многое другое!
В чем отличия от ChatGPT?

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