задачка

[avva]

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

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

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

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


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

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

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

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

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

Comments

[hotgiraffe.livejournal.com]

Коды, исправляющие одиночную ошибку ? ;)

Re:

[avva.livejournal.com]

Э... наверное, можно перевести оттуда сюда, да. Но слишком муторно. Легче сразу найти алгоритмическое решение, мне кажется.

[manco.livejournal.com]

Ага, первое что пришло в голову.

Re:

[avva.livejournal.com]

Ну переведите тогда.

[krace.livejournal.com]

дихотомия и жёстко огворенные в вопросах границы отрезков

Шаг 1

[lvalien.livejournal.com]

В двоичной форме - 4 знакоместа
За 4 вопроса узнаём число.
Осталось проверить истинность предыдущих 4-х ответов 3-мя оставшимися вопросами
Сейчас додумаю

Re:

[avva.livejournal.com]

Вперёд ;)

Re: Фи, как просто

[lvalien.livejournal.com]

От 0 до 15 - это от 0000 до 1111.

1. Первый бит - 1? По резултатам записываем, что он будет A (0 или 1 - в зависимости от ответа)
2. Второй бит - 1? Записываем - B.
3. Первые два бита - AB? Если "нет", то право на ошибку уже использовано, а у нас осталось 4 вопроса. Тривиальщина. Если "да", то чуть сложнее.
4. Третий бит - 1? Записываем - C.
5. Первые три бита - ABC? Если "нет", то неверно отвечен вопрос 4, результат на него D и у нас два вопроса на 4-й бит. Если "да", то мы просто дважды спрашиваем про 4-й бит.

Простая задачка :(

Re: Сорри за сумбурное изложение

[lvalien.livejournal.com]

Если надо, я могу изобразить это алголоподобно.

Re: Шаг 1

[larshin.livejournal.com]

Вот оно самое, только каждый вопрос задаётся два раза подряд - где-то так.

аналогично

[rsh.livejournal.com]

вот ведь, а?!
анекдот про чайник и математика помните? :)

Re: Не совсем

[lvalien.livejournal.com]

Два раза подряд - 8 вопросов
одного не хватает

Re: Фи, как просто

[avva.livejournal.com]

Нет, это неверное решение. Подумайте ещё немного, хотя бы над тем, почему оно неверное.

Re: Шаг 1

[avva.livejournal.com]

Ну-ну :)

objasnyaju svyza'

[mi-b.livejournal.com]

Est' takaja vesh', kak [7,4,3]-kod Hemminga: nabor iz 2^4=16 dvoichnyh strok (kodovyh slov) dliny 7 kazhdaja, pri etom kazhdaja
stroka koda otlichaetsya ot drugoj ne menee, chem na 3 simvola. V parametrizacii, privedennoj po ssylke, bity 3,4,5,7 - informacionnye, sochetanija ostal'nyh proverochnyh 3 bitov dajut pozicuju oshibki.

Kak etot kod ispol'zovat':
- kazhdyj informacionnyj bit - eto vopros ob ostatke ot delenija nashengo chisla na 2^k, k=0,1,2,3. Kazhdyj proverochnyj bit - linejnaja kombinacija mod 2 nekotoryh informacionnyh bitov - tozhe legko prevrashaetsay v vopros. Kazhdomu polnostju pravdivomu naboru otvetov sootvetstvuet kodovoe slovo. Esli my izmenim odin bit v kodovom slove, my poluchim stroku, kotoraja otlichaetsya ot lubogo drugog kodovogo slova ne menee, chem v 2 pozicijah i smozhem vosstanovit' kodovoe slovo (mozhno i pereborom, no na samom dele vosstanovlenije eto linejnaja proekcija mod 2).

Great minds think alike :)))

[khatul.livejournal.com]

Вот и моё решение, только у mi_b очень хорошо сформулировано, я бы так не смог.

Re: Не совсем

[hotgiraffe.livejournal.com]

И, кстати, задавая все вопросы по два раза, вы лишь обнаружите ошибку ("враньё").
Для её исправления понадобится дополнительный вопрос.
Правильное решение - исправляющий одиночную ошибку (7,4)-код Хемминга, описанный ниже mi_b.

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

Re: objasnyaju svyza'

[avva.livejournal.com]

Большое спасибо за подробное объяснение. Да, это решает задачу.

И всё же существует куда более простое (не требующее теории корректирующих кодов совершенно) и красивое алгоритмическое решение, хотелось бы, чтобы его нашли.

Re: Да, извиняюсь

[lvalien.livejournal.com]

Да, согласен.
Ошибку понял.

[denspb.livejournal.com]

