логическая задачка

[avva]

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

А вот пару дней назад случайно наткнулся на задачку с похожим условием, но более тяжёлую, чем обычно для таких задачек. Мне её понравилось решать. Если кому интересно - попробуйте свои силы:

На некотором острове живут: люди, которые всегда говорят правду, люди, которые всегда лгут, и люди, которые просто отвечают наугад, случайным образом. Причём они всегда ходят по три человека, так, что в каждой тройке есть по одному представителю каждого типа. Путник встретил такую тройку. Может ли он определить, кто есть кто, задав всего три двоичных вопроса (т.е. вопроса, на каждый из которых существуют всего два ответа)? Каждый вопрос можно задавать только одному человеку. Жители острова знают друг о друге и о себе самих, кто есть кто.

Comments

Îïÿòü

[french-man.livejournal.com]

ïðîâîöèðóåòå? Íî ÿ Âàì îòîìùó.

 ñâîå âðåìÿ â "Êâàíòå" áûëà ñëåäóþùàÿ âåëèêàÿ çàäà÷à.

N ó÷àñòíèêîâ íåêîãî êîíãðåññà äåëÿòñÿ íà õèìèêîâ è àëõèìèêîâ, ïðè÷åì õèìèêîâ áîëüøå. Õèìèêè âñåãäà ãîâîðÿò ïðàâäó, à àëõèìèêè èíîãäà ïðàâäèâû, à èíîãäà ëãóò. Îïðåäåëèòü, êòî åñòü êòî, çàäàâ 2N–2 âîïðîñà.

ß äî ñèõ ïîð áîëüøå ãîðæóñü ðåøåíèåì ýòîé çàäà÷è, ÷åì ìíîãèìè èç ñâîèõ îðèãèíàëüíûõ ðåçóëüòàòîâ. Ýòî ïðèòîì, ÷òî 2N–2 ìîæíî óëó÷øèòü. Âïîñëåäñòâèè â "Êâàíòå" áûëà ñòàòüÿ, ïîêàçûâàþùàÿ, ÷òî 3N/2 (èëè âðîäå òîãî) äîñòàòî÷íî, à ìåíüøå íåäîñòàòî÷íî.

Re: Îïÿòü

[oxfv.livejournal.com]

Äåéñòâèòåëüíî, ýòà ïîñëîæíåå áóäåò. Àââèíó âðîäå ðåøèë (íå ñêàæó êàê, íî îòâåò - êîíå÷íî æå, òðåõ âîïðîñîâ õâàòèò), à ñ ýòîé òðóäíî...

[french-man.livejournal.com]

Äàòü ïîäñêàçêó?

[oxfv.livejournal.com]

Äàòü, ïîæàëóé. Ñ òðóäîì øåñòåðåíêè øåâåëÿòñÿ, ðàññóæäåíèÿ âñå êàêèå-òî íà ïàëüöàõ, áåñòîëêîâûå.

[french-man.livejournal.com]

Ïóñòü N ÷åòíî. Ðàçîáüåì âñåõ íà ïàðû, è â êàæäîé ïàðå ñïðîñèì ó êàæäîãî î íàïàðíèêå. Âñåãî N âîïðîñîâ.

Íàçîâåì ïàðó õèìè÷åñêîé åñëè îáà íàçîâóò íàïàðíèêà õèìèêîì. Õèìè÷åñêàÿ ïàðà ìîæåò ñîñòîÿòü ëèáî èç äâóõ õèìèêîâ, ëèáî èç äâóõ àëõèìèêîâ. Òàê êàê õèìèêîâ áîëüøå, òî õèìïàð èç äâóõ õèìèêîâ áîëüøå.

Ïóñòü Ì ÷èñëî õèìïàð. Âîçüìåì â êàæäîé õèìïàðå ïî ïðåäñòàâèòåëþ, ïîëó÷èì ìíîæåñòâî èç Ì ó÷àñòíèêîâ, â êîòîðîì õèìèêîâ áîëüøå. Ïî èíäóêöèè, ìû ìîæåì ðàñêîëîòü åãî çà 2̖2 âîïðîñà. Òåïåðü ìû çíàåì âñå î ïîïàâøèõ â õèìïàðû. Îá îñòàâøèõñÿ N–2Ì ìîæíî ñïðîñèòü ó ëþáîãî èçâåñòíîãî õèìèêà, åùå N–2Ì âîïðîñîâ. Èòîãî

N+2̖2+N–2Ì = 2N–2

âîïðîñà.

Åñëè N íå÷åòíî, òî äåëî ÷óòü ñëîæíåå. ×òîáû ðàçäåëèòü íà ïàðû, íàäî îäíîãî âûáðîñèòü.  èòîãè, ñðåäè Ì õèìïàð ÷èñëî ïàð õèìèêîâ è ïàð àëõèìèêîâ ìîæåò ñðàâíÿòüñÿ. Íî õèìèêîâ íå ìîæåò ñòàòü ìåíüøå.

Åñëè Ì íå÷åòíî, òî õèìèêîâ ñðåäè Ì ïðåäñòàâèòåëåé áîëüøå, è ïðèìåíÿåì ïðåäûäóùåå ðàññóæäåíèå. Åñëè Ì ÷åòíî, òî äåëèì èõ íà ïàðû îïÿòü, è ò.ä. Ýòîò ïðîöåññ ïðîäîëæàåì äî îäíîé èç ñëåäóþùèõ ñèòóàöèé:

(à) íà êàêîì–òî øàãå ÷èñëî õèìïàð îêàçàëîñü íå÷åòíûì. Òîãäà èíäóêöèÿ, ñ ïîäñ÷åòîì ÷èñëà âîïðîñîâ êàê â ïåðâîì ñëó÷àå, íî ÷óòü áîëåå ñëîæíûì.

(á) íà êàêîì–òî øàãå íå áûëî õèìè÷åñêèõ ïàð âîîáùå. Ýòî çíà÷èò, ÷òî âûáðîøåííûé ÿâëÿåòñÿ õèìèêîì. Èñïîëüçóÿ åãî, ëåãêî âñåõ âû÷èñëèòü. Îïÿòü, íàäî ÷óòü ïîâîçèòüñÿ ñ ïîäñ÷åòîì ÷èñëà âîïðîñîâ.

Ïðèâåò,

Ôðàíöóçèê.

Re: Îïÿòü

[avva.livejournal.com]

Õììììì.
À âîïðîñû òîëüêî äà-íåò èëè ìîæíî ïîïðîñèòü, íàïðèìåð, ïîêàçàòü íà àëõèìèêà? À ó÷àñòíèêè êîíãðåññà âñå çíàþò, êòî åñòü êòî?

pardon

[french-man.livejournal.com]

ÿ åå íå÷àÿííî ðåøèë. Õîòåë Âàëåðå ÷óòü ïîäñêàçàòü, à âìåñòî ýòîãî íàïèñàë ðåøåíèå. Ïàêîñòü íå ïîëó÷èëàñü. Îòëîæèì íà ïîòîì.

Âîïðîñû äâîè÷íûå. Äîëæíû çíàòü êòî åñòü êòî. Áåç ýòîãî, êàæåòñÿ, äàæå òðîèõ íåëüçÿ âû÷èñëèòü çà êîíå÷íîå ÷èñëî âîïðîñîâ.

Re: pardon

[avva.livejournal.com]

ß åù¸ íå ïðî÷èòàë ðåøåíèå, îòøàòíóëñÿ â óæàñå, êîãäà ïèñüìî îòêðûë. Òàê ÷òî ìîæåò åù¸ ïîäóìàþ, åñëè íåâòåðï¸æ íå ïåðåñèëèò.
Î! Ôðàçîé ïðî êîíå÷íîå ÷èñëî âîïðîñîâ Âû íàïîìíèëè ìíå çàìå÷àòåëüíóþ è ìàëîèçâåñòíóþ çàäà÷êó ïðî ìàòåìàòèêîâ â òþðüìå. Âîò ÿ ñåé÷àñ Âàì è îòîìùó.

À ñàìè

[french-man.livejournal.com]

æèòåëè çíàþò, êòî åñòü êòî?

Re: À ñàìè

[avva.livejournal.com]

Àãà, çíàþò. Èñïðàâèë çàïèñü, ñïàñèáî.

òîãäà ëåãêî

[french-man.livejournal.com]

Íàçîâåì èõ ïðàâäèâûìè, ëæåöàìè è èäèîòàìè.

Âîïðîñ ê 1–ìó: ÷òî îòâåòèò ïðåäñòàâèòåëü òâîåé ãðóïïû íà âîïðîñ, ÿâëÿåòñÿ ëè 2–é èäèîòîì?

Äàëüøå ÿñíî.

Re: òîãäà ëåãêî

[avva.livejournal.com]

Íåÿñíî. Ïîëîæèì, ïåðâûé - èäèîò. Îí îòâå÷àåò äà èëè íåò ñëó÷àéíî íà ýòîò âîïðîñ. Äàëüøå ÷òî?
Âîîáùå íèêàêîé èíôîðìàöèè íå äîáàâèëîñü, ò.ê. è ïðàâäèâûé, è ëæåö òîæå ìîãëè îòâåòèòü è äà, è íåò.

Re: òîãäà ëåãêî

[french-man.livejournal.com]

Åñëè îòâåò "äà", òî ëèáî ïåðâûé èäèîò, ëèáî âòîðîé èäèîò. Òðåòèé â ëþáîì ñëó÷àå íå èäèîò. Åñëè îòâåò "íåò", òî âòîðîé çàâåäîìî íå èäèîò. Òàê èëè èíà÷å, ìû çíàåì ïðî êîãî–òî, ÷òî îí íå èäèîò. Ýòîãî äîñòàòî÷íî, ÷òîáû çàêðûòüñÿ çà äâà âîïðîñà.

Re: òîãäà ëåãêî

[avva.livejournal.com]

Äà, ëîãè÷íî. Íå îñîçíàë ñðàçó ;)
Èçâåñòíîå ìíå ðåøåíèå ðàáîòàåò íà òîì æå ïðèíöèïå, ò.å. ïåðâûì âîïðîñîì âûäåëÿåì êîãî-òî, êòî íå èäèîò, íî íå ïîëüçóåòñÿ òðþêîì êîñâåííîé ññûëêè, ÷òîáû îáúåäèíèòü ëæåöà ñ ïðàâäèâûì. Ïåðâûé âîïðîñ òàêîé: Ïîêàæè ìíå òîãî èç äâóõ äðóãèõ, êòî ñëåäóþùèé ïîñëå òåáÿ ïî "õóæåñòè" (ñ÷èòàÿ, ÷òî ëæåö õóæå ïðàâäèâîãî, à èäèîò õóæå ëæåöà).

Re: òîãäà ëåãêî

[oxfv.livejournal.com]

Åñëè îòâåò "äà", òî òðåòèé-òàêè ìîæåò áûòü èäèîòîì - åñëè ïåðâûé - ëæåö, à âòîðîé - ÷åñòíÿãà-ïàðåíü. Òàê ÷òî - íå ðàáîòàåò.

ß çàîäíî ïîíÿë, ÷òî ìîå ðåøåíèå òîæå ëèïîâîå. Ïîæàëóé, àââèíî ïðàâèëüíîå è åñòü.

Re: òîãäà ëåãêî

[avva.livejournal.com]

Òóò ðàáîòàåò êîñâåííàÿ ññûëêà, îáðàòèòå âíèìàíèå íà òî÷íóþ ôîðìó âîïðîñà. Ëæåö çíàåò, ÷òî ÷åëîâåê åãî òèïà, ò.å. ëæåö, íà òàêîé îòâåò îòâåòèò "äà"; íî îí äîëæåí ñîëãàòü è ïîòîìó îòâå÷àåò "íåò".

Re: òîãäà ëåãêî

[oxfv.livejournal.com]

Øèò, êàêèå õûòðûå!

Òàêèå ìû

[french-man.livejournal.com]

ôðàíöóçèêè!

Íåò, ðàáîòàåò

[french-man.livejournal.com]

Õîòåë ñàì íàïèñàòü, íî Àíàòîëèé óæå îòâåòèë.

[stas]

Ó Ñìàëëèàíà åñòü öèêë êíèæåê, ïîñâÿùåííûõ ýòîìó âîïðîñó. Ó íåãî òàì åñòü ôîðìóëà âîïðîñà, êîòîðûé ïîçâîëÿåò âûÿñíèòü ëþáîé ôàêò ó ëþáîãî èç òàêèõ æèòåëåé. Âîîáùå ó íåãî òàì âåñüìà ñèëüíàÿ òåîðèÿ íà ýòîò ñ÷åò. Æàëêî, ÿ ýòè êíèæêè â Êèåâå îñòàâèë...

ñìàëëèàí

[french-man.livejournal.com]

×èòàë ÿ ýòè êíèæêè. Íóäíûå äî óæàñà. Âàìïèðû âñå êàêèå–òî.

Re: ñìàëëèàí

[stas]

Âàìïèðû òîëüêî â îäíîé. Åùå â îäíîé ïðèíöåññû è òèãðû, â îäíîé âçëîìû ñåéôîâ è åùå â îäíîé ïðî Ãåäåëÿ. Èõ ó ìåíÿ 3 èëè 4 âñåãî áûëî, â êàæäîé íåñêîëüêî ÷àñòåé. Ìíå î÷åíü íðàâèëîñü :)

Re: ñìàëëèàí

[french-man.livejournal.com]

Äåëî âêóñà. Ìíå òîæå äðóã ïîðåêîìåíäîâàë ñ âîñòîðãîì. À ÿ ïðåäïî÷èòàþ íîðìàëüíûé "ñêó÷íûé" ó÷åáíèê ëîãèêè.

[(Anonymous)]

ïîìîãèòå-ñïàñèòå, âñå ðàâíî ñïîðèì è íå ìîæåì ðàçãàäàòü :(((

[avva.livejournal.com]

Ïåðâûé âîïðîñ ÷åëîâåêó íîìåð 1 òàêîé: Ïîêàæè ìíå òîãî èç äâóõ äðóãèõ, êòî ñëåäóþùèé ïîñëå òåáÿ ïî "õóæåñòè" (ñ÷èòàÿ, ÷òî ëæåö õóæå ïðàâäèâîãî, à èäèîò õóæå ëæåöà).

Åñëè ïåðâûé - ïðàâäèâûé, îí ïîêàæåò íà ëæåöà. Åñëè ïåðâûé - ëæåö, îí ïîêàæåò íà ïðàâäèâîãî (ïîòîìó ÷òî ïðàâèëüíûé îòâåò - èäèîò, à îí ëæåö). Åñëè ïåðâûé - èäèîò, îí ïîêàæåò íà êîãî-òî èç äâîèõ îñòàâøèõñÿ.  ëþáîì èç òð¸õ ñëó÷àåâ ÷åëîâåê, íà êîòîðîãî ïîêàçàëè, íå ìîæåò áûòü èäèîòîì.  ýòîì ñîëü ðàçãàäêè.

Âòîðûì âîïðîñîì ìû ñïðàøèâàåì ýòîãî ÷åëîâåêà (íà êîòîðîãî óêàçàëè): "Óìååøü ëè òû ðàçãîâàðèâàòü?". Ïî åãî îòâåòó ìû ïîíèìàåì, ïðàâäèâûé îí èëè ëæåö. Òðåòüèì âîïðîñ åìó æå: "Êòî èç äâîèõ îñòàâøèõñÿ èäèîò?" Ïî åãî îòâåòó, çíàÿ óæå, ïðàâäèâûé îí èëè ëæåö, ìû îïðåäåëÿåì òèï îñòàâøèõñÿ äâóõ ëþäåé.

Thanks for a good puzzle.

[snyders.livejournal.com]

>(ñ÷èòàÿ, ÷òî ëæåö õóæå ïðàâäèâîãî, à èäèîò õóæå ëæåöà).

pravdiviy -- huzhe idiota, t.k. inache nedoopredeleno, a idiotu vse ravno kak otvechat'.

>"Óìååøü ëè òû ðàçãîâàðèâàòü?"

hmm.. smth fishy here (ambiguous question which may have no "Y/N" answer). What if their only knowledge in life is "who is who"?

Re: Thanks for a good puzzle.

[avva.livejournal.com]

hmm.. smth fishy here (ambiguous question which may have no "Y/N" answer). What if their only knowledge in life is "who is who"?

That's an unreasonable restriction. Anyway, in that case ask him "are you an idiot?" (here ambiguous, but only because french_man suggested the ambiguous term "idiot" ;)).