задачка про рыцарей и купцов
Нелегкая и интересная задачка, которая мне не попадалась раньше (спасибо urod за то, что написал о ней).
В городе живут n рыцарей и купцов (n>1), каждый житель либо рыцарь, либо купец, и все друг про друга знают, кто они, рыцари или купцы. Рыцари всегда говорят правду, купцы могут и лгать. Рыцарей больше, чем купцов. Можно задавать любым горожанам вопросы типа "кем является такой-то" (в частности, можно спросить человека, кем является он сам). Другие вопросы задавать нельзя (например, нельзя спросить, верно ли, что у A и B одна и та же профессия, или что-то про количество рыцарей). Доказать, что можно узнать профессии всех горожан за
(a) 2n-2 вопроса
(b) 2n-3 вопроса
У этой задачи известно оптимальное решение, оно еще лучше, чем эти два задания (меньше вопросов), если хотите, попробуйте найти его тоже. Я запощу сюда послезавтра все решения и ссылки; если вы знаете или нашли ссылку на решение задачи, не кидайте ее до этого, пожалуйста. Комментарии скрывать не буду, там могут появляться спойлеры решений от других участников.
В городе живут n рыцарей и купцов (n>1), каждый житель либо рыцарь, либо купец, и все друг про друга знают, кто они, рыцари или купцы. Рыцари всегда говорят правду, купцы могут и лгать. Рыцарей больше, чем купцов. Можно задавать любым горожанам вопросы типа "кем является такой-то" (в частности, можно спросить человека, кем является он сам). Другие вопросы задавать нельзя (например, нельзя спросить, верно ли, что у A и B одна и та же профессия, или что-то про количество рыцарей). Доказать, что можно узнать профессии всех горожан за
(a) 2n-2 вопроса
(b) 2n-3 вопроса
У этой задачи известно оптимальное решение, оно еще лучше, чем эти два задания (меньше вопросов), если хотите, попробуйте найти его тоже. Я запощу сюда послезавтра все решения и ссылки; если вы знаете или нашли ссылку на решение задачи, не кидайте ее до этого, пожалуйста. Комментарии скрывать не буду, там могут появляться спойлеры решений от других участников.