Наша цель - угадать загаданное число из множества целых чисел {1, 2, ..., n} при помощи вопросов. Каждое число (вопрос), про которое мы спрашиваем, имеет вес, равный этому числу, и мы можем получить один из трех возможных ответов:

• "Ваше число меньше, чем загаданное", или
• "Да, это оно!", или
• "Ваше число больше, чем загаданное".

При заданном значении n, оптимальная стратегия минимизирует суммарный вес (т.е. сумму всех заданных вопросов) для наихудшего возможного случая. Т.е.:

При n=3, лучшее, что можно сделать, очевидно, спросить про число "2". Ответ мгновенно приведет нас к загаданному числу (при суммарном весе = 2).

При n=8, можно попытаться воспользоваться стратегией "двоичного поиска": первый вопрос будет про "4", и, если загаданное число больше, чем 4, то понадобится еще одна или две попытки-вопроса.
Пусть второй вопрос будет про "6". Если загаданное число все еще больше 6, то потребуется третий вопрос, чтобы выяснить - загаданное число равно 7 или 8.
Таким образом, третий вопрос будет про "7", и общий вес этого наихудшего случая оставит 4+6+7= 17.

Можно существенно уменьшить вес наихудшего случая при n=8, задав первый вопрос про "5".
Если окажется, что загаданное число больше 5, то второй вопрос будет про "7", и тогда мы наверняка узнаем загаданное число (при общем весе 5+7=12).
Если же окажется, что загаданное число меньше 5, то второй вопрос будет про "3", а если загаданное число будет меньше чем 3, то третий вопрос будет про "1". Итого, общий вес составит 5+3+1=9.
Т.к. 12>9, то вес наихудшего случая при такой стратегии будет равен 12. Это лучше результата, который был получен выше при помощи стратегии "двоичного поиска". Кроме того, этот результат не хуже результата любой другой стратегии.
Таким образом, мы только что описали оптимальную стратегию при n=8.

Пусть C(n) - вес наихудшего возможного случая, достигнутый оптимальной стратегией для n чисел, описанный выше.
Таким образом, C(1) = 0, C(2) = 1, C(3) = 2 и C(8) = 12.
Аналогично, C(100) = 400 и C(n) = 17575.

Найдите C(n).