![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaВот хорошая задачка, менее тривиальная, чем на первый взгляд кажется.
Я загадываю число от 0 до 15 (включительно). Вам разрешается задать 7 вопросов, на каждый из которых возможные ответы - "да" или "нет". Я отвечаю на ваши вопросы, и мне разрешается соврать один раз (я могу и вообще не врать и ответить правильно на все вопросы, а могу на один какой-нибудь ответить неправильно).
Задание: найти стратегию, всегда позволяющую вам узнать, какое число я загадал.
Update: В комментах есть уже несколько верных доказательств, разной степени сложности. Я приведу здесь другое, особенно простое, которое в точности ещё никто не повторил, хотя подошли очень близко. За элжекатом.
Итак, A загадал число от 0 до 15, а Б его отгадывает. В двоичной записи это число записывается в четыре двоичных цифры (например, 7 это 0111 итп.).
Первые три вопроса Б - про первые три двоичных разряда числа. Он получает от А какие-то ответы. Затем он спрашивает у А: ты уже успел соврать?
Если А на этот вопрос отвечает "нет", это значит, что он действительно ещё не успел соврать (т.к. если уже успел соврать, то и этот ответ неверен, и вместе получается два неверных ответа). Но это значит, что Б уже знает три правильных цифры, и у него есть ещё 3 вопроса. Он задаёт три раза один и тот же вопрос: о четвёртой цифре. По большинству ответов заключает, какова четвёртая цифра, и знает всё число.
Если А на четвёрый вопрос отвечает "да", этот ответ либо верный, либо неверный; но в любом случае выходит, что за первые четыре ответа А уже успел солгать. Теперь Б использует два вопроса для того, чтобы узнать, в каком именно из первых четырёх ответов солгал А (т.е. он использует два вопроса для того, чтобы выбрать одну возможность из четырёх, и он уже знает, что А не может больше лгать, так что это легко; например, первый вопрос: "ты солгал в одном из первых двух ответов?" итп.). Из этого он заключает, какой из первых трёх разрядов он знает неправильно (или все правильно, если А солгал в ответ на 4-й вопрос). И оставшимся 7-м вопросом Б определяет последний разряд, т.к. А опять-таки не может уже лгать.
Да, и ещё, это решение выглядит особенно красивым благодаря своему четвёртому "мета"-вопросу... конечно, эта эффектность несколько тускнеет, если задуматься и понять, что вместо "врал ли ты уже" можно просто спросить о сумме первых трёх разрядов по модулю 2 и заключить то же самое :)
Но всё равно мило, по-моему.
Я загадываю число от 0 до 15 (включительно). Вам разрешается задать 7 вопросов, на каждый из которых возможные ответы - "да" или "нет". Я отвечаю на ваши вопросы, и мне разрешается соврать один раз (я могу и вообще не врать и ответить правильно на все вопросы, а могу на один какой-нибудь ответить неправильно).
Задание: найти стратегию, всегда позволяющую вам узнать, какое число я загадал.
Update: В комментах есть уже несколько верных доказательств, разной степени сложности. Я приведу здесь другое, особенно простое, которое в точности ещё никто не повторил, хотя подошли очень близко. За элжекатом.
Итак, A загадал число от 0 до 15, а Б его отгадывает. В двоичной записи это число записывается в четыре двоичных цифры (например, 7 это 0111 итп.).
Первые три вопроса Б - про первые три двоичных разряда числа. Он получает от А какие-то ответы. Затем он спрашивает у А: ты уже успел соврать?
Если А на этот вопрос отвечает "нет", это значит, что он действительно ещё не успел соврать (т.к. если уже успел соврать, то и этот ответ неверен, и вместе получается два неверных ответа). Но это значит, что Б уже знает три правильных цифры, и у него есть ещё 3 вопроса. Он задаёт три раза один и тот же вопрос: о четвёртой цифре. По большинству ответов заключает, какова четвёртая цифра, и знает всё число.
Если А на четвёрый вопрос отвечает "да", этот ответ либо верный, либо неверный; но в любом случае выходит, что за первые четыре ответа А уже успел солгать. Теперь Б использует два вопроса для того, чтобы узнать, в каком именно из первых четырёх ответов солгал А (т.е. он использует два вопроса для того, чтобы выбрать одну возможность из четырёх, и он уже знает, что А не может больше лгать, так что это легко; например, первый вопрос: "ты солгал в одном из первых двух ответов?" итп.). Из этого он заключает, какой из первых трёх разрядов он знает неправильно (или все правильно, если А солгал в ответ на 4-й вопрос). И оставшимся 7-м вопросом Б определяет последний разряд, т.к. А опять-таки не может уже лгать.
Да, и ещё, это решение выглядит особенно красивым благодаря своему четвёртому "мета"-вопросу... конечно, эта эффектность несколько тускнеет, если задуматься и понять, что вместо "врал ли ты уже" можно просто спросить о сумме первых трёх разрядов по модулю 2 и заключить то же самое :)
Но всё равно мило, по-моему.
