задачка про рыцарей и купцов
Jun. 19th, 2020 06:05 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaНелегкая и интересная задачка, которая мне не попадалась раньше (спасибо ![[livejournal.com profile]](https://www.dreamwidth.org/img/external/lj-userinfo.gif)
urod за то, что написал о ней).
В городе живут n рыцарей и купцов (n>1), каждый житель либо рыцарь, либо купец, и все друг про друга знают, кто они, рыцари или купцы. Рыцари всегда говорят правду, купцы могут и лгать. Рыцарей больше, чем купцов. Можно задавать любым горожанам вопросы типа "кем является такой-то" (в частности, можно спросить человека, кем является он сам). Другие вопросы задавать нельзя (например, нельзя спросить, верно ли, что у A и B одна и та же профессия, или что-то про количество рыцарей). Доказать, что можно узнать профессии всех горожан за
(a) 2n-2 вопроса
(b) 2n-3 вопроса
У этой задачи известно оптимальное решение, оно еще лучше, чем эти два задания (меньше вопросов), если хотите, попробуйте найти его тоже. Я запощу сюда послезавтра все решения и ссылки; если вы знаете или нашли ссылку на решение задачи, не кидайте ее до этого, пожалуйста. Комментарии скрывать не буду, там могут появляться спойлеры решений от других участников.
urod за то, что написал о ней). В городе живут n рыцарей и купцов (n>1), каждый житель либо рыцарь, либо купец, и все друг про друга знают, кто они, рыцари или купцы. Рыцари всегда говорят правду, купцы могут и лгать. Рыцарей больше, чем купцов. Можно задавать любым горожанам вопросы типа "кем является такой-то" (в частности, можно спросить человека, кем является он сам). Другие вопросы задавать нельзя (например, нельзя спросить, верно ли, что у A и B одна и та же профессия, или что-то про количество рыцарей). Доказать, что можно узнать профессии всех горожан за
(a) 2n-2 вопроса
(b) 2n-3 вопроса
У этой задачи известно оптимальное решение, оно еще лучше, чем эти два задания (меньше вопросов), если хотите, попробуйте найти его тоже. Я запощу сюда послезавтра все решения и ссылки; если вы знаете или нашли ссылку на решение задачи, не кидайте ее до этого, пожалуйста. Комментарии скрывать не буду, там могут появляться спойлеры решений от других участников.
