Форум умных людей

Я задумал число от 1 до 1000. Отгадай его за наименьшее число вопросов, при условии, что я отвечаю только "да" или "нет".

Это число меньше 500?

как вам 1000 понравилась
вы уж больше или меньше возьмите
и в чем фишка

ради тебя - да! :)

это число меньше 250?

хе-хе.... а ты в курсе? тады давай ответ  :ura:

да

и это число 13 ;D ;D ;D ;D ;D ;D

это число меньше 125?

Коля, для тебя - ййессссссссссс!!!!!!!!!!! ;)

Илья, сколько вопросов на круг, чтобы 100% угадать при самом неблагоприятном случае?

где-то около 20-ти. Скорей всего можно и меньше. :read:

ну да. много меньше... ;)

 :beer:

ага  :drink:

Илюха, это даже не 24  :D

ничего смешного.
задал задачку- а потом начал дурачаться.
если вопросов меньше 20-ки, докажи.\
я загадал число. 1-1000
угадывай!

Илья, я не дурачился, просто решается за меньшее число вопросов. Это задача из олимпиады для 5 класса, там всего 10 вопросов на круг, не учитывая систем счисления. Если учитывать - то тоже 10, хотя всё гораздо проще.

Я задал эту задачу не столько для её решения (собственно, поскольку решение здесь вполне прогнозируемо), сколько для задания следующего вопроса: сколько потребуется (минимум) вопросов, если я могу 1 раз соврать?

зы: если кому интересно ;)

а взрослым дядям врать не прилично :)

ок. у тебя было правильное направление в определении числа, но можно поступить по-другому. к примеру, перевести число 1000 в двоичную систему счисления. так, 1000 в двоичной системе счисления составит 1111101000, т.е. 10-знаков в числе. остается спросить загадавшего о соответствии числа в каждом знаке. учитывая изложенное, попробуй определить, сколько вопросов понадобится, если можно 1 раз соврать (взрослым дядям) ;)

можно "поумничать", если кому интересно  :D

число целое? так?

Вторую задачу не понял...

Ну 21 (в самом неудобном случае)

да, верно.

можно меньше.

Сыграем?

Умник, ты умник! (шоб мну не забанили)  :D
это игра для одного, иначе ты проиграешь, а я вынужден буду выложить алгоритм.

думай.

В ЛС ???

  Очевидно, что во второй задаче  необходимо и достаточно 14 попыток.

Ничего не понимаю.
Можно решение увидеть?

Показать скрытый текст

да, Вы правы, 14 вопросов. но Ваш ответ меня поверг... Вы знали и подвели теорию под ответ, или... :roll:
зы: впрочем, спасибка вами засужена определенно  :bravo2:

   Просто это известная задача. Есть статья в "Кванте"  об этой задаче. Да и подсказка про цифры в двоичной системе счисления была очень сильная.

четное ли число? или же наоборот.
оно делится на 2 или на 3 ?

Илья по твоей схеме (делить на 2) вопросов вроде не больше 10-11

Ну да 2¹⁰

А как это доказать?
Предположу, что вы имели в виду, что мы обязательно отгадаем не только задуманное число, но и номер вопроса, на котором нам соврали, отсюда получим это неравенство.  Но по условию задачи нам не требуется отгадывать номер вопроса.  А вдруг есть такие хитрые 13 вопросов, из которых мы узнаем число, но не сможем достоверно определить номер ложного ответа?

Вы скажете, что если рассмотреть дерево разбора, то каждое задуманное число может привести в 14 возможных листьев этого дерева, что доказывает неравенство, т.к. выбором номера ложного ответа можно выполнить ответвление от "честной траектории" на любом из уровней этого дерева.  Но такое рассуждение неверно, потому что нам позволено задавать любые вопросы, в том числе о планах загадывающего на выбор номера ложного ответа.  Например, первый вопрос "А не соврёте ли вы, отвечая на первый вопрос?" не создаст ответвление на первом уровне дерева разбора, и ваша константа 14*1000 уменьшается...

  Докажем от противного. Предположим , что всегда можно отгадать за 13 вопросов. Существует  1000 вариантов для загадывания числа, 14 вариантов для номера вопроса, на который ответили ложь (условно номер равен бесконечности, если такого ответа нет). Всего есть 14000 комбинаций. Каждую из комбинаций можно реализовать на практике. Отгадывающий получает последовательность из "да"/"нет" длины 13. Этих последовательностей не более 2¹³. Для каждой последовательности ответов, которая может быть реализована, не может соответствовать комбинации с различными числами (иначе невозможно однозначно угадать). Но также для каждой последовательности ответов, которая может быть реализована, не может соответствовать различные комбинации с одинаковыми загаданными числами. Так как, если загадано одно и то же число, получены одинаковые ответы на соответствующие вопросы, то и номер вопроса, на который был дан ложный ответ совпадает, то есть комбинации совпадают. Следовательно, каждой последовательности ответов соответствует не более одной комбинации. Еще раз повторю, что каждую  комбинацию можно реализовать на практике. Значит, 14*1000<=2¹³. Но 14*1000>2¹³. Противоречие. Следовательно, нельзя со 100%-ной уверенностью отгадать за 13 вопросов.