пусть вопросы A, B, C, D -- вопросы, "выделяющие" соответсвенно 0..3 биты.
Тогда первые 4 вопроса:
z1 = A xor B
z2 = C xor D
z3 = D xor A
z4 = B xor C
после этого есть два варианта:
z1 xor z2 = z3 xor z4, или нет
Если да -> задаю 3 раза вопрос A, узнаю A, остюда получаю все остальные.
Если нет -> ложь уже была-> задаю вопрос A xor B xor C xor D, узнаю, какая из первых пар была ложной. Пусть z1 и z2 -- истинные. Тогда задав вопрос про A узнаю и про B, а задав вопрос про D узнаю и С.

[manco.livejournal.com]

Вопросы 1) - 4)
Соответственно, 1 - 4й биты числа
Вопрос 5
Контрольная сумма всех битов (по модулю 2) - если совпала - мы узнали число
Вопрос 6
Контрольная сумма 1-го и 2-го бита - если совпала, то
Вопрос 7
Контрольный 3-й (ли 4-й) бит
если нет
Вопрос 7
Контрольный 1-й (ли 2-й) бит

С кодами как-то никак пока :)

Re: objasnyaju svyza'

[mi-b.livejournal.com]

vy luchshe napishite prostoe reshenije, kogda chislo ot 1 do 2^7 i navrat' mozhno 4 raza ;) (otvet: 23)

?

[anton.livejournal.com]

1,2,3 Спрашиваем первые три бита
4 спрашиваем, была ли уже ошибка
5 спрашиваем четвёртый бит

если была ошибка в 4, проверяем (6,7) первые два бита, что даёт нам точное место ошибки

если не было, спрашиваем (6) четвёртый бит и (7) проверяем его

[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 вопроса, но тут мы уже знаем, что вранье использовано.

Re: objasnyaju svyza'

[avva.livejournal.com]

Ну уж нет ;)

Re: ?

[avva.livejournal.com]

Почти верно.

:)

Re: Не совсем

[avva.livejournal.com]

Вот "по простому" - это уже хорошо. И верно, да ;)
Я знаю другую формулировку такого же в принципе решения; почти верную версию её только что antonme в комменте написал. Сейчас сделаю апдейт к записи.

Re:

[avva.livejournal.com]

Проблема в том, что в варианте для домохозяек не хватит 7 вопросов.

Re:

[avva.livejournal.com]

Пятый вопрос слишком расточительный ;)
В результате это не работает, т.к. не учитывает ту возможность, что ответ на пятый вопрос не совпадает именно потому, что на него лгут.

!

[anton.livejournal.com]

Почти - из-за четвёртого вопроса?

sorry

[bety.livejournal.com]

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

Re: !

[avva.livejournal.com]

Из-за одной из стратегий поведения после него.

[anton.livejournal.com]

А-а. Я понял, точно.

[avva.livejournal.com]

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

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

[larshin.livejournal.com]

Вариант социлогический: за первых три вопроса заставляем человека соврать - немного зная пациента можно придумать такой вопрос или последовательность вопросов, на которые ему будет неловко ответить честно и он неизбежно соврёт, ну а дальше, сбросив гору с плеч, за 4 хода в дамки.

[lezze.livejournal.com]

вообще не очень это честно :) Надо было предупреждать, что "ВЫ" (отвечающий) знаете двоичную систему, либо сразу указать что число загадано в двоичной форме.

[avva.livejournal.com]

Ой. Просто замечательно!

[bety.livejournal.com]

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

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

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

[anton.livejournal.com]

Это не принципиально. Можно сформулировать вопросы для незнающего двоичной сс, это не сложно.

[lezze.livejournal.com]

хм.. как? ладно, видимо, я слишком бегло пробежался по триду и не вник в решенив.

[lom.livejournal.com]

Нe читая ни oднoгo кoммeнта, я прeдлагаю такoй путь.
Пoскoльку начальных чисeл всeгo 16, тo бeз вoзмoжнoсти лжи пoтрeбoвалoсь бы 4 вoпрoса ( бифуркация - дeлeниe на равныe группы )
для oкoнчатeльнoгo oтвeта.

Слeдoватeльнo, задавая вoпрoсы с "услoвнoй" бифуркациeй ( oбщий вoпрoс прилагаeтся нижe ***) , я пoслe 4-гo пoлучу слeдующиe варианты, мeжду кoтoрыми мнe eщe прeдстoит выбирать:

_________________________________
***
Слeдуeщee утвeрждeниe правдивo - да или нeт ? :

