Задача 35415

Темы:    [ Принцип Дирихле (прочее) ] [ Деление с остатком ] [ Правило произведения ]

Сложность: 4 Классы: 8,9,10

Условие

На доске написано 10 натуральных чисел. Докажите, что из этих чисел можно выбрать несколько чисел и расставить между ними знаки "+" и "–" так, чтобы полученная в результате алгебраическая сумма делилась на 1001.

Подсказка

Рассмотрите вначале только суммы со знаками "+". Затем покажите, что из одной из этих сумм можно вычесть другую так, чтобы результат делился на 1001.

Решение

Рассмотрим всевозможные суммы нескольких из выписанных чисел. Количество таких сумм будет равно  2¹⁰ = 1024  (мы учитываем пустую сумму). Согласно принципу Дирихле некоторые две из этих сумм S₁ и S₂ дают одинаковый остаток при делении на 1001. Разность этих сумм  S₁ – S₂  делится на 1001 и представляет собой сумму нескольких данных чисел со знаками "+" или "–".

Источники и прецеденты использования

web-сайт

задача