Взвешивания и количество информации

Заметим, что Покажем, что можно выбрать номиналов так, чтобы с помощью не более чем монет можно было уплатить без сдачи любую сумму от до рублей.

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

Пусть теперь Монетный двор изготовит монеты с номиналами и рублей при Любое число от до единственным образом представляется в виде где числа могут принимать значения от до (Фактически, это разложение числа в девятеричной системе счисления.) Как показано выше, сумма может быть получена не более чем двумя монетами. Таким образом, вся сумма может быть получена не более чем монетами указанных номиналов, что и требовалось.