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