Question

докажите что любую сумму из целого числа рублей большую семи можно уплатить купюрами в 3 и 5 руб без сдачи

Answer 1

По индукции.
База: 8 = 5 + 3 можно.
Переход. Пусть k рублей можно. Докажем, что и k + 1 можно.
- Если k можно уплатить так, что среди купюр есть 5 рублей - убираем 5 рублей, добавляем 3 + 3 = 6 рублей.
- Если k можно уплатить только трехрублевками, то трехрублевок не менее 3  (минимальная сумма не меньше 8, которую можно оплатить 3-рублевками, равна 9). Тогда меняем 3 + 3 + 3 = 9 на 5 + 5 = 10.
Переход доказан.

Answer 2

Любую сумму из целого числа рублей большую семи можно уплатить купюрами в 3 и 5 рублей без сдачи

Для доказательства этого утверждения, рассмотрим следующую логику:

- Первое наблюдение: Любое число, большее 7, можно представить в виде суммы 3 и 5. - Второе наблюдение: Если мы можем представить число N в виде суммы 3 и 5, то мы также можем представить число N+3 в виде суммы 3 и 5.

Используя эти два наблюдения, мы можем доказать, что любую сумму из целого числа рублей большую семи можно уплатить купюрами в 3 и 5 рублей без сдачи.

Доказательство:

1. Базовый случай: Пусть N = 8. Мы можем представить число 8 в виде суммы 3 и 5 следующим образом: 3 + 5 = 8. 2. Индукционный шаг: Предположим, что мы можем представить число N в виде суммы 3 и 5 без сдачи. То есть, существуют целые числа a и b, такие что N = 3a + 5b. 3. Докажем, что мы также можем представить число N+3 в виде суммы 3 и 5 без сдачи: - N+3 = (3a + 5b) + 3 = 3(a+1) + 5b. - Таким образом, мы можем представить число N+3 в виде суммы 3 и 5 без сдачи. 4. Исходя из индукционного шага, мы можем представить любое число больше 7 в виде суммы 3 и 5 без сдачи.

Таким образом, мы доказали, что любую сумму из целого числа рублей большую семи можно уплатить купюрами в 3 и 5 рублей без сдачи.