Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

задачка про рыцарей и купцов

Нелегкая и интересная задачка, которая мне не попадалась раньше (спасибо urod за то, что написал о ней).

В городе живут n рыцарей и купцов (n>1), каждый житель либо рыцарь, либо купец, и все друг про друга знают, кто они, рыцари или купцы. Рыцари всегда говорят правду, купцы могут и лгать. Рыцарей больше, чем купцов. Можно задавать любым горожанам вопросы типа "кем является такой-то" (в частности, можно спросить человека, кем является он сам). Другие вопросы задавать нельзя (например, нельзя спросить, верно ли, что у A и B одна и та же профессия, или что-то про количество рыцарей). Доказать, что можно узнать профессии всех горожан за

(a) 2n-2 вопроса
(b) 2n-3 вопроса

У этой задачи известно оптимальное решение, оно еще лучше, чем эти два задания (меньше вопросов), если хотите, попробуйте найти его тоже. Я запощу сюда послезавтра все решения и ссылки; если вы знаете или нашли ссылку на решение задачи, не кидайте ее до этого, пожалуйста. Комментарии скрывать не буду, там могут появляться спойлеры решений от других участников.
Tags: задачка
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 48 comments