ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 103964
Темы:    [ Принцип Дирихле (прочее) ]
[ Арифметика остатков (прочее) ]
Сложность: 3
Классы: 7,8,9
Название задачи: Делимость на n.
В корзину
Прислать комментарий

Условие

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

Подсказка

Рассмотрите суммы a1,   a1 + a2,    a1 + a2 + a3,    … ,    a1 + a2 + … + an.

Решение

Воспользуемся указанием и запишем суммы a1,   a1 + a2,    a1 + a2 + a3,    … ,    a1 + a2 + … + an. Если одна из сумм делится без остатка на n, то задача решена. Если же ни одна сумма не делится на n, то остатки могут быть 1, 2, 3, …, n-1, т.е. всего n-1 возможностей - "клеток", а чисел у нас на единицу больше, следовательно, по крайней мере, две суммы имеют равные остатки. Осталось взять разность этих сумм.

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

кружок
Место проведения МЦНМО
класс
Класс 8
Кружок
Год 2005/2006
занятие
Дата 2005-10-01
Номер 1
Название Принцип Дирихле
Тема Принцип Дирихле (прочее)
задача
Номер 5
книга
Автор Алфутова Н.Б., Устинов А.В.
Год издания 2002
Название Алгебра и теория чисел
Издательство МЦНМО
Издание 1
глава
Номер 4
Название Арифметика остатков
Тема Деление с остатком. Арифметика остатков
параграф
Номер 2
Название Делимость
Тема Теория чисел. Делимость (прочее)
задача
Номер 04.047
кружок
Место проведения МЦНМО
класс
Класс 7
год
Год 2004/2005
занятие
Номер 8
Название Принцип Дирихле
Тема Принцип Дирихле
задача
Номер 8.8

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .