Олимпиадная задача по логике: сколько вопросов нужно задать, чтобы найти приз среди 100 коробок
Задача
Есть 100 коробок, пронумерованных числами от 1 до 100. В одной коробке лежит приз и ведущий знает, где он находится. Зритель может послать ведущему пачку записок с вопросами, требующими ответа "да" или "нет". Ведущий перемешивает записки в пачке и, не оглашая вслух вопросов, честно отвечает на все. Какое наименьшее количество записок нужно послать, чтобы наверняка узнать, где находится приз?
Решение
Так как порядок зачтения ответов на свои вопросы зрителю неизвестен, то он должен сделать безошибочный выбор, зная только количество ответов "нет". Если послано N записок, то количество услышанных ответов "нет" может принимать любые целые значения от 0 до N, то есть возможен N + 1 вариант. Это количество должно определять номер призовой коробки, поэтому его значение должно быть не меньше, чем количество коробок, то есть N ≥ 99.
Приведём пример набора из 99 записок, удовлетворяющий условию. Пусть зритель подаёт ведущему записки с однотипной фразой: "Верно ли, что номер коробки с призом не превышает числа K?" для всех K от 1 до 99. Предположим, что приз лежит в коробке с номером m. Тогда зритель услышит
m – 1 ответ "нет". Прибавив 1 к количеству услышанных ответов "нет", он определит номер призовой коробки.
Ответ
99 записок.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь