Задачка на энтропию

[Добрая Кобра]

Помогите  отгадать загаданное число от 1 до 200, используя пять вопросов. Варианты ответа отвечающего только: Да, нет, не знаю.
Существует три варианта ответа, один из них считается немножко жульническим (но я не знаю ни одного).

Чтобы было понятнее: можно использовать  вопросы типа : Это число находится в промежутке от одного до ста?
И ход рассуждений напишите, пожалуйста

[ruslik]

Как можно что-то отгадать если на все 5 вопросов отвечающий даст ответ: не знаю ? Чушь какая-то Вы точно поняли условие ?

[AlexK]

совсем не чушь. очевидно подразумевается, что отвечающий всегда говорит правду.

[AlexK]

похоже я понимаю в каком направлении надо двигаться

стандартное решение подобной задачи это бисекция i.e. деление набора чисел на 2. i.e. первый вопрос: это число больше 100? если нет, то след вопрос: это число больше 50? и т.д.
к сожалению таким способом угадать число от 1 до 200 за 5 попыток нельзя. Но это считая, что у отвечающего есть только два варианта ответа "ДА" и "НЕТ".
так что, чтобы решить надо использовать вариант "не знаю".

Для этого можно использовать похожий трюк, но с разбивкой чисел на три части.  отвечающему можно задать такой вопрос: Если число меньше или равно 66 отвечай "ДА", если число между 67 и 133 отвечай "ДА" если больше 133 отвечай "не знаю".

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

[ruslik]

совсем не чушь. очевидно подразумевается, что отвечающий всегда говорит правду.

Серьёзно ? Тоесть отвечающий может знать число, но не знать к примеру в каком интервале оно находится ? Вычурно Вы наверно имеете ввиду что не знаю можно использовать чтобы не говориь да или нет.

Я склоняюсь к тому что Добрая Кобра недостаточно ясно поняла условия задачи. И что теперь смысл состоит в самостоятельном додумывании и решении ? Мне как-то недосуг И вообще при чём тут энтропия ? Добрая Кобра хоть догадывается о значении термина ?

Если следовать Вашей догадке, AlexK, то полный интервал должен быть 66*3=198. Но даже в этом случае на 5-ом шаге Вам придётся выбрать между 2-мя числами, т.е. отгадка не гарантирована

[Добрая Кобра]

ruslik,

Я склоняюсь к тому что Добрая Кобра недостаточно ясно поняла условия задачи. И что теперь смысл состоит в самостоятельном додумывании и решении ? Мне как-то недосуг И вообще при чём тут энтропия ? Добрая Кобра хоть догадывается о значении термина ?

Догадываюсь, догадываюсь  и о значении термина и о том, что Вы решить задачку не можете Условия я не понимаю, это правда, но  передала я их точно, слово  в слово.

то полный интервал должен быть 66*3=198. Но даже в этом случае на 5-ом шаге Вам придётся выбрать между 2-мя числами, т.е. отгадка не гарантирована

А в условии оговаривается, что вариантов ответа три. Один нашелся, СПАСИБО Вазу под цветочек не подарю.
AlexK, алгоритм  - класс, ОГРОМНОЕ спасибо 

[sergsl]

можно составлять сложные вопросы составляющие взаимоисключающую систему. Что-то типа: " это четное число заканчивающееся на 2 ?" и так далее в зависимости от полученного ответа

[ruslik]

Ну не решил, Добрая Кобра, согласен AlexK решил в собственном варианте постaновки задачи Молодец

[Добрая Кобра]

sergsl,

можно составлять сложные вопросы составляющие взаимоисключающую систему. Что-то типа: " это четное число заканчивающееся на 2 ?" и так далее в зависимости от полученного ответа

Замечательная идея, спасибо

[AlexK]

Если следовать Вашей догадке, AlexK, то полный интервал должен быть 66*3=198. Но даже в этом случае на 5-ом шаге Вам придётся выбрать между 2-мя числами, т.е. отгадка не гарантирована

отгадка гарантирована т.к. 3^5 > 200.

[ruslik]

отгадка гарантирована т.к. 3^5 > 200.

Признаюсь я не понял при чём тут 3^5 и возможно я не понял Вашего решения. Вот что я понял. Вы делаете разбивки каждый раз на три интервала:

шаг 1    1-66     67-132    133-200  в третьем интервале не 66 цифр, а 68, но давайте брать всегда первый.
шаг 2    1-22    23-44        45-66
шаг 3    1-7        8-14        15-22  третий интервал содержит не 7 цифр, а 8, ну Бог с ним берём первый.
шаг 4    1-2        3-4            5-7    третий интервал содержит не 2 цифры, а 3, ну Бог с ним берём снова первый.

Итак на 5-ом шаге (последнем как я понял) Вам предлагается выбрать между цифрой скажем 1 и 2. Как я могу это угадать на 100 % ?

Что в моём рассуждении не верно ? Всё ? :lol: :lol: :lol:

[AlexK]

замечаний два

