|
|
 |
Условие
Шайка разбойников отобрала у купца мешок монет. Каждая монета стоит целое число грошей. Оказалось, что какую бы монету ни отложить, оставшиеся монеты можно разделить между разбойниками так, чтобы каждый получил одинаковую сумму в грошах. Докажите, что если отложить одну монету, то число монет разделится на число разбойников.
Решение
Можно считать, что стоимости монет в грошах взаимно просты. Действительно, если они имеют наибольший общий делитель 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. Тогда равенство долей при каждой делёжке можно записать как равенство некоторых сумм. Набор всех таких равенств – однородная линейная система с рациональными коэффициентами, и про нее известно, что она имеет решение в положительных числах. Но тогда она имеет решение и в положительных рациональных числах. Умножив такое решение на общий знаменатель, получим решение в натуральных числах. А для такого случая делимость уменьшенного на единицу числа слитков на число разбойников только что доказана.
