ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 109949
Темы:    [ Числа Фибоначчи ]
[ Выигрышные и проигрышные позиции ]
[ Линейные рекуррентные соотношения ]
[ Системы счисления (прочее) ]
[ Оценка + пример ]
Сложность: 6-
Классы: 8,9,10,11
В корзину
Прислать комментарий

Условие

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

Решение

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

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

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

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

Ответ

11 рублей.

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

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

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .