Задача 35037

Темы:    [ Уравнения в целых числах ] [ Раскладки и разбиения ]

Сложность: 3 Классы: 8,9,10

Условие

В обращении есть монеты достоинством в 1, 2, 5, 10, 20, 50 копеек и 1 рубль. Известно, что k монетами можно набрать m копеек.
Докажите, что m монетами можно набрать k рублей.

Подсказка

Для каждой монеты достоинством в n коп. есть монета достоинством в  ¹⁰⁰/_n  коп.

Решение

  Пусть среди k монет, дающих в сумме m копеек, есть a₁ монет по 1 коп., a₂ – по 2 коп., a₃ – по 5, a₄ – по 10, a₅ – по 20, a₆ – по 50 коп. и a₇ – по 1 рублю. Тогда
      a₁ + 2a₂ + 5a₃ + 10a₄ + 20a₅ + 50a₆ + 100a₇ = m;
      a₁ + a₂ + a₃ + a₄ + a₅ + a₆ + a₇ = k.
  Умножим второе равенство на 100 и запишем его в виде:
      100a₁ + 50·2a₂ + 20·5a₃ + 10·10a₄ + 5·20a₅ + 2·50a₆ + 100a₇ = 100k.
  Отсюда следует, что если взять 100a₇ монет по 1 коп., 50a₆ – по 2, 20a₅ – по 5, 10a₄ – по 10, 5a₃ – по 20, 2a₂ – по 50 коп. и a₁ монет по 1 рублю, то в сумме они дадут 100k копеек, то есть k рублей. А согласно первому равенству монет будет m.

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

web-сайт

задача