Рюкзак

Известно, что в двоичном представлении степеней двойки присутствует лишь одна единица: 2^0=1, 2^1=10, 2^2=100, ..., 2^8=100000000. Видим, что в двоичной записи числа 105 единицы стоят в 1-й, 4-й, 6-й и 7-й позициях (считаем слева направо). Значит, 105=2^0+2^3+2^5+2^6. Поскольку двоичное число 111111111 (девять единиц) равно 511 > 300, заключаем, что девяти чисел 1, 2, 4, 8, 16, 32, 64, 128, 256 вполне достаточно для представления любого натурального числа от 1 до 300 (и даже до 511).

Использование двоичной системы записи не является ключевым при решении этой задачи. Например, так же верны следующие девять чисел: 1, 2, 3, 7, 14, 28, 56, 112, 224.

Доказательство того, что искомый набор не может содержать менее девяти чисел:
Действительно, пусть у нас есть восемь чисел и любое число от 1 до 300 представимо в виде суммы разных чисел из этого набора. Используя наш набор, мы можем закодировать любое число от 1 до 300: пусть, например, число a равно сумме первого и третьего чисел нашего набора, тогда будем писать a=(1,0,1,0,0,0,0,0). Итак, число а получило свой код - строку из восьми символов, каждый символ или 0, или 1. Но нам надо закодировать триста чисел, а строк длины 8, как нетрудно видеть, всего 256. Значит, восьми чисел недостаточно.