Question

Доказать, что среди любых 99 натуральных чисел всегда можно выбрать 15 так, что разность любых двух из них делится на 7

Answer 1

Ответ:

1. При делении натурального числа на 7 возможны 7 остатков: от 0 до 6. Среди 100 натуральных чисел найдутся 15 таких, которые имеют один и тот же остаток. Докажем это.

  2. Предположим, что утверждение ложно, и для каждого из 7 остатков не больше 14 чисел. Поскольку остатков всего 7, то наибольшее количество чисел в этом случае будет 7 * 14 = 98 < 100, а у нас их 100. Значит, наше предположение ложно.

  3. Тогда разность любых двух из этих 15 чисел с равными остатками будет кратна 7, что и требовалось доказать.

Надеюсь помог, удачи тебе. :)

Answer 2

Ответ:

Пошаговое объяснение:

Разность 2-х чисел делится на 7 если остатки при делении на 7 у этих 2-х чисел одинаковы. Возможны 7 разных остатков при делении на 7

(0 ; 1; 2; 3; 4; 5; 6).  Т.е. среди 8-и натуральных чисел найдутся обязательно по крайней мере 2 числа с одинаковыми остатками при делении на 7 ( принцип Дирихле) . Среди 15 - по крайней мере 3 числа,  Среди 15+7 =22 - по крайней мере 4 числа с одинаковыми остатками при делении на 7  А  среди 99- 99/7=14 1/7   -  по крайней мере 15 чисел с одинаковыми остатками при делении на 7  

Что и требовалось доказать.

Answer 3

Давайте докажем этот факт методом принципа Дирихле.

Рассмотрим остатки этих 99 чисел при делении на 7. Всего существует 7 возможных остатков: 0, 1, 2, 3, 4, 5, 6.

Если среди этих 99 чисел есть хотя бы 15 чисел с одним и тем же остатком, то разность любых двух из них будет делиться на 7. В этом случае утверждение уже доказано.

Предположим, что среди этих 99 чисел нет 15 чисел с одним и тем же остатком. Тогда, по принципу Дирихле, среди них должны быть как минимум по два числа с одним и тем же остатком (или более). Рассмотрим одну из таких пар чисел.

Пусть у нас есть два числа a и b из нашего набора, которые имеют одинаковый остаток при делении на 7. Тогда a - b будет делиться на 7. Добавим это значение в наш набор чисел и удалим исходные числа a и b из него.

После этого у нас останется 98 чисел. Продолжим этот процесс до тех пор, пока не найдутся 15 чисел с одним и тем же остатком (что гарантированно произойдет рано или поздно).

Таким образом, мы сможем выбрать 15 чисел из исходных 99 так, чтобы разность любых двух из них делилась на 7.