Задача 103964

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

Сложность: 3 Классы: 7,8,9 Название задачи: Делимость на n.

Условие

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

Подсказка

Рассмотрите суммы a₁,   a₁ + a₂,    a₁ + a₂ + a₃,    … ,    a₁ + a₂ + … + a_n.

Решение

Воспользуемся указанием и запишем суммы a₁,   a₁ + a₂,    a₁ + a₂ + a₃,    … ,    a₁ + a₂ + … + a_n. Если одна из сумм делится без остатка на 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