Логика и комбинаторика · 8–9 классыКомбинаторика: основы

Размен монет: сколькими способами?

Сколькими способами можно набрать сумму монетами разных номиналов, если порядок монет не важен. Считаем перебором по количеству монет.

Вариант № 47130

Размен монет: сколькими способами? · Вариант № 47130 · Обычный · Имя: ____________________

1
У Андрея есть монеты номиналом 2, 3 и 5 рублей (каждого вида достаточно много). Сколькими способами можно уплатить ровно 16 рублей? Порядок монет не важен.
Ответ: 7
Перебираем число монет самого крупного номинала $5$ : от $0$ до $3$ .
Остаток набираем монетами меньших номиналов — снова перебором.
В сумме находим $7$ способов.
2
У Романа есть монеты номиналом 1, 5 и 10 рублей (каждого вида достаточно много). Сколькими способами можно уплатить ровно 10 рублей? Порядок монет не важен.
Ответ: 4
Перебираем число монет самого крупного номинала $10$ : от $0$ до $1$ .
Остаток набираем монетами меньших номиналов — снова перебором.
В сумме находим $4$ способа.
3
У Сони есть монеты номиналом 1, 5 и 10 рублей (каждого вида достаточно много). Сколькими способами можно уплатить ровно 13 рублей? Порядок монет не важен.
Ответ: 4
Перебираем число монет самого крупного номинала $10$ : от $0$ до $1$ .
Остаток набираем монетами меньших номиналов — снова перебором.
В сумме находим $4$ способа.
4
У Насти есть монеты номиналом 2, 3 и 5 рублей (каждого вида достаточно много). Сколькими способами можно уплатить ровно 21 рубль? Порядок монет не важен.
Ответ: 11
Перебираем число монет самого крупного номинала $5$ : от $0$ до $4$ .
Остаток набираем монетами меньших номиналов — снова перебором.
В сумме находим $11$ способов.
5
У Иры есть монеты номиналом 1, 3 и 5 рублей (каждого вида достаточно много). Сколькими способами можно уплатить ровно 30 рублей? Порядок монет не важен.
Ответ: 40
Перебираем число монет самого крупного номинала $5$ : от $0$ до $6$ .
Остаток набираем монетами меньших номиналов — снова перебором.
В сумме находим $40$ способов.

Коротко о теме

Способ набрать сумму — это набор чисел: сколько монет каждого номинала. Порядок монет не важен.
Перебирай количество самых крупных монет, остаток набирай мелкими: так не потеряешь вариант и не посчитаешь дважды.
Для двух номиналов $a$ и $b$ нужно, чтобы остаток после монет $a$ делился на $b$ .
Таблица «сумма → способов» заполняется по очереди для каждого номинала.

Уровни: Разминка · Обычный · Challenge. Все ответы вычислены программой из тех же чисел, что и условие.

Ещё тренажёры

Раздел «Комбинаторика: основы»

Число подмножеств

Другие темы: 8 класс