Определить одно число из 1000, задав 10 вопросов, «Софизмы, ребусы...». Сообщение #8. Задача 38. Решение и ответ. Опции

[Николай Петрович]

Представьте себе, что ваш друг загадал некоторое целое число в промежутке от 1 до 1000. Чтобы угадать задуманное число, вы будете задавать вопросы. Условимся, что на все вопросы ваш друг будет отвечать только "да" или "нет".

Может показаться невероятным, что достаточно всего лишь десяти вопросов, чтобы наверняка отгадать любое задуманное целое число в промежутке от 1 до 1000. Однако это так.

Сообразите, какие вопросы надо задавать.

Если бы я знал теорию информации, мой ответ был бы иным. А сейчас, как говорится, не стреляйте в пианиста...
Гуманитариям, вероятно, вспомнится игра в дружеской компании, когда кому-то предлагают определить, кого из присутствующих задумали остальные в его отсутствии. Отгадывающий может задавать лишь те вопросы (о приметах задуманного человека, о расположении в алфавите первой буквы его имени и т. п.), на которые может быть дан утвердительный или отрицательный ответ. Эта игра, по-моему, интересна тем, что в ней отгадывающий проявляет изобретательность в придумывании разнородных вопросов. Но это воспоминание, по-моему, не помогает решению поставленной сейчас задачи.

Мне помог решить эту задачу прочитанный когда-то способ поимки льва в пустыне Сахара.
Надо всю пустыню разделить забором на две равные по площади части и посмотреть, в какой из них находится лев. Эту часть разделить забором тоже на две равные части и так далее до получения участка такой малой площади, которая позволяет считать, что лев пойман. Если лев своевременно не догадается о плане ловца и не загрызёт его, то успех ловцу обеспечен.
Почему важна одинаковость площадей по обе стороны каждого из заборов? Потому что даже недогадливый лев, заметив возводимые заграждения, просто из стремления к свободе будет уходить на участок с большей площадью.
Применительно к построению вопросов для определения задуманного числа это означает следующее.
Попробуем построить первый вопрос, исходя из разделения всего количества чисел не на 500 и 500, а, например, на 700 и 300. Здесь возможны два варианта. Первый: одна группа чисел — это от 1 до 300, вторая — от 301 до1000. Этому соответствует вопрос: «число больше 300?» или равноценный ему вопрос «число меньше 301?». Второй вариант: одна группа чисел — от 1 до 700, вторая — от 701 до 1000. Этому соответствует вопрос «число больше 700?» или равноценный ему вопрос «число меньше 701?».
Задавая один из этих четырёх вопросов, мы можем получить такой ответ, который сузит область поисков с 1000 до 700, а не до 500, как в случае разделения на равные части. В дальнейшем нам может нехватить позволенных десяти вопросов.
Итак, максимум информации из каждого ответа мы извлечём, если каждое множество чисел будем делить на две равные части.

Вот пример того, как можно заданием десяти вопросов определить задуманное число 1. Все ответы здесь будут отрицательными.

Первый вопрос: число больше 500? Второй вопрос: число больше 250? Третий: число больше 125? Четвёртый: число больше 63? Пятый: больше 32? Шестой: больше 16? Седьмой: больше 8? Восьмой: больше 4? Девятый: больше 2? Десятый: больше 1?

Решением этой задачи будет инструкция по составлению вопросов, учитывающая все возможные ситуации. Начало положено, попробуйте самостоятельно продолжить. Требуется исследовать последствия того, что группу из 125 чисел приходится разделять на две неравные части, и учесть это при составлении инструкции.

[Николай Петрович]

Мне не вполне нравится название «дерево возможных ответов», но более удачного не нашёл.

Дерево возможных ответов показывает, насколько уменьшается область поиска после получения ответа на очередной вопрос. В предыдущем рисунке показаны три ступени его ветвления для случая, когда вопросы удовлетворяют требованию, изложенному в предыдущем сообщении.
Это дерево дорисовано до конца для случая, когда задуманное число находится в пределах от 1 до 16.





Всего в этих рисунках имеется десять ступеней ветвления. Это показывает, что для определения одного числа из 1000 достаточно получить ответы на десять вопросов.

Теперь посмотрите на дерево возможных ответов, нарисованное для случая, когда содержание первого вопроса не соответствовало упомянутому требованию. Задающий вопросы решил один раз рискнуть в надежде на удачу и спросил одно из двух: «число больше 750?» или «число больше 250?». Ему в равной степени не повезёт, если на первый вопрос ответят «нет» или на второй вопрос ответят «да». Просто в первом случае он будет искать задуманное число среди 750 первых чисел, а во втором — среди последних 750 чисел из тысячи. Вот рисунки, соответствующие первому случаю.







В этом случае ответов на десять вопросов будет достаточно только для того, чтобы определить каждое третье число натурального ряда: 3, 6, 9, 12 и т. д. В остальных случаях потребуется задать одиннадцать вопросов.