Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

задачка

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

Я загадываю число от 0 до 15 (включительно). Вам разрешается задать 7 вопросов, на каждый из которых возможные ответы - "да" или "нет". Я отвечаю на ваши вопросы, и мне разрешается соврать один раз (я могу и вообще не врать и ответить правильно на все вопросы, а могу на один какой-нибудь ответить неправильно).

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

Update: В комментах есть уже несколько верных доказательств, разной степени сложности. Я приведу здесь другое, особенно простое, которое в точности ещё никто не повторил, хотя подошли очень близко. За элжекатом.


Итак, A загадал число от 0 до 15, а Б его отгадывает. В двоичной записи это число записывается в четыре двоичных цифры (например, 7 это 0111 итп.).

Первые три вопроса Б - про первые три двоичных разряда числа. Он получает от А какие-то ответы. Затем он спрашивает у А: ты уже успел соврать?

Если А на этот вопрос отвечает "нет", это значит, что он действительно ещё не успел соврать (т.к. если уже успел соврать, то и этот ответ неверен, и вместе получается два неверных ответа). Но это значит, что Б уже знает три правильных цифры, и у него есть ещё 3 вопроса. Он задаёт три раза один и тот же вопрос: о четвёртой цифре. По большинству ответов заключает, какова четвёртая цифра, и знает всё число.

Если А на четвёрый вопрос отвечает "да", этот ответ либо верный, либо неверный; но в любом случае выходит, что за первые четыре ответа А уже успел солгать. Теперь Б использует два вопроса для того, чтобы узнать, в каком именно из первых четырёх ответов солгал А (т.е. он использует два вопроса для того, чтобы выбрать одну возможность из четырёх, и он уже знает, что А не может больше лгать, так что это легко; например, первый вопрос: "ты солгал в одном из первых двух ответов?" итп.). Из этого он заключает, какой из первых трёх разрядов он знает неправильно (или все правильно, если А солгал в ответ на 4-й вопрос). И оставшимся 7-м вопросом Б определяет последний разряд, т.к. А опять-таки не может уже лгать.

Да, и ещё, это решение выглядит особенно красивым благодаря своему четвёртому "мета"-вопросу... конечно, эта эффектность несколько тускнеет, если задуматься и понять, что вместо "врал ли ты уже" можно просто спросить о сумме первых трёх разрядов по модулю 2 и заключить то же самое :)
Но всё равно мило, по-моему.
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 42 comments