Условие
Есть неограниченное число монет достоинством 4 и 5 рублей; сдачу получать нельзя. а) Можно ли набрать 10 рублей? б) Можно ли набрать 11 рублей? в) Найдите наибольшую целую положительную сумму, которую набрать нельзя.
Подсказка
10=(2)·5. Достаточно 2 монет большего достоинства.
Если 4x+5y=11, то по модулю 4 имеем y≡3. При y≥0 это требует y≥3, но одни такие монеты стоят не менее 15>11. Противоречие.
Показать ответ
а) да; б) нет; в) 11
Пошаговое решение
- Строим сумму из пункта а
10=(2)·5. Достаточно 2 монет большего достоинства.
- Доказываем невозможность следующей суммы
Если 4x+5y=11, то по модулю 4 имеем y≡3. При y≥0 это требует y≥3, но одни такие монеты стоят не менее 15>11. Противоречие.
- Доказываем достижимость всех больших сумм
Пусть S≥12. Делим с остатком: S=4q+r, 0≤r≤3. Тогда q≥3≥r, и S=4(q−r)+5r. Оба количества монет неотрицательны.
- Объединяем результаты
Сумму 11 набрать нельзя, а каждую целую сумму начиная с 12 можно. Поэтому искомый максимум 11.
Ответ: а) да; б) нет; в) 11