Разделы 
Дополнительно
Задача по математике - 1546
2019-01-19 
Загадано число от 1 до 144. Разрешается выделить одно подмножество множества чисел от 1 до 144 и спросить, принадлежит ли ему загаданное число. За ответ «да» надо заплатить 2 рубля, за ответ «нет» -1 рубль. Какая наименьшая сумма денег необходима для того, чтобы наверняка угадать число?
Решение:
Пусть $a_1 = 2, a_2 = 3, a_i = a_{i-1} + a_{i-2}$ для $i \geq 3$. Тогда $a_{10} = 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_1$ из $a_{i-2}$ чисел и $M_2$ из $a_{i-1}$ чисел, и задавать вопрос о принадлежности числа множеству $M_1$.
Ответ. 11 рублей.
Загадано число от 1 до 144. Разрешается выделить одно подмножество множества чисел от 1 до 144 и спросить, принадлежит ли ему загаданное число. За ответ «да» надо заплатить 2 рубля, за ответ «нет» -1 рубль. Какая наименьшая сумма денег необходима для того, чтобы наверняка угадать число?
Решение:
Пусть $a_1 = 2, a_2 = 3, a_i = a_{i-1} + a_{i-2}$ для $i \geq 3$. Тогда $a_{10} = 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_1$ из $a_{i-2}$ чисел и $M_2$ из $a_{i-1}$ чисел, и задавать вопрос о принадлежности числа множеству $M_1$.
Ответ. 11 рублей.
