Question

Докажите, что среди любых 7 целых чисел найдутся одно или несколько, сумма которых делится на 7.

Answer 1

7, 14, 21, 28, 35, 42, 49

все числа кратны 7

Answer 2

Для решения этой задачи можно использовать принцип Дирихле, который гласит, что если n предметов распределены по k ящикам, и n > k, то хотя бы в одном ящике будет больше одного предмета .

Пусть даны 7 целых чисел a[1], a[2], ..., a[7]. Рассмотрим их остатки при делении на 7. Они могут быть равны 0, 1, 2, 3, 4, 5 или 6. Если хотя бы одно из этих чисел имеет остаток 0, то оно само по себе делится на 7, и задача решена.

Если же нет, то, поскольку чисел всего семь, а остатков - шесть, среди них найдутся хотя бы два числа s[i] и s[j] (i < j) с равными остатками. Тогда их разность, равная сумме:

s[j] - s[i] = a[i + 1] + ... + a[j],

будет иметь остаток 0 при делении на 7, то есть делиться на 7. Таким образом, мы нашли одно или несколько чисел, сумма которых делится на 7.