Задача 109949

Темы:    [ Числа Фибоначчи ] [ Выигрышные и проигрышные позиции ] [ Линейные рекуррентные соотношения ] [ Системы счисления (прочее) ] [ Оценка + пример ]

Сложность: 6- Классы: 8,9,10,11

Условие

Автор: Островский М.

Загадано число от 1 до 144. Разрешается выделить одно подмножество множества чисел от 1 до 144 и спросить, принадлежит ли ему загаданное число. За ответ да надо заплатить 2 рубля, за ответ нет – 1 рубль. Какая наименьшая сумма денег необходима для того, чтобы наверняка угадать число?

Решение

Пусть 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 рублей.

Источники и прецеденты использования

олимпиада
Название	Всероссийская олимпиада по математике
год
Год	1998
Этап
Вариант	4
Класс
Класс	10
задача
Номер	98.4.10.8