логическая задачка
Sep. 2nd, 2001 03:00 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaВ детстве, помню, буквально глотал всякие сборники логических задачек. Все, наверное, помнят такой целый класс задач о лжецах и правдивых людях: например, путник, встречая на перекрёстке человека, который либо всегда врёт, либо всегда говорит правду, должен выяснить одним вопросом, по какой дороге ему надо идти дальше.
А вот пару дней назад случайно наткнулся на задачку с похожим условием, но более тяжёлую, чем обычно для таких задачек. Мне её понравилось решать. Если кому интересно - попробуйте свои силы:
На некотором острове живут: люди, которые всегда говорят правду, люди, которые всегда лгут, и люди, которые просто отвечают наугад, случайным образом. Причём они всегда ходят по три человека, так, что в каждой тройке есть по одному представителю каждого типа. Путник встретил такую тройку. Может ли он определить, кто есть кто, задав всего три двоичных вопроса (т.е. вопроса, на каждый из которых существуют всего два ответа)? Каждый вопрос можно задавать только одному человеку. Жители острова знают друг о друге и о себе самих, кто есть кто.
А вот пару дней назад случайно наткнулся на задачку с похожим условием, но более тяжёлую, чем обычно для таких задачек. Мне её понравилось решать. Если кому интересно - попробуйте свои силы:
На некотором острове живут: люди, которые всегда говорят правду, люди, которые всегда лгут, и люди, которые просто отвечают наугад, случайным образом. Причём они всегда ходят по три человека, так, что в каждой тройке есть по одному представителю каждого типа. Путник встретил такую тройку. Может ли он определить, кто есть кто, задав всего три двоичных вопроса (т.е. вопроса, на каждый из которых существуют всего два ответа)? Каждый вопрос можно задавать только одному человеку. Жители острова знают друг о друге и о себе самих, кто есть кто.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Íàçîâåì ïàðó õèìè÷åñêîé åñëè îáà íàçîâóò íàïàðíèêà õèìèêîì. Õèìè÷åñêàÿ ïàðà ìîæåò ñîñòîÿòü ëèáî èç äâóõ õèìèêîâ, ëèáî èç äâóõ àëõèìèêîâ. Òàê êàê õèìèêîâ áîëüøå, òî õèìïàð èç äâóõ õèìèêîâ áîëüøå.
Ïóñòü Ì ÷èñëî õèìïàð. Âîçüìåì â êàæäîé õèìïàðå ïî ïðåäñòàâèòåëþ, ïîëó÷èì ìíîæåñòâî èç Ì ó÷àñòíèêîâ, â êîòîðîì õèìèêîâ áîëüøå. Ïî èíäóêöèè, ìû ìîæåì ðàñêîëîòü åãî çà 2Ì2 âîïðîñà. Òåïåðü ìû çíàåì âñå î ïîïàâøèõ â õèìïàðû. Îá îñòàâøèõñÿ N2Ì ìîæíî ñïðîñèòü ó ëþáîãî èçâåñòíîãî õèìèêà, åùå N2Ì âîïðîñîâ. Èòîãî
N+2Ì2+N2Ì = 2N2
âîïðîñà.
Åñëè N íå÷åòíî, òî äåëî ÷óòü ñëîæíåå. ×òîáû ðàçäåëèòü íà ïàðû, íàäî îäíîãî âûáðîñèòü.  èòîãè, ñðåäè Ì õèìïàð ÷èñëî ïàð õèìèêîâ è ïàð àëõèìèêîâ ìîæåò ñðàâíÿòüñÿ. Íî õèìèêîâ íå ìîæåò ñòàòü ìåíüøå.
Åñëè Ì íå÷åòíî, òî õèìèêîâ ñðåäè Ì ïðåäñòàâèòåëåé áîëüøå, è ïðèìåíÿåì ïðåäûäóùåå ðàññóæäåíèå. Åñëè Ì ÷åòíî, òî äåëèì èõ íà ïàðû îïÿòü, è ò.ä. Ýòîò ïðîöåññ ïðîäîëæàåì äî îäíîé èç ñëåäóþùèõ ñèòóàöèé:
(à) íà êàêîìòî øàãå ÷èñëî õèìïàð îêàçàëîñü íå÷åòíûì. Òîãäà èíäóêöèÿ, ñ ïîäñ÷åòîì ÷èñëà âîïðîñîâ êàê â ïåðâîì ñëó÷àå, íî ÷óòü áîëåå ñëîæíûì.
(á) íà êàêîìòî øàãå íå áûëî õèìè÷åñêèõ ïàð âîîáùå. Ýòî çíà÷èò, ÷òî âûáðîøåííûé ÿâëÿåòñÿ õèìèêîì. Èñïîëüçóÿ åãî, ëåãêî âñåõ âû÷èñëèòü. Îïÿòü, íàäî ÷óòü ïîâîçèòüñÿ ñ ïîäñ÷åòîì ÷èñëà âîïðîñîâ.
Ïðèâåò,
Ôðàíöóçèê.