Олимпиадная задача по теории чисел про монеты, k и m
Задача
В обращении есть монеты достоинством в 1, 2, 5, 10, 20, 50 копеек и 1 рубль. Известно, что k монетами можно набрать m копеек.
Докажите, что m монетами можно набрать k рублей.
Решение
Пусть среди k монет, дающих в сумме m копеек, есть a1 монет по 1 коп., a2 – по 2 коп., a3 – по 5, a4 – по 10, a5 – по 20, a6 – по 50 коп. и a7 – по 1 рублю. Тогда
a1 + 2a2 + 5a3 + 10a4 + 20a5 + 50a6 + 100a7 = m;
a1 + a2 + a3 + a4 + a5 + a6 + a7 = k.
Умножим второе равенство на 100 и запишем его в виде:
100a1 + 50·2a2 + 20·5a3 + 10·10a4 + 5·20a5 + 2·50a6 + 100a7 = 100k.
Отсюда следует, что если взять 100a7 монет по 1 коп., 50a6 – по 2, 20a5 – по 5, 10a4 – по 10, 5a3 – по 20, 2a2 – по 50 коп. и a1 монет по 1 рублю, то в сумме они дадут 100k копеек, то есть k рублей. А согласно первому равенству монет будет m.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь