Задача
COM-B2-M04-P010 Суммы из троек и пятёрок
#10
★★★☆☆ Уровень 3 из 5
Докажите, что каждое целое число \(n\ge 8\) можно представить в виде \(n=3a+5b\), где \(a,b\) — неотрицательные целые числа.
Проверьте три первых числа, затем выберите наименьший контрпример.
Имеем \(8=3+5\), \(9=3+3+3\), \(10=5+5\). Предположим, что существуют контрпримеры, и пусть \(n\) — наименьший из них.
Так как \(8,9,10\) представимы, то \(n\ge 11\). Тогда \(n-3\ge 8\), и по минимальности \(n\) число \(n-3\) представимо: \(n-3=3a+5b\).
Следовательно, \(n=3(a+1)+5b\), что противоречит тому, что \(n\) — контрпример. Значит, утверждение верно для всех \(n\ge 8\).
Хотя задача числовая, метод — чистый минимальный контрпример.