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

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

Условие

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


Решение

   Предположим, что такое число n существует.

   Максимальный возможный остаток от деления на натуральное число m равен  m – 1.  Поэтому сумма остатков от деления произвольного числа на числа  a1, ..., a11  не больше чем  407 – 11 = 396,  а сумма остатков от деления его на числа  4a1, 4a2, ..., 4a11  не больше, чем  4·407 – 11 = 1617.  Если бы все остатки были максимальными возможными, то их сумма равнялась бы  396 + 1617 = 2013.  Поскольку эта сумма для нашего числа n равна 2012, то все остатки, кроме одного, – максимальные возможные, а один – на единицу меньше максимального возможного.
   Значит, при некотором k один из остатков от деления n на числа ak и 4ak – максимальный возможный, а другой – на единицу меньше максимального возможного. Тогда одно из чисел  n + 1  и  n + 2  делится на ak, а другое – на 4ak, то есть два взаимно простых числа  n + 1  и  n + 2  делятся на  ak ≥ 2.  Это невозможно.


Ответ

Не может.

Замечания

Ср. с задачей 116763.

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

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

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

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