Рыцари и купцы
Отсюда
Выстроим всех жителей в круг и будем спрашивать жителей по очереди, кем является их сосед одесную. Заметим, что только когда все стоящие в кольце - рыцари, все ответят, что их сосед - рыцарь. В любом другом случае хотя бы один из жителей да ответит "купец". Помимо того, заметим, что когда кто-либо отвечает, что его сосед одесную - купец, либо он сам, либо этот самый сосед, либо оба они являются купцами. В любом случае, при выводе этих двух жителей из кольца (и замыкании кольца сближением их соседей) разница между количеством рыцарей и купцов в кольце не уменьшается. Наконец, тот факт, что рыцарей строго больше, чем купцов, гарантирует, что упомянутое выше изгнание пар жителей из кольца, повторенное столько раз, сколько это возможно, приведёт нас к кольцу, где каждый оставшийся говорит, что его сосед - рыцарь. Пускай а - число пар, изгнанных из кольца, а b - число жителей, оставшихся в «рыцарском» кольце. Тогда число вопросов, которое мы истратим, чтобы дойти от кольца, в котором никто ещё не дал ответа, к «рыцарскому» кольцу - a+b. В кольце, согласно нашему наблюдению, обязательно остался хотя бы один житель, и все, кто остались - рыцари, стало быть, чтобы определить, кем являются изгнанные из кольца, достаточно спросить об этом одного из рыцарей в кольце. На это потребуется ещё 2a вопросов. В общей сложности, после за (a+b) + 2a = 3a+b вопросов мы будем знать всё, что нужно. Осталось определить максимальное значение этого выражения. Поскольку 2a+b = n, то оно равно n+a. Так как в кольце должен был остаться по крайней мере один рыцарь,
, значит, максимальное количество вопросов -)
, что не больше, чем (2n-3) при
. В случае n=2 никого ничего спрашивать не надо, поскольку и так понятно, что оба рыцари, то есть можно обойтись нулём вопросов, что меньше, чем 2n-3 = 1. В случае n=3 идём по общей схеме с небольшим отклонением: если все трое рыцари, то после трёх вопросов всё становится понятным, а если двое рыцари, то оставшийся в кольце рыцарь должен явно определить только одного из выбывших (это и есть отклонение от общей схемы), а второй выбывший определяется автоматом, поскольку среди выбывших обязательно один рыцарь и один купец. В любом случае, можно обойтись тремя вопросами, что равно 2n-3 = 3.
Описанная схема, таким образом, обходится (2n-3)-мя или меньшим числом вопросов при любом n.
Выстроим всех жителей в круг и будем спрашивать жителей по очереди, кем является их сосед одесную. Заметим, что только когда все стоящие в кольце - рыцари, все ответят, что их сосед - рыцарь. В любом другом случае хотя бы один из жителей да ответит "купец". Помимо того, заметим, что когда кто-либо отвечает, что его сосед одесную - купец, либо он сам, либо этот самый сосед, либо оба они являются купцами. В любом случае, при выводе этих двух жителей из кольца (и замыкании кольца сближением их соседей) разница между количеством рыцарей и купцов в кольце не уменьшается. Наконец, тот факт, что рыцарей строго больше, чем купцов, гарантирует, что упомянутое выше изгнание пар жителей из кольца, повторенное столько раз, сколько это возможно, приведёт нас к кольцу, где каждый оставшийся говорит, что его сосед - рыцарь. Пускай а - число пар, изгнанных из кольца, а b - число жителей, оставшихся в «рыцарском» кольце. Тогда число вопросов, которое мы истратим, чтобы дойти от кольца, в котором никто ещё не дал ответа, к «рыцарскому» кольцу - a+b. В кольце, согласно нашему наблюдению, обязательно остался хотя бы один житель, и все, кто остались - рыцари, стало быть, чтобы определить, кем являются изгнанные из кольца, достаточно спросить об этом одного из рыцарей в кольце. На это потребуется ещё 2a вопросов. В общей сложности, после за (a+b) + 2a = 3a+b вопросов мы будем знать всё, что нужно. Осталось определить максимальное значение этого выражения. Поскольку 2a+b = n, то оно равно n+a. Так как в кольце должен был остаться по крайней мере один рыцарь,
, значит, максимальное количество вопросов -
, что не больше, чем (2n-3) при
. В случае n=2 никого ничего спрашивать не надо, поскольку и так понятно, что оба рыцари, то есть можно обойтись нулём вопросов, что меньше, чем 2n-3 = 1. В случае n=3 идём по общей схеме с небольшим отклонением: если все трое рыцари, то после трёх вопросов всё становится понятным, а если двое рыцари, то оставшийся в кольце рыцарь должен явно определить только одного из выбывших (это и есть отклонение от общей схемы), а второй выбывший определяется автоматом, поскольку среди выбывших обязательно один рыцарь и один купец. В любом случае, можно обойтись тремя вопросами, что равно 2n-3 = 3.
Описанная схема, таким образом, обходится (2n-3)-мя или меньшим числом вопросов при любом n.