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

Проект МЦНМО
при участии
школы 57
Задача 98410
Темы:    [ Деление с остатком ]
[ НОД и НОК. Взаимная простота ]
[ Уравнения в целых числах ]
[ Системы линейных уравнений ]
Сложность: 4
Классы: 7,8
В корзину
Прислать комментарий

Условие

Шайка разбойников отобрала у купца мешок монет. Каждая монета стоит целое число грошей. Оказалось, что какую бы монету ни отложить, оставшиеся монеты можно разделить между разбойниками так, чтобы каждый получил одинаковую сумму в грошах. Докажите, что если отложить одну монету, то число монет разделится на число разбойников.


Решение

  Можно считать, что стоимости монет в грошах взаимно просты. Действительно, если они имеют наибольший общий делитель  d > 1,  то деноминируем грош, приравняв один новый к d старым. Тогда все условия задачи по-прежнему выполнены, но новые стоимости монет будут взаимно простыми.
  Пусть n разбойников отняли m монет на общую сумму в g грошей. Так как при вычитании из g стоимости любой монеты получим число, кратное n, то стоимости всех монет дают при делении на n один и тот же остаток r. Так как стоимость любого набора из  m – 1  монет делится на n, то  (m – 1)r  делится на n. Кроме того, r и n взаимно просты, поскольку любой их общий делитель является общим делителем стоимостей всех монет. Отсюда следует, что
m – 1  делится на n.

Замечания

То, что стоимости монет соизмеримы, несущественно. Заменим монеты золотыми слитками веса x1, x2, ..., xn. Тогда равенство долей при каждой делёжке можно записать как равенство некоторых сумм. Набор всех таких равенств – однородная линейная система с рациональными коэффициентами, и про нее известно, что она имеет решение в положительных числах. Но тогда она имеет решение и в положительных рациональных числах. Умножив такое решение на общий знаменатель, получим решение в натуральных числах. А для такого случая делимость уменьшенного на единицу числа слитков на число разбойников только что доказана.

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

web-сайт
задача
олимпиада
Название Турнир городов
Турнир
Дата 1998/1999
Номер 20
вариант
Вариант осенний тур, основной вариант, 8-9 класс
Задача
Номер 6

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

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