IPB

Здравствуйте, гость ( Вход | Регистрация )

Активные темы за последние сутки
Новые сообщения с Вашего последнего посещения
Главная страница форума
Определить одно число из 1000, задав 10 вопросов, «Софизмы, ребусы...». Сообщение #8. Задача 38. Решение и ответ.
Николай Петрович
сообщение 21.12.2015, 17:53
Сообщение #1


Я такой же, как все: я не похож ни на кого другого.


Группа: Пользователь
Сообщений: 2080
Регистрация: 7.10.2014
Из: Москва
Пользователь №: 2324



Представьте себе, что ваш друг загадал некоторое целое число в промежутке от 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 - 2)
Николай Петрович
сообщение 7.6.2016, 18:23
Сообщение #2


Я такой же, как все: я не похож ни на кого другого.


Группа: Пользователь
Сообщений: 2080
Регистрация: 7.10.2014
Из: Москва
Пользователь №: 2324



Рекомендации по отгадыванию числа таковы.
Первый вопрос должен быть: «загаданное число больше 500?»
Ничуть не хуже был бы второй вариант вопроса: «загаданное число меньше 501?», но мы будем применять первый вариант.
Суть первого вопроса в том, что, разделив множество последовательных чисел от 1 до 1000 на две равные части, мы хотим узнать, в какой из этих двух частей находится загаданное число. Ответ «нет» будет означать, что число меньше или равно 500, то есть находится в пределах от 1 до 500. Ответ «да» — что оно находится среди чисел от 501 до 1000.
Математик сказал бы, что мы разделили множество, элементами которого являются числа натурального ряда от 1 до 1000, на два подмножества, содержащие равное количество элементов, и задаём вопрос: элементом какого из этих двух подмножеств является задуманное число.
Если бы мы были азартными игроками и разделили множество чисел на две существенно неравные части, например, в пропорции 3 к 1, то в случае благоприятного ответа мы были бы вдвое ближе к ответу и возможно, что нам хватило бы ответов на девять вопросов. В случае же неблагоприятного ответа мы смогли бы исключить из дальнейшего рассмотрения только четверть общего количества чисел и в дальнейшем нам могло бы не хватить ответов на десять вопросов.
Поэтому последующие вопросы должны быть построены аналогично первому и основываться на разделении подмножеств чисел на две по возможности равные части.

Прикрепленное изображение


Перед вами дерево возможных ответов на три вопроса типа «загаданное число больше n?». Для формулировки четвёртого и, возможно, следующих вопросов придется разделить нечётное множество чисел на две неравные части. Если разница в количестве чисел не будет больше единицы, то она несущественна для процесса отгадывания, ответов на десять вопросов будет достаточно. Дорисуйте дерево в той части, которая ведёт к числам 1, 2 и 3, и вы увидите, что необходимость разделять подможества чисел на две неравные части не усложняет отгадывание и что достаточно десяти (а в некоторых случаях и девяти) вопросов.

Я отказался от намерения написать решение в виде инструкции, потому что она получилась бы тяжёлой для восприятия.
Одна из написанных выше строк позволила вспомнить случай из практики и сочинить лингвистическую загадку (см. активную ссылку).
http://sobes.net/forum/index.php?s=&sh...ost&p=23529
Перейти в начало страницы
 
+Цитировать сообщение
Николай Петрович
сообщение 21.10.2017, 19:44
Сообщение #3


Я такой же, как все: я не похож ни на кого другого.


Группа: Пользователь
Сообщений: 2080
Регистрация: 7.10.2014
Из: Москва
Пользователь №: 2324



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

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

Прикрепленное изображение

Прикрепленное изображение

Прикрепленное изображение


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

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

Прикрепленное изображение

Прикрепленное изображение


Прикрепленное изображение

Прикрепленное изображение


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

Ответить в данную темуНачать новую тему
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 



RSS Текстовая версия Сейчас: 18.11.2017, 22:22