Теория чисел на СПБГУ: десятичная запись, оценка+пример, разные системы счисления

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

Теперь пусть из монет мы сможем собрать число , то есть , где целые и неотрицательные. Заметим, что 3 монеты вида можно обменять на 5 монет . Значит, можно считать, что . С другой стороны, делится на 3, и значит, и . Тогда , где целые и неотрицательные. Это значит, что из монет мы смогли собрать ?!

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

Заметим, что для мы можем получить все числа хотя бы 10, так как для любого существует от 0 до 2 такое, что и . Значит, . Так же , , а вот 7 получить уже не получится. Значит . Отсюда и .