Задано число от 1 до n. За один ход можно выбрать произвольное подмножество множества чисел от 1 до n и спросить, принадлежит ли ему заданное число. При ответе «да» будет начислено a баллов, при ответе «нет» — b баллов.
а) Можно ли наверняка угадать число, получив не менее 16 и не более 21 баллов, если 
б) Может ли n быть равным 144, если известно, что число можно наверняка угадать, получив не менее 11 баллов, и при этом 
в) Какую наименьшую сумму баллов можно получить, чтобы наверняка угадать число, если 
Пункт в) переборный, решается при помощи компьютера.
Угадывающему следует выбирать подмножества так, чтобы как можно чаще услышать ответ «да» — чтобы набрать больше баллов. Поэтому ему следует делить множество чисел на части с большим и меньшим количеством чисел и спрашивать про меньшую часть. Если отвечающий скажет «да», то у угадывающего останется мало вариантов, и отвечающий не сможет много раз сказать «да». С другой стороны, если отвечающий скажет «нет», то вариантов останется больше, но за ответ «нет» начисляется меньше баллов. Угадывающему надо подобрать соотношение между количеством остающихся вариантов и разностью баллами за ответ «да» по сравнению с «нет».
а) Разделим числа на две равные группы и спросим про одну из них. Независимо от ответа, останется ровно 64 подозрительных числа. Продолжая делить пополам, мы будем получать 32, 16, 8, 4, 2, 1 подозрительное число. Это 7 вопросов, число угадано и число баллов не превосходит 21. Если оно меньше 16, будет задавать дополнительные вопросы про какое-нибудь другое число, получая ответы «нет» до тех пор, пока не наберем 16 баллов.
б) Да. Пусть 
а загадывающий при каждом ходе отвечает так, чтобы отбросилось не более половины возможных загаданных чисел. Тогда после первого вопроса останется не менее 72 кандидатов, после второго — не менее 36, затем 18, затем 9, затем 5. Итак, нужно не менее шести (а на самом деле восьми) вопросов, поэтому для гарантированного угадывания придется получить минимум 
баллов.
в) Будем считать, что 
— от того, что несколько больших чисел будут запрещены, нам может стать только легче угадать число. Обозначим за 
минимальное число баллов, достаточное для угадывания числа из x вариантов — очевидно, совершенно неважно, из каких именно x вариантов происходит угадывание. Ясно также, что — неубывающая функция и 
(мы можем получить на наш первый же вопрос ответ «да»).
Если есть x кандидатов, то мы разбиваем их на две группы, y и 
и спрашиваем про первую группу. При ответе «да» пользуясь оптимальным алгоритмом, мы получим 
баллов, при ответе «нет» — 
баллов. Значит, для такого разбиения гарантирующее число баллов равно 
Перебирая все значения y от 1 до 
мы, естественно, выберем из них то, для которого этот максимум минимален. Итак,
Приведем пример. Пусть 
Тогда при 
имеем
а при 
имеем
поэтому 
а оптимальный алгоритм — первым вопросом спросить про множество из одного числа.
Пользуясь этим соотношением, можно по очереди находить значения 
Но это очень долго, поэтому мы напряжем на этот перебор компьютерную программу:
program ball;
var
f: array [1..170] of integer;
x, y, a, b, c: integer;
begin
for x := 1 to 170 do f[x] := 0;
f[2] := 3;
for x := 3 to 170 do begin
c := 10000;
for y := 1 to x − 1 do begin
if (3 + f[y] > 1 + f[x − y]) and (3 + f[y] < c) then c := 3 + f[y];
if (3 + f[y] <= 1 + f[x − y]) and (1 + f[x − y] < c) then c := 1 + f[x − y];
end;
f[x] := c;
writeln('f(',x,')=', f[x]);
end;
end.
Получаем в результате ее работы следующие данные: 
Поэтому ответ 15.
Ответ: 15.
Комментарий.
На форуме у Ларина, где была предложена эта задача, ее условие понимают как-то по-другому.
Примечание. Рекомендуем сравнить эту задачу с задачей окружного этапа Всероссийской олимпиады школьников по математике 1998 год, 10 класс (см. ниже).
ЗАДАЧА:
Загадано число от 1 до 144. Разрешается выделить одно подмножество множества чисел от 1 до 144 и спросить, принадлежит ли ему загаданное число. За ответ «да» надо заплатить 2 рубля, за ответ «нет» — 1 рубль. Какая наименьшая сумма денег необходима для того, чтобы наверняка угадать число?
РЕШЕНИЕ:
ОТВЕТ: 11 рублей.