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

Проект МЦНМО
при участии
школы 57
Задача 116763
Темы:    [ Арифметика остатков (прочее) ]
[ НОД и НОК. Взаимная простота ]
[ Доказательство от противного ]
Сложность: 4-
Классы: 10,11
В корзину
Прислать комментарий

Условие

Пусть  a1, ..., a10  – различные натуральные числа, не меньшие 3, сумма которых равна 678. Может ли сумма остатков от деления некоторого натурального числа n на 20 чисел  a1, a2, ..., a10, 2a1, 2a2,..., 2a10  равняться 2012?


Решение

  Предположим, что такое число n существует. Максимальный возможный остаток от деления на натуральное число m равен  m – 1.  Поэтому сумма остатков от деления произвольного числа на числа  a1, ..., a10  не больше чем  678 – 10 = 668,  а сумма остатков от деления его на числа 2a1, 2a2,..., 2a10 не больше чем  2·678 – 10 = 1346.  Если бы все остатки были максимальными возможными, то их сумма равнялась бы  668 + 1346 = 2014.  Поскольку эта сумма для нашего числа n равна 2012, возможны только два случая.
  1) Ровно один из остатков на 2 меньше максимального возможного, а остальные – максимальные возможные. Тогда при некотором k один из остатков от деления n на числа ak и 2ak – максимальный возможный, а другой – на 2 меньше. Значит, одно из чисел  n + 1  и  n + 3  делится на ak, а другое – на 2ak, то есть оба делятся на ak. Это невозможно, так как число  (n + 3) – (n + 1) = 2  не делится на  ak > 2.
  2) Ровно два остатка на 1 меньше максимальных возможных. Тогда среди остатков от деления n на четные числа  2a1, 2a2,..., 2a10  по крайней мере восемь – максимальные возможные, то есть нечётные. Значит, n – нечётное число, и потому все остатки от деления его на числа 2a1, 2a2,..., 2a10 нечётны. Таким образом, они – максимальные возможные. Это значит, что  n + 1  делится на все числа  2a1, 2a2,..., 2a10  и, следовательно, на все числа a1, ..., a10,  то есть все 20 остатков – максимальные возможные. Противоречие.


Ответ

Не может.

Замечания

1. Можно показать, что ответ остаётся отрицательным, даже если предположить, что все числа ai больше 1.

2. Ср. с задачей 116755.

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

олимпиада
Название Всероссийская олимпиада по математике
год
Год 2011-2012
Этап
Вариант 5
класс
Класс 10
Задача
Номер 10.1

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

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