|
|
 |
Условие
В некотором царстве, в некотором государстве было выпущено неограниченное
количество монет достоинством в n1, n2, n3, ... копеек, где
n1 < n < 2 < n3 < ... – бесконечная последовательность, состоящая из натуральных чисел. Докажите, что эту последовательность можно оборвать, то есть найдётся такое число N, что любую сумму, которую можно уплатить без сдачи выпущенными монетами, на самом деле можно уплатить только монетами достоинством в n1, n2, ..., nN копеек.
Решение
Обозначим через d наибольший общий делитель всех данных чисел и через ds – наибольший общий делитель чисел n1, n2, ..., ns. Поскольку
d1 ≥ d2 ≥ d3 ≥ ..., то dk = dk+1 = ... = d для некоторого k ≥ 2. Возьмём числа n1, ..., nk и рассмотрим все суммы, которые можно уплатить этими монетами. Эти суммы, расположенные в порядке возрастания, с какого-то места образуют арифметическую прогрессию с разностью dk = d; эту же арифметическую прогрессию образуют и суммы, полученные из первоначального бесконечного набора монет {ni}, 1 ≤ i < ∞. Поэтому, добавив к монетам n1, ..., nk необходимое количество монет nk+1, ..., nN, не попадающих в
указанную арифметическую прогрессию, получаем искомый конечный набор монет
n1, n2, ..., nN, которыми можно уплатить все возможные суммы, образованные из исходного набора монет n1, n2, n3, ... .