( <бифуркативнoe услoвиe ( типа: загаданнoe числo нe бoльшe 7 ) > плюс дoбавoчнoe услoвиe (< И всe прeдыдущиe oтвeты были правдивы ) )
ИЛИ ( < втoрoe бифуркативнoe утвeрждeниe И oтвeт #1 был лoжью > )
ИЛИ .....
и так далee ...

___________________________

1. Мнe ни разу нe сoврали - и тoгда загаданoe числo - такoe-тo.
2. Мнe сoврали в пeрвoм oтвeтe - и числo такoe-тo

5. Мнe сoврали в пoслeднeм oтвeтe - и числo такoe-тo

Задача рeзкo упрoстилась. Нe мeняя инвариантнoсти прoнумeруeм oставшиeся числа-кандидаты 1, 2, 3, 4, 5 - гдe числo сooтвeтствуeт
нoмeру oтвeта с лoжью, и 5 - oтсутвию лжи в пeрвых 4 oтвeтах.

Дальшe дeйствуeм, напримeр, так ( навeрнoe, eсть и другиe пути ):
5 вoпрoс) 1 или 2 или 5 ?
6 вoпрoс) 3 или 4 или 5 ?

Eсли имeeм да, да , тo либo в пoслeдних oтвeтах была лoжь ( а значит ee нe былo в пeрвых 4-х вoпрoсах ), либo oтвeт 5, чтo oднo и тo
жe - и имeeм oтвeт 5
Eсли oтвeт "нeт-нeт", тo хoть oдин из них - лoжь - и тoгда oтвeт oпять-таки 5.
В случаe "нeт-да" или "да-нeт" нам oстаeтся oтвeтить на пoслeдний вoпрoс.
Прeдпoлoжим, oдин из oтвeтoв был лoжью. Нo тoгда лжи нe былo в пeрвых 4-х oтвeтах, а слeдoватeльнo загаданo былo имeннo 5,
а слeдoватeльнo oба oтвeта oбязаны были быть правдoй. Слeдoватeльнo, прeдпoлoжeниe лoжнo.
Итак, нам oба раз сказали правду в вариантe "да-нeт" или "нeт-да". Этo исключаeт 5 ( oдин раз на 5 правдивo сказали нeт ).
Oсталoсь задать пoслeдний вoпрoс.
7 вoпрoс) 1 ? ( для варианта да-нeт, eсли в прeдыдущих двух былo нeт-да, тo: 3 ? )
Сoврать нам нe мoгут - ибo oдин раз ужe сoврали.

[avva.livejournal.com]

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

[avva.livejournal.com]

Да, и так тоже работает. Спасибо! красивое решение.

[hotgiraffe.livejournal.com]

Ну, скажем, "младший бит равен 0" - это то же самое, что "делицца на 2".
Или там, "старший бит равен 0" - "меньше 8".
Для остальных - наборы чисел ("второй с младшего конца бит равен 0" == "это 0, 1, 4, 5, 8, 9, 12 или 13").

С другой стороны, конкретные биты не так важны - будут работать любые 4 различные разбиения множества чисел от 0 до 15 пополам.

[migmit.livejournal.com]

Ух, далеко меня занесло. Надеюсь, ответы вам на почту ходят.

Что придумалось. Мне изначально казалось, что здесь должна быть геометрия; и она таки нашлась.

Итак. Берём проективную плоскость над полем F₂. В ней, как известно, семь точек и семь прямых. Рассмотрим следующие множества точек:

1) Пустое (одно, мощности 0)
2) Прямые (семь, мощности 3)
3) Дополнения прямых (семь, мощности 4)
4) Вся плоскость (одна, мощности 7)

Всего этих множеств 16 штук. Пронумеруем их числами от 0 до 15. Теперь можно считать, что вы задумали одно из этих множеств, и мне надо угадать, какое именно.

Про каждую из семи точек я спрашиваю вас, принадлежит ли она задуманному вами множеству. В результате я получаю некоторое множество точек ("заявленное"), и мне известно, что оно отличается от задуманного не более чем на одну точку.

Далее смотрим на мощность заявленного множества

1) Заявленное множество пусто или содержит одну точку. Тогда задуманное множество пусто.
2) Заявленное множество содержит две точки. Тогда задуманное множество — прямая, через них проходящая; то, что третья точка на этой прямой задуманному множеству не принадлежит — враньё.
3) Заявленное множество содержит три точки. Тут варианты:
3.1) Заявленное множество содержит три точки, причём лежащие на одной прямой. Тогда задуманное множество — эта прямая, и вранья не было.
3.2) Заявленное множество содержит три точки, и они не лежат на одной прямой. Через каждую из этих точек проходят три прямых — всего девять, но те прямые, которые проходят через две из этих точек сразу, мы посчитали дважды; их всего три (столько же, сколько пар из этих трёх точек), и получается, что в нашей плоскости 9-3=6 прямых, пересекающих заявленное множество. Значит, есть ровно одна прямая, не пересекающаяся с заявленным множеством; её дополнение — и есть задуманное множество.
4) Заявленное множество содержит четыре или более точек. Тогда его дополнение содержит не более трёх точек; один из вариантов 1-3 даёт нам дополнение задуманного множества.