#algorithm
#алгоритм
Вопрос:
Я почти уверен, что вы, ребята, знаете об игре «Угадай число» (кажется, здесь уже есть довольно много вопросов), где Алиса думает о натуральном числе, а Боб пытается его угадать. Алиса отвечает либо словами «Ты угадал», «Низкий», «Высокий». Обычная стратегия, которую может использовать Боб, — это выполнить двоичный поиск, который угадал бы число в O (log n) догадках, где n — это число, о котором думала Алиса.
Меня всегда интересовал вариант, в котором Алисе разрешалось лгать.
Предположим, теперь Алисе было разрешено лгать постоянное количество раз (заранее известное как Алисе, так и Бобу), но лгать разрешалось только при ответе «Высокий», «Низкий» (т. Е. если Боб угадывает число правильно, она должна это признать).
Возможно ли все еще, что Боб может угадать число в O (log n) догадках?
Что, если бы Бобу разрешили дополнительные запросы типа «Сколько раз ты уже солгал?» (какая Алиса должна ответить правдиво)? Возможны ли еще запросы O (log n)?
РЕДАКТИРОВАТЬ: Что, если бы количество лжи тоже было разрешено равным O (logn), и дополнительными запросами были: Вы лгали более x раз? и Алисе было разрешено лгать о них…
Приношу извинения за РЕДАКТИРОВАНИЕ.
Комментарии:
1. Если количество разрешенной лжи — скажем, k — фиксировано и не зависит от n, Боб может просто задать каждый вопрос 2k 1 раз и отделается O (log (n)).
2. Просто задавайте каждый «стандартный» вопрос с вопросом «сколько раз вы солгали» — и соответствующим образом меняйте ответ. Результат: задано такое же количество вопросов, как если бы Алиса никогда не лгала.
3. Мне это нравится. Две немедленные мысли (1) как насчет отображения пространства на основе вероятностей (2) как бы выглядела схема для попытки определить правильные или неправильные ответы?
4. Я не был уверен, сколько вопросов я могу задать в вопросе. Я отредактировал, чтобы сделать количество ложей непостоянным, и разрешил Алисе лгать о том, сколько лжи… Извините, если это не по теме (я вижу итоговое голосование).
5. @Jim: Да, это интересно. Что-то вроде отказоустойчивого двоичного поиска 🙂
Ответ №1:
Запустите обычный алгоритм двоичного поиска. Либо ты получаешь ответ, либо ты получаешь несоответствие (пустой набор кандидатов). Если вы получаете несоответствие, Алиса, должно быть, солгала хотя бы один раз. Перезапустите двоичный поиск. Если я чего-то не упустил, после O (k * log (n)) шагов вы получите ответ (плюс нижняя граница того, сколько раз она солгала). Вам не нужно знать k априори.
Комментарии:
1. Я думаю, это было глупо: как только вы закончите, вы точно знаете, сколько раз она солгала. Что касается оптимизации, в худшем (детерминированном) случае, я не думаю, что вы сможете превзойти k * log (n), поскольку Алисе не нужно лгать до самого последнего вопроса в любом заданном запуске. Если вы можете победить это с помощью рандомизированного алгоритма, я не знаю; это хороший вопрос.
2. Я думаю, ключ в том, чтобы иметь возможность выбрать лучшую отправную точку (чем середина) для следующего раунда, как только вы получите нулевой набор.
3. Спасибо! Я хотел, чтобы это было просто, получилось слишком просто 🙂
4. @Dante: Я думаю, что это все еще просто нижняя граница, поскольку Алиса может солгать дважды или более, прежде чем вы достигнете несоответствия.
5. Для любых будущих поисковиков я также нашел эту страницу на math.stackexchange для более подробного решения: math.stackexchange.com/questions/172372 /…
Ответ №2:
Я думаю, что это все еще O (log n), потому что вы указали, что Алиса может лгать только постоянное количество раз. Это означает, что она может максимум умножить количество догадок, сделанных Бобом, на константу.
Представьте, что Алиса может солгать 5 раз. Теперь, независимо от того, когда Алиса лжет, в конечном итоге ей придется противоречить самой себе. Боб заметит это и сможет начать свой бинарный поиск заново. Алисе также запрещено лгать в пределах O (log n) догадок, иначе Боб угадает число правильно, и Алиса потеряет свой шанс.
Итак, в худшем случае, когда Алиса лжет пять раз, каждый / непосредственно перед/ Боб получает ответ, она просто заставила двоичный поиск Боба принять 6 * (log n) догадок (пять ложных один правильный ответ), что по-прежнему равно O (log n).