Теоретико-числовые свойства чисел Фибоначчи

Пусть для Тогда Докажем по индукции, что среди не менее, чем чисел, загаданное число нельзя угадать, заплатив менее, чем рубль. Из этого утверждения будет следовать, что необходимо потратить хотя бы рублей.

Для и это верно.

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

Алгоритм отгадывания числа ясен из предыдущих рассуждений: на каждом шаге множество из чисел, содержащее загаданное число, нужно разбивать на множества из чисел и из чисел, и задавать вопрос о принадлежности числа множеству