Разделы 
Дополнительно
Задача по математике - 13296
2023-08-14 
Я хочу предложить вам одну разновидность известной игры в «двадцать вопросов», суть которой такова. Я задумываю натуральное число, а вы должны отгадать его, задав не более двадцати вопросов, на каждый из которых можно ответить только «да» или «нет». Чему равно наибольшее чнсло, задумав которое, я все еще смогу получить от вас правильный ответ после двадцати вопросов?
Решение:
Если из конечного множества объектов выбран один, то наилучший способ, с помощью которого спрашивающий может его определить, заключается в следующем. На каждом шаге нужно выяснить, обладает ли данный объект свойством, которое есть ровно у половины «подозреваемых» объектов. В этом случае при любом ответе число «подозреваемых» объектов уменьшается ровно вдвое. Применяя такой способ, спрашивающий может, задав 20 вопросов, определить любое задуманное натуральное число, не превышающее $2^{20}$.
Например, на $i$-м шаге ($i = 1, 2, \cdots, 20$) можно задать вопрос: «Если число записать в двоичной системе, то будет ли его $i$-я цифра равна 1?» Отметим, что если на все вопросы мы получим ответ «нет», то искомое число 21-значно (в двоичной системе) и состоит из 1, за которой следуют 20 нулей, то есть равно $2^{20}$. Если хотя бы на один из вопросов получен ответ «да», то задуманное число, самое большее, 20-значно и полностью определяется после 20 ответов.
Я хочу предложить вам одну разновидность известной игры в «двадцать вопросов», суть которой такова. Я задумываю натуральное число, а вы должны отгадать его, задав не более двадцати вопросов, на каждый из которых можно ответить только «да» или «нет». Чему равно наибольшее чнсло, задумав которое, я все еще смогу получить от вас правильный ответ после двадцати вопросов?
Решение:
Если из конечного множества объектов выбран один, то наилучший способ, с помощью которого спрашивающий может его определить, заключается в следующем. На каждом шаге нужно выяснить, обладает ли данный объект свойством, которое есть ровно у половины «подозреваемых» объектов. В этом случае при любом ответе число «подозреваемых» объектов уменьшается ровно вдвое. Применяя такой способ, спрашивающий может, задав 20 вопросов, определить любое задуманное натуральное число, не превышающее $2^{20}$.
Например, на $i$-м шаге ($i = 1, 2, \cdots, 20$) можно задать вопрос: «Если число записать в двоичной системе, то будет ли его $i$-я цифра равна 1?» Отметим, что если на все вопросы мы получим ответ «нет», то искомое число 21-значно (в двоичной системе) и состоит из 1, за которой следуют 20 нулей, то есть равно $2^{20}$. Если хотя бы на один из вопросов получен ответ «да», то задуманное число, самое большее, 20-значно и полностью определяется после 20 ответов.
