задачка

[avva]

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

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

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

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


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

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

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

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

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

Comments

[bety.livejournal.com]

1. В первой половине?
2. Среди той части(8 чисел) в которой это на самом деле(т.е правильного ответа на первый вопрос),находится ли загаданное число в первой половине(среди первых 4 чисел)?
3,4 - аналогично делим пополам еше дважды.

Если записать полученные ответы по порядку как 0 или 1 (0 да,1 - нет) справа налево , получим число от 0 до 15 в двоичной записи.

Остается 3 вопроса и 5 вариантов: либо получившееся число(назовем его y),либо число с "переворотом" одного бита относительно y (z1,z2,z3,z4).

5. y или z1 ?
теперь ответ обязан быть правдой (иначе это уже второе вранье)
если ответ да - нет проблем угадать за 2 вопроса (например дважды спросить, первый ли это)
если нет - остаются 3 возможности и 2 вопроса, но тут мы уже знаем, что вранье использовано.

sorry

[bety.livejournal.com]

да, и конечно не забывать закрывать <.i> tag-и в следующий раз :)

[avva.livejournal.com]

y или z1 ?
теперь ответ обязан быть правдой (иначе это уже второе вранье)

Вот этой части и дальше я не понял, но, кажется, это не может сработать ;)

[bety.livejournal.com]

имелся ввиду вопрос 5.Является ли загаданное число одним из этих двух(y,z1).
Представим себе, что ответ "да" и это ложь.То есть в часности это не у. Но тогда один из ответов на вопросы 1-4 (которые в совокупности утверждают, что это у) был ложен - и это противоречит тому, что допустима лишь одна ложь. Значит ответ да - правдив и дальше просто.

Относительно ответа "нет",я похоже была слишком оптимистична,но кажется, это можно исправить :) Если "нет" - ложь, значит на самом деле это число у (z1 не может быть). А если "нет" это правда, то один из ответов на в.1-4 не верен. В любом случае,ложь уже была израсходована и загаданное число не z1.
Остается 4 возможности и 2 вопроса.

Но это решение уже ,конечно, слегка громоздко.
(P.S извиняюсь за сумбурность, но я старалась :) )

[avva.livejournal.com]

Мне почему-то не казалось, что так получится, но на самом деле, действительно всё сходится ;)
Поздравляю!