Изменения
Нет описания правки
Убедимся также, что необходимую сумму (<tex>n - 1</tex>) всегда можно набрать. Зафиксируем размер алфавита равным <tex>n = 2^k</tex>. Теперь вспомним неравенство, которым связаны <tex>n</tex> и <tex>L</tex>: <tex> n \le 2^L </tex>. Возьмем минимально возможное значение <tex>L</tex> такое, что <tex>2^L = n</tex>. По условию у нас есть по <tex>n</tex> монет номинала <tex>2^{-i}</tex>, где <tex>1 \le i \le L</tex>. Попробуем посчитать суммарную стоимость имеющихся монет:
<tex dpi = "150160">\frac{n}{2^1} + \frac{n}{2^2} + \dots + \frac{n}{2^L} </tex>
Поскольку <tex>n = 2^L</tex>:
<texdpi = "160">\frac{2^L}{2^1} + \frac{2^L}{2^2} + \dots + \frac{2^L}{2^L} = 2^{L - 1} + 2 ^ {L - 2} + \dots + 2^{L - L} = 2^L - 1 = n - 1 </tex>
Таким образом, мы набрали необходимую сумму, используя все предметы. Но так как мы рассматривали граничный случай, при бОльших значениях L данную сумму гарантированно можно набрать.
