Задача о расплате без сдачи

[Gepidium]

Здраствуйте. Второй день бьюсь над вроде бы простой задачей.
На одном острове в обращении находятся монеты достоинством только в $3$ и $5$ южноокеанских долларов.
Требуется доказать, что любое целое число долларов, большее $7$, можно уплатить без сдачи этими монетами.
Я составила небольшую программу, она просчитала все значения от $n=8$ до $n=200000$, и любое число из этого интервала можно разбить на слагаемые из троек и пятёрок.
Но вот как доказать? Ничего не вижу.
Киньте идею, подскажите, хоть с чего начать.

[Mihr]

Попробуйте методом математической индукции. По-моему, очень легко.

[Gepidium]

Mihr в сообщении #1568330 писал(а):

Попробуйте методом математической индукции.

База индукции ясна: при $n=8$ утверждение выполняется.
А вот как сделать индукционное предположение?

[Mihr]

База индукции: при $n=8$, $n=9$, $n=10$ утверждение выполняется. Дальше сообразите сами?

[B@R5uk]

Было бы интереснее и, самое главное, практичнее указать формулы для расчёта количества пятёрок и троек. Понятно, что вариантов представления одного и того же числа может быть больше одного (заменяем 3 пятака на 5 троек — получаем новый вариант; аналогично наоборот), но всё равно, явное указание решения всегда предпочтительней просто факта его существования.

Указанная замена, на мой взгляд, уже даёт вполне конкретный намёк на то, как такое решение построить.

Mihr в сообщении #1568336 писал(а):

База индукции: при $n=8$, $n=9$, $n=10$ утверждение выполняется.

Кстати, тоже хороший намёк, как построить явные формулы.

[lel0lel]

Платим пятаками до предела. Возможные остатки, которые надо доплатить это $1, 2, 3, 4$. Если $1, 4$, то забираем пятак и платим трёшками. Если остаток $2$, забираем два пятака.

[svv]

Если $n$ можно, то также можно $n+3, n+6, n+9...$.
$3$ можно, значит, также $6, 9, 12...$
$5$ можно, значит, также $8,11,14...$
$10$ можно, значит, также $13,16,19...$
Каких чисел нет в списках?

[Gepidium]

svv
Но тут надо доказать, что все эти арифметические прогрессии полностью покрывают натуральный ряд.

[svv]

У каждой прогрессии "свой" остаток от деления любого из её членов на $3$. А остаток может быть лишь $0,1,2$.

[Евгений Машеров]

Если у нас сумма в N долларов ЮА представлена монетами, среди которых есть хотя бы одна в 5 долларов ЮА...
Если эта сумма представлена только монетами в 3 доллара ЮА, то их не менее 3...
На этом Шехерезада прекращает дозволенные речи.

[Gepidium]

Евгений Машеров
Вы - гений. Навели меня на индукционное предположение.
Предположим, что мы можем заплатить сумму в $n$ долларов тройками и пятерками. Надо доказать, что и сумму в $n+1$ долларов мы также сможем заплатить.
Надо убрать три тройки и добавить две пятерки. Но это если сумма состоит только из троек (а их не может быть меньше трех - алиллуйя, Евгений Машеров!).
А вот если в сумме присутствует хоть одна пятерка, мы ее убираем, а добавляем две тройки.
Все!!! Так?

[Евгений Машеров]

Польщён, но гениальности в себе не усматриваю. Достаточно стандартный "алгоритмический" подход.

[Mihr]

Gepidium, раз уж Вы догадались, я изложу для сравнения своё решение. Идеи здесь такие же, оформление немного иное. Смотрите сами, какое для Вас удобнее.

Всякое целое число при делении на 3 может давать остаток $r$, равный 0, 1 или 2. Поэтому всякое число $a$ представимо в виде $a=3n+t$, где $t=0$, $t=1$ или $t=-1$. В первых двух случаях $t$ совпадает с указанным остатком $r$, в третьем случае $t=r-3$.
Используем обобщенный принцип полной математической индукции: будем доказывать справедливость утверждения не для всех вообще $n$, а для всех $n$, начиная с некоторого, в данном случае начиная с $n=3$.

База индукции: при $n=3$ (то есть, для чисел $a=8$, $a=9$, $a=10$) утверждение справедливо.

Индуктивный переход: если утверждение справедливо при некотором $n$, то оно справедливо при $n+1$ (физически это соответствует добавлению к имеющемуся набору монет одной трёхдолларовой монеты).

Ч. т. д.

[Евгений Машеров]

Не-индуктивный вариант. Также начинающийся с установления того, что требуемая к выдаче сумма при делении на 3 может иметь остаток 0, 1 или 2.
Если остаток 0 - то выдаём трёшками. Для остатка 2 - нужна 1 пятёрка, для остатка 1 - две пятёрки. Суммы меньшие 8 не рассматриваются, 8 достигается 1 пятёркой, 10 двумя. Остальные суммы 1 или 2 пятёрками (или нулём) сообразно остатку, добирая трёшками.

[Gepidium]

Mihr в сообщении #1568389 писал(а):

всякое число $a$ представимо в виде $a=3n+t$, где $t=0$, $t=1$ или $t=-1$. В первых двух случаях $t$ совпадает с указанным остатком $r$, в третьем случае $t=r-3$.

Mihr
Немного недопоняла про третий случай. Почему выгодней представить остаток как $t=-1$, чем как $t=2$?

(Оффтоп)

А почему у Вас на профиле никнейм без цвета? Вы же ЗУ!