Какое наименьшее количество натуральных чисел надо взять, чтобы любое число от 1 до 300 можно было представить в виде суммы подходящего набора различных указанных натуральных чисел.
При решении этой задачи участники широко использовали двоичное представление чисел. Например, 105=1101001. Известно, что в двоичном представлении степеней двойки присутствует лишь одна единица: 20=1, 21=10, 22=100, ..., 28=100000000. Видим, что в двоичной записи числа 105 единицы стоят в 1-й, 4-й, 6-й и 7-й позициях (считаем слева направо). Значит, 105=20+23+25+26. Поскольку двоичное число 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. Значит, восьми чисел недостаточно.