Question

Помогите! срочно!!!!! из любых ли ста целых чисел можно выбрать два числа сумма которых кратна 7

Answer 1

Нет, достаточно взять 100 чисел дающих остатки 1 при деление на 7(например 8,15,22,29 и так далее), тогда сумма любых 2-х будет давать остаток 2 при деление на 7

Answer 2

Да, из любых ста целых чисел всегда можно выбрать два числа, сумма которых будет кратна 7. Это можно доказать, применив принцип Дирихле, который гласит:

Если имеется N+1 объектов, размещенных в N контейнерах, то как минимум в одном контейнере окажется по два или более объекта.

В данном случае, мы рассматриваем N = 100 (100 целых чисел) и контейнеры - это возможные остатки чисел при делении на 7. Остатки могут быть от 0 до 6, всего 7 контейнеров.

Если мы будем делить каждое из 100 целых чисел на 7 и рассматривать остатки, то у нас будет 7 контейнеров. В силу принципа Дирихле, как минимум в одном из контейнеров будет содержаться два или более числа. Значит, существуют два целых числа из выбранных ста, сумма которых кратна 7.