Ниасилил?

[VVV]

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

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

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 вопросов.

[Smith]

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

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

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 вопросов.

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

[VVV]

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

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

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 вопросов.

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

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

[Toxa]

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

[Муслим]

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

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

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

[Илья]

Ну да 2¹⁰

[iPhonograph]

Из неравенства 14*1000>2¹³ следует недостаточность 13 вопросов.

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

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

[VVV]

Из неравенства 14*1000>2¹³ следует недостаточность 13 вопросов.

А как это доказать?

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

[iPhonograph]

Так как, если загадано одно и то же число, получены одинаковые ответы на соответствующие вопросы,

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

[VVV]

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

[iPhonograph]

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

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

[VVV]

Так как, если загадано одно и то же число, получены одинаковые ответы на соответствующие вопросы,

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

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

[iPhonograph]

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

[VVV]

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

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

[zhekas]

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