|
|
 |
Условие
Глава Монетного двора хочет выпустить монеты 12 номиналов (каждый – в натуральное число рублей) так, чтобы любую сумму от 1 до 6543 рублей можно было заплатить без сдачи, используя не более 8 монет. Сможет ли он это сделать?
(При уплате суммы можно использовать несколько монет одного номинала.)
Решение
Заметим, что 94 = 6561 > 6543.
Если выпустить монеты трёх номиналов – 1, 3 и 4 рубля, то, как легко проверить, с помощью не более чем двух монет можно уплатить без сдачи любую сумму от 1 до 8 рублей.
Пусть Монетный двор изготовит монеты с номиналами 9k, 3·9k и 4·9k рублей при k = 0, 1, 2, 3. Любое число N от 1 до 6560 единственным образом представляется в виде N = a3·9³ + a2·9² + a1·9 + a0, где числа ak могут принимать значения от 0 до 8. Как показано выше, сумма ak·9k может быть получена не более чем двумя монетами. Таким образом, вся сумма N может быть получена не более чем 4·2 = 8 монетами указанных номиналов.
Ответ
Сможет.
