|
|
 |
Условие
Любую ли сумму из целого числа рублей больше семи, можно уплатить без сдачи денежными купюрами по 3 и 5 рублей?
Решение 1
Если эта сумма кратна 3 (наименьшее возможное число 9), используем только 3-рублевые купюры. Если при делении на 3 она даёт остаток 1 (наименьшее возможное число 10), то берём две 5-рублевые купюры, остальное доплачиваем 3-рублевыми. Если же при делении на 3 сумма даёт остаток 2 (наименьшее возможное число 8), то берём одну 5-рублевую купюру, остальное доплачиваем 3-рублевыми.
Решение 2
Докажем это по индукции.
База: сумму в 8 рублей выплатить можно.
Шаг индукции. Пусть сумму в n рублей можно выплатить 3- и 5-рублевыми купюрами. Если среди этих купюр есть хоть одна 5-рублевая, то заменив её на две 3-рублевые, мы получим n + 1 рублей. Если же все купюры 3-рублевые, то их не меньше трёх, и, заменив три 3-рублевые купюры на две 5-рублевые, мы тоже получим n + 1 рублей.
Ответ
Любую.
Источники и прецеденты использования
| книга | |
| Автор | Алфутова Н.Б., Устинов А.В. |
| Год издания | 2002 |
| Название | Алгебра и теория чисел |
| Издательство | МЦНМО |
| Издание | 1 |
| глава | |
| Номер | 1 |
| Название | Метод математической индукции |
| Тема | Индукция |
| параграф | |
| Номер | 3 |
| Название | Индукция в геометрии и комбинаторике |
| Тема | Индукция (прочее) |
| задача | |
| Номер | 01.048 |
| кружок | |
| Место проведения | МЦНМО |
| класс | |
| Класс | 6 |
| год | |
| Год | 2004/2005 |
| занятие | |
| Номер | 11 |
| задача | |
| Номер | 11.3 |
