![[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 и заключить то же самое :)
Но всё равно мило, по-моему.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2003-01-29 04:11 am (UTC)Re:
Date: 2003-01-29 04:19 am (UTC)no subject
Date: 2003-01-29 04:26 am (UTC)Re:
Date: 2003-01-29 04:29 am (UTC)no subject
Date: 2003-01-29 05:17 am (UTC)Соответственно, 1 - 4й биты числа
Вопрос 5
Контрольная сумма всех битов (по модулю 2) - если совпала - мы узнали число
Вопрос 6
Контрольная сумма 1-го и 2-го бита - если совпала, то
Вопрос 7
Контрольный 3-й (ли 4-й) бит
если нет
Вопрос 7
Контрольный 1-й (ли 2-й) бит
С кодами как-то никак пока :)
Re:
Date: 2003-01-29 05:34 am (UTC)В результате это не работает, т.к. не учитывает ту возможность, что ответ на пятый вопрос не совпадает именно потому, что на него лгут.
аналогично
Date: 2003-01-29 04:44 am (UTC)анекдот про чайник и математика помните? :)
no subject
Date: 2003-01-29 04:32 am (UTC)Re:
Date: 2003-01-29 04:32 am (UTC)Шаг 1
Date: 2003-01-29 04:32 am (UTC)За 4 вопроса узнаём число.
Осталось проверить истинность предыдущих 4-х ответов 3-мя оставшимися вопросами
Сейчас додумаю
Re: Шаг 1
Date: 2003-01-29 04:45 am (UTC)Re: Фи, как просто
1. Первый бит - 1? По резултатам записываем, что он будет A (0 или 1 - в зависимости от ответа)
2. Второй бит - 1? Записываем - B.
3. Первые два бита - AB? Если "нет", то право на ошибку уже использовано, а у нас осталось 4 вопроса. Тривиальщина. Если "да", то чуть сложнее.
4. Третий бит - 1? Записываем - C.
5. Первые три бита - ABC? Если "нет", то неверно отвечен вопрос 4, результат на него D и у нас два вопроса на 4-й бит. Если "да", то мы просто дважды спрашиваем про 4-й бит.
Простая задачка :(
Re: Сорри за сумбурное изложение
Date: 2003-01-29 04:41 am (UTC)Re: Фи, как просто
Re: Да, извиняюсь
Date: 2003-01-29 05:06 am (UTC)Ошибку понял.
Re: Шаг 1
Date: 2003-01-29 04:42 am (UTC)Re: Не совсем
одного не хватает
Re: Не совсем
Date: 2003-01-29 05:04 am (UTC)Для её исправления понадобится дополнительный вопрос.
Правильное решение - исправляющий одиночную ошибку (7,4)-код Хемминга, описанный ниже
По простому - спрашиваем про все биты, потом три раза - про контрольные суммы (по модулю два) из трёх битов каждая, выкидывая каждый раз другой бит.
Хемминг исправляет одиночную ошибку и позволяет обнаружить двойную.
Re: Не совсем
Date: 2003-01-29 05:32 am (UTC)Я знаю другую формулировку такого же в принципе решения; почти верную версию её только что
objasnyaju svyza'
Date: 2003-01-29 04:49 am (UTC)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 :)))
Date: 2003-01-29 04:58 am (UTC)Re: objasnyaju svyza'
И всё же существует куда более простое (не требующее теории корректирующих кодов совершенно) и красивое алгоритмическое решение, хотелось бы, чтобы его нашли.
Re: objasnyaju svyza'
Re: objasnyaju svyza'
Date: 2003-01-29 05:31 am (UTC)no subject
Date: 2003-01-29 05:07 am (UTC)Тогда первые 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 узнаю и С.
no subject
Re:
Date: 2003-01-29 05:33 am (UTC)?
Date: 2003-01-29 05:25 am (UTC)4 спрашиваем, была ли уже ошибка
5 спрашиваем четвёртый бит
если была ошибка в 4, проверяем (6,7) первые два бита, что даёт нам точное место ошибки
если не было, спрашиваем (6) четвёртый бит и (7) проверяем его
Re: ?
Date: 2003-01-29 05:31 am (UTC):)
!
Date: 2003-01-29 05:35 am (UTC)Re: !
Date: 2003-01-29 05:42 am (UTC)no subject
Date: 2003-01-29 05:49 am (UTC)no subject
Date: 2003-01-29 05:27 am (UTC)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
Date: 2003-01-29 05:38 am (UTC)no subject
Date: 2003-01-29 05:53 am (UTC)теперь ответ обязан быть правдой (иначе это уже второе вранье)
Вот этой части и дальше я не понял, но, кажется, это не может сработать ;)
no subject
Date: 2003-01-29 06:42 am (UTC)Представим себе, что ответ "да" и это ложь.То есть в часности это не у. Но тогда один из ответов на вопросы 1-4 (которые в совокупности утверждают, что это у) был ложен - и это противоречит тому, что допустима лишь одна ложь. Значит ответ да - правдив и дальше просто.
Относительно ответа "нет",я похоже была слишком оптимистична,но кажется, это можно исправить :) Если "нет" - ложь, значит на самом деле это число у (z1 не может быть). А если "нет" это правда, то один из ответов на в.1-4 не верен. В любом случае,ложь уже была израсходована и загаданное число не z1.
Остается 4 возможности и 2 вопроса.
Но это решение уже ,конечно, слегка громоздко.
(P.S извиняюсь за сумбурность, но я старалась :) )
no subject
Поздравляю!
no subject
Date: 2003-01-29 05:54 am (UTC)no subject
no subject
no subject
Date: 2003-01-29 07:12 am (UTC)no subject
Date: 2003-01-29 07:18 am (UTC)no subject
Date: 2003-01-30 04:08 am (UTC)Или там, "старший бит равен 0" - "меньше 8".
Для остальных - наборы чисел ("второй с младшего конца бит равен 0" == "это 0, 1, 4, 5, 8, 9, 12 или 13").
С другой стороны, конкретные биты не так важны - будут работать любые 4 различные разбиения множества чисел от 0 до 15 пополам.
no subject
Date: 2003-01-29 01:04 pm (UTC)П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врали.
no subject
Date: 2012-04-14 08:52 pm (UTC)Что придумалось. Мне изначально казалось, что здесь должна быть геометрия; и она таки нашлась.
Итак. Берём проективную плоскость над полем F2. В ней, как известно, семь точек и семь прямых. Рассмотрим следующие множества точек:
1) Пустое (одно, мощности 0)
2) Прямые (семь, мощности 3)
3) Дополнения прямых (семь, мощности 4)
4) Вся плоскость (одна, мощности 7)
Всего этих множеств 16 штук. Пронумеруем их числами от 0 до 15. Теперь можно считать, что вы задумали одно из этих множеств, и мне надо угадать, какое именно.
Про каждую из семи точек я спрашиваю вас, принадлежит ли она задуманному вами множеству. В результате я получаю некоторое множество точек ("заявленное"), и мне известно, что оно отличается от задуманного не более чем на одну точку.
Далее смотрим на мощность заявленного множества
1) Заявленное множество пусто или содержит одну точку. Тогда задуманное множество пусто.
2) Заявленное множество содержит две точки. Тогда задуманное множество — прямая, через них проходящая; то, что третья точка на этой прямой задуманному множеству не принадлежит — враньё.
3) Заявленное множество содержит три точки. Тут варианты:
3.1) Заявленное множество содержит три точки, причём лежащие на одной прямой. Тогда задуманное множество — эта прямая, и вранья не было.
3.2) Заявленное множество содержит три точки, и они не лежат на одной прямой. Через каждую из этих точек проходят три прямых — всего девять, но те прямые, которые проходят через две из этих точек сразу, мы посчитали дважды; их всего три (столько же, сколько пар из этих трёх точек), и получается, что в нашей плоскости 9-3=6 прямых, пересекающих заявленное множество. Значит, есть ровно одна прямая, не пересекающаяся с заявленным множеством; её дополнение — и есть задуманное множество.
4) Заявленное множество содержит четыре или более точек. Тогда его дополнение содержит не более трёх точек; один из вариантов 1-3 даёт нам дополнение задуманного множества.