Кто быстрее отгадает задуманное число?

[Smith]

Я когда-то загадывал эту задачу, но возможно тогда она была не ко времени, хотя попытки ее решить были и отчасти даже удавшиеся. Познакомился я с этой задачей на математической олимпиаде для 5 класса (по крайней мере с первой частью задачи). Ответ (минимальный) на вторую часть пришел лично ко мне много позже и после значительных усилий по его поиску. Мне эта задача нравится сочетанием простоты и сложности одновременно, поэтому решился выложить ее повторно.

Задача формулируется примерно так:
Я задумал число от 1 до 1000.
Вопросов два:
1)За какое минимальное количество ходов вы сможете его отгадать задавая мне вопросы, на которые я буду отвечать только "да" или "нет"?
2)тот же вопрос, только теперь я имею право 1 раз солгать.
Удачи.

[Lkob]

Первое - понятно. Т.е. Это число больше/меньше 500. Далее (к примеру было меньше) - тогда больше/меньше, чем 250 и т.д.

[Smith]

Первое - понятно. Т.е. Это число больше/меньше 500. Далее (к примеру было меньше) - тогда больше/меньше, чем 250 и т.д.

можно так. хотя нужно очень осторожно, т.к. только при правильном делении получается 10.
можно проще, но как для первого вопроса - не принципиально. зато если найти другое решение для 1 вопроса - проще будет с решением 2 вопроса.

[Maxonya]

А может быть еще на четное-нечетное ориентироваться?

[buka]

А может быть еще на четное-нечетное ориентироваться?

Мне этот подход нравится больше. Особенно, если требуется исправить один ложный ответ. В принципе больше-меньше эквивалентно (по сути и тот и другой подходы определяют биты двоичного представления числа - больше-меньше нацинает со старшего бита, чёт-нечёт - с младшего)
Итак чёт-нечёт:
1) Число чётное?
2) Его целочисленная половина - чётна?
3) Целочисленная четверть - чётная? и т.д. для 1/8, 1/16, ..., 1/512...
Так мы получим 10 бит, но 1 может быть ложным.
Требуется ещё 5 вопросов:
11) Первые 10 ответов правдивы?
12) Первые 5 ответов и 11 - правдивы?
13) Ответы 1,2,3,6,7 и 12 - правдивы?
14) Ответы 1,2,6,8,9 и 13 - правдивы?
15) Ответы 1,3,5,7,9 и 14 - правдивы?
В принципе, если не требуется зафиксировать двойную ложь, то можно не включать в вопросы "и 12", "и 13" и т.д.

[Хэлл]

Да просто задавать один и тотже вопрос два раза, а если получится разногласие, то задать на этом числе и третий раз ))

[Lkob]

//скрытый текст, требуется сообщений: 213//

[Lkob]

//скрытый текст, требуется сообщений: 213//

[buka]

Да просто задавать один и тотже вопрос два раза, а если получится разногласие, то задать на этом числе и третий раз ))

Наша задача - задать минимум вопросов.
Ваш же подход требует как минимум 2*log₂N вопросов для числа N
Мы же оцениваем число вопросов в log₂N + log₂(log₂N)

[Lkob]

Оптимальный алгоритм - решить уравнение:

//скрытый текст, требуется сообщений: 213//

А дальше задавать нужные цифры.

P.S. Скажите ответ, который будет круче - буду просто В ВОСТОРГЕ!

[buka]

Оптимальный алгоритм - решить уравнение:

//скрытый текст, требуется сообщений: 213//

А дальше задавать нужные цифры.

P.S. Скажите ответ, который будет круче - буду просто В ВОСТОРГЕ!

Так Вы - конкретнее - решите для 1000.
Дайте число вопросов и мы посмотрим.
Муторно для 1000 - дайте для 16.

[Smith]

А может быть еще на четное-нечетное ориентироваться?

Итак чёт-нечёт:
1) Число чётное?
2) Его целочисленная половина - чётна?
3) Целочисленная четверть - чётная? и т.д. для 1/8, 1/16, ..., 1/512...
Так мы получим 10 бит, но 1 может быть ложным.
Требуется ещё 5 вопросов:

может быть я не совсем понял объяснение, но что-то не верно
предположим, число 6.
1)да
2)нет
3)нет
4)нет (т.к. целочисленной восьмой части от этого числа нет, или имеем ввиду, что 0 - четное число?)
5)...10) нет (аналогично)

с вопросами 11-15 подход верный, но скажите однозначно сколько вопросов получается минимум? и еще не понял термин "двойная ложь", ведь по условию соврать можно только 1 раз..

[Smith]

//скрытый текст, требуется сообщений: 213//

так какой ответ на второй вопрос?

[buka]

А может быть еще на четное-нечетное ориентироваться?

Итак чёт-нечёт:
1) Число чётное?
2) Его целочисленная половина - чётна?
3) Целочисленная четверть - чётная? и т.д. для 1/8, 1/16, ..., 1/512...
Так мы получим 10 бит, но 1 может быть ложным.
Требуется ещё 5 вопросов:

может быть я не совсем понял объяснение, но что-то не верно
предположим, число 6.
1)да
2)нет
3)нет
4)нет (т.к. целочисленной восьмой части от этого числа нет, или имеем ввиду, что 0 - четное число?)
5)...10) нет (аналогично)

с вопросами 11-15 подход верный, но скажите однозначно сколько вопросов получается минимум? и еще не понял термин "двойная ложь", ведь по условию соврать можно только 1 раз..

1. Я думаю, можно вложиться в 14 вопросов.
2. Касательно двойной лжи: речь идёт об усложнении условия задачи, а именно, определить исконное число, если допускается 1 ложный ответ и заловить ситуацию, если 2 ложных ответа (в этом случае число определить не удастся, а вот убедиться, что ложных ответов - 2 можно).

[Smith]

соррри, тайм-аут((
2. об этом вопроса не было, хотя интересно..
1. да, 14 и у меня (кодировка по 2 и далее, когда не хватает, - по 3)
начало: перевести все и вся в двоичную систему, тогда все просто с 1-м вопросом и проще со 2-м
в целом: респект и уважуха!