в детерминированном случае - да.
но предположим, что мы сначала попросим загадывающего кинуть кубик и получить случайное число, которое нам неизвестно, и задавать вопросы мы будем о паре (задуманное число, случайное число), и после всех ответов мы не сможем определить случайное число, а следовательно, и номер ложного ответа.

  Утверждение доказано при условии выполнения естественного условия, что задаются вопросы, для которых один ответ является истиной, а другой --- ложью. Если же разрешить задавать вопросы, для которых любой ответ является ложью (например, "верно ли утверждение, что вы сейчас скажите "нет"?"), то ситуация становится другой. В этом случае достаточно 11 вопросов. Сначала заставляем солгать, а затем обычным способом узнаем число. Но в этом случае задача становится противоречивой, так как можно задать этот провокационный вопрос дважды. Если же разрешить вопросы, для которых любой ответ является истиной, то требуется модификация доказательства.

Может.  Я привёл пример со случайным числом.

  Я не вижу здесь указания на ошибку. Какое отношение имеет рассуждение со случайным числом к конкретной задаче?

потому что условие не обязывает нас ограничиваться вопросами из области арифметических свойств задуманного числа

  Пожалуйста, только пусть выполняется естественное условие, что задаются вопросы, для которых один ответ является истиной, а другой --- ложью.

Если задавать только те вопросы, которые относятся к нахождению числа. И один раз может соврать, то какая должна быть тактика.

Вот этот логический вывод не доказан.

Может соврать или должен соврать?

Может

То есть, если не врал, то в конце нужно два раза число переспросить? :)

Я так понимаю задавать вопросы можно только из серии: " принадлежит ли число данному подмножеству". И отвечающий может один раз соврать. Тут говорят, что за 14 вопросов можно наверняка узнать число. Вот я и спрашиваю какая должна быть стратегия у задающего вопросы.

    Это очевидно, если выполняется естественное условие, что задаются вопросы, для которых один ответ является истиной, а другой --- ложью.

  10 вопросов о i-ой цифре двоичного представления. В результате остается 11 кандидатов, при этом только для одного из кандидатов (а) остается возможность получить лживый ответ. Для простоты обозначений пусть эти кандидаты будут 1,2,3,4,5,6,7,8,9,10,а. Следующий вопрос --- "x\in {1,2,3,4,5,6,7}?" В случае положительного ответа остается лишь 8 вариантов {1,2,3,4,5,6,7,а}, а у отвечающего нет больше возможности лгать. Поэтому за 3 попытки легко отгадать искомое число. В случае же негативного ответа задаем вопрос: "x\in {8,9,10}?" Если получаем положительный ответ, то остается лишь 4 варианта {8,9,10,а}, а у отвечающего нет больше возможности лгать. Поэтому за 2 попытки легко отгадать искомое число. Если получаем отрицательный ответ, то искомое число --- а. Из неравенства 14*1000>2¹³ следует недостаточность 13 вопросов.

это не очевидно
например, вопрос: "равен ли нулю младший бит (задуманное число) XOR (случайное число) ?"
представьте два сеанса разгадывания
число задумано оба раза одно и то же
ответы одинаковые
но номер ложного ответа - разный, потому что случайное число для каждого сеанса своё

  Хорошо, пусть в вопросах есть случайные величины. Если загадывающий сообщит значения этих величин, то задача сводится к "нормальной". Лишняя информация не может помешать в отгадывании, она может только помочь. А раз 13 вопросов мало для "нормальной" задачи,  следовательно, 13 вопросов не хватит и в случае  задачи со случайными величинами.

так-так, это что же получается?  я указываю нерассмотренный случай в доказательстве, его рассматривают, но где гарантия отсутствия новых нерассмотренных случаев?
доказательство в том виде, как оно есть, неполно
дайте универсальное доказательство, которое не оставляет сомнений

  Проще ограничить вопросы. Обсуждение выявило "дырки" и слабые места в доказательстве. Показало, что  не все очевидное является верным. :) Высветило интересные моменты. Но все же лучше изменить задачу, ограничив вопросы до разумных пределов.