1) на первом шаге непонятно зачем разбивать на 66, 66 и 68 чисел. проще разбить на 66, 67 и 67
2) в худшем случае на конечном шаге остается даже не 2, а 3 цифры и один (5й) вопрос.
Но никаких проблем здесь не вижу, используется тот же трюк. Честно говоря, удивлен что вы тут не смогли догадаться.

А решение на конечном шаге такое, если осталось числа a, b, и c, то задается вопрос "Если это число a отвечай "Да", если  b то "Нет", если c то "Не знаю".

[ruslik]

Ага, ясно. Вообще довольно дебильная задача. Ну да и хрен с ней

[AlexK]

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

[дядя Сережа]

1) на первом шаге непонятно зачем разбивать на 66, 66 и 68 чисел. проще разбить на 66, 67 и 67

Разбивать можно на любые интервалы и любым способом (и решений тут не 5, а фигова туча, если за одтельное решение принимать каждое новое разбиение множества 1..200), важно, чтобы в результате получалось при примерно одинаковые множества. И тогда имеем максимальное покрытие: 3 в пятой степени.

Но есть одна непонятка: все решения заставляют отвечать "не знаю", хотя отвечающий четко знает. Если настаивать именно на незнании, тогда все становится гораздо менее очевидным.

[ruslik]

Ну я так понимаю, дядя Сережа, это не не знаю, а третье квантовое состояние квантового компа. Тоесть ни 1 ни 0, а не знаю. Если у компа будет 200 квантовых состояний тогда ответ может быть получен за один шаг. А реально даже меньше чем за один шаг если брать комбинации состояний. В смысле потребуется меньше чем 200 состояний.

[AlexK]

Разбивать можно на любые интервалы и любым способом

серьезно? ок, если можно на любые то делаю так:
1 шаг: {1}, {2}, {>2}, допустим число в 3м интервале (>2), тогда на 2м шаге разбиваю этот интервал на
{3}, {4}, {>4}, и т.д. в итоге на пятом шаге может оказаться что число в интервале { от 9 до 200}.

И как за 1 оставшийся вопрос узнать какое из чисел от 9 до 200 было загадано?

[ruslik]

Разбивать можно на любые интервалы и любым способом (и решений тут не 5, а фигова туча, если за одтельное решение принимать каждое новое разбиение множества 1..200), важно, чтобы в результате получалось при примерно одинаковые множества. И тогда имеем максимальное покрытие: 3 в пятой степени.

Но есть одна непонятка: все решения заставляют отвечать "не знаю", хотя отвечающий четко знает. Если настаивать именно на незнании, тогда все становится гораздо менее очевидным.

AlexK, тут опечатка, имеется ввиду три, а не при.

Короче дядя Сережа имел ввиду что такие разбиения как:

(1-20;40-60;80-106)   (21-39;61-79;107-132)   (133-200) это суть эквиваленты решаемые таким же способом и гарантирующие ответ за 5 шагов. Таких разбиений на подмножества действительно дофига что он, видимо, и имел ввиду

Короче разбиение идёт не на 3 непрерывных интервала, а на три группы произвольным образом сконструированных подмножества с одним лишь условием что суммарное число элементов в них должно было одинаковым насколько это возможно в случае 200 элементов (на первом шаге; на других соответственно ALL/3), к примеру 66,67,67.

[AlexK]

ок. понятно!

[дядя Сережа]

AlexK, извиняюсь за неточную формулировку. Точная: разбивать можно на любые множества. Интервалы тут совершенно ни при чем.

ruslik, про квантовый комп ни черта не понял. Тут используется обычная троичная логика.

[Добрая Кобра]

дядя Сережа,

Точная: разбивать можно на любые множества.

Пожалуйста, не сочти за труд показать на примере

Например, с цифрой 36.

[ruslik]

дядя Сережа, я имел ввиду что в принципе квантовый комп может решать такое с использованием меньшего числа логик. Да не важно, я в этом в общем не спец. Показалось просто.

[дядя Сережа]

Добрая Кобра, не понял, а при чем тут 36?

[Кот Учёный]

Добрая Кобра, В смысле, если ты загадала цифру 36?
Давай попробуем. Я пробовала на бумажке вчера названный тут троичным метод.

1) от 1 до 66 - да     от 67 до 133 - нет     от 134 до 200 - не знаю.
Ответ - да.

2) от 1 до 22 - да     от 23 до 44 - нет     от 45 до 66 - не знаю.
Ответ - нет.

3) от 23 до 30 - да     от 31 до 37 - нет     от 38 до 44 - не знаю.
Ответ - нет.

4) от 31 до 33 - да     от 34 до 36 - нет     от 37 - не знаю.
Ответ - нет.

5) 34 - да        35 - нет         36 - не знаю.
Ответ - не знаю.


Все, пять шагов и ответ ты вычисляешь просто.

[дядя Сережа]

Кот Учёный, а у меня квантовый компьютер (по руслику) и он выдает правильный ответ за один шаг:

1) от 1 до 35 - нет, 36 - да, от 37 до 200 - не знаю. Ответ: да.
Все, задача решена