Олимпиадная задача по системам счисления и теории алгоритмов: оптимальные вопросы

Пусть a₁=2, a₂=3, a_i=a_i-1+a_i-2для i3. Тогда a10=144. Докажем по индукции, что среди не менее, чем a_i чисел, загаданное число нельзя угадать, заплатив менее, чем i+1рубль.

Для i=1и i=2это верно.

Пусть чисел не менее, чем a_i . Тогда либо множество M чисел, выделенных в первом вопросе, содержит не менее a_i-2чисел (первый случай), либо множество чисел, не попавших в M , содержит не менее a_i-1чисел (второй случай). В первом случае, если загаданное число попало в M , то за ответ нужно заплатить 2 рубля, и, по предположению индукции, еще не менее(i-2)+1рублей для того, чтобы угадать число, т.е. всего не менее i+1 рублей. Во втором случае, если загаданное число не попало в M , то нужно заплатить 1 рубль за ответ и не менее чем(i-1)+1рубль за угадывание числа, т.е. вновь всего не менее чем i+1рублей.

Алгоритм отгадывания числа ясен из предыдущих рассуждений: на каждом шаге множество M из a_i чисел, содержащее загаданное число, нужно разбивать на множества M₁ из a_i-2чисел и M₂ из a_i-1чисел, и задавать вопрос о принадлежности числа множеству M₁ .

11 рублей.