Question

К Холмсу пришли 25 рыцарей и лжецов, но рыцарей было больше. Холмс, зная это, может задавать любому вопрос типа: "Кто такой-то : рыцарь или лжец?" Как Холмсу узнать, кто есть кто, за 24 вопроса?

Answer 1

Выберем одного из 25 пришедших. Тогда среди оставшихся 24 либо рыцарей больше, чем лжецов, либо их поровну.
Будем спрашивать каждого из этих 24 относительно одного из выбранных.
Все лжецы дают одинаковые ответы и все рыцари дают одинаковые ответы, ответы рыцарей и лжецов различны.
Поэтому если какой-то ответ преобладал, то этот ответ давали рыцари, противоположный ответ давали лжецы, а так как рыцари говорят правду, то преобладающий ответ был правдой. Значит за 24 вопроса мы все определили.
Если ответов было поровну, то среди этих 24 одинаковое количество рыцарей и лжецов, а значит выбранный - рыцарь. Тогда те, кто ответил "рыцарь" - рыцари, а кто ответил "лжец" - лжецы. Мы вновь за 24 вопроса узнали все, что было необходимо.

Answer 2

Для решения этой задачи, Холмс может использовать стратегию вопросов, которая позволит ему идентифицировать каждого человека за 24 вопроса. Вот план действий:

Шаг 1: Разделение на группы

• Первый вопрос Холмс задает любому человеку: "Сколько среди вас рыцарей?" Допустим, этот человек отвечает "х рыцарей".
• Теперь Холмс знает, что среди остальных (25 - х) человек лжецов.

Шаг 2: Определение рыцарей

• Холмс продолжает задавать вопросы (всего х - 1 вопрос) каждому человеку из группы, кроме первого. Он спрашивает: "Кто такой [имя человека] : рыцарь или лжец?" Поскольку он знает, что среди оставшихся только лжецы, он получит правдивый ответ каждый раз.

После этого Холмс узнает имена всех рыцарей.

Шаг 3: Определение лжецов

• Холмс переходит к оставшимся (25 - х) человекам, которые являются лжецами. Он задает каждому из них по одному вопросу: "Кто такой [имя человека] : рыцарь или лжец?" Таким образом, он узнает, кто из них лжецы, а кто — рыцари.

Итого, Холмсу потребуется х + (25 - х) = 25 вопросов, чтобы идентифицировать всех рыцарей и лжецов. Если х равно, например, 10 (то есть среди группы было 10 рыцарей и 15 лжецов), то ему потребуется 24 вопроса, чтобы разгадать ситуацию.