Question

на собрании присутсвовало k рыцарей и хитрецов, причем рыцарей было больше, чем хитрецов. путешественник хочет выяснить про каждого, кто он. Для этого он может задать вопрос "Кем является такой-то: рыцарем или хитрецом?" Докажите что путешественник может установить это за: а) 4k вопросов б) 2k -2 вопроса в)2k -3 вопроса​

Answer 1

Для решения этой задачи мы можем использовать метод дихотомии, который позволяет нам разделить группу людей пополам на каждом шаге.

Допустим, изначально у нас есть k рыцарей и h хитрецов, где k > h.

Шаг 1:
Путешественник задает вопрос "Кем является первый человек?" В результате этого вопроса он получает информацию о том, что первый человек - рыцарь или хитрец.

Шаг 2:
Далее путешественник разделяет оставшихся (k-1) рыцарей и h хитрецов на две группы примерно одинакового размера и повторяет тот же вопрос о первом человеке в каждой из этих групп. Таким образом, он выясняет кем являются два человека в каждой из групп.

На этом этапе у него осталось (k-2)/2 рыцарей и (h-2)/2 хитреца.

Шаг 3:
Путешественник повторяет шаг 2 еще два раза, разделить оставшихся рыцарей и хитрецов на две группы каждый раз, и задает вопрос о первом человеке в каждой группе.

На третьем шаге у него осталось (k-4)/4 рыцарей и (h-4)/4 хитреца.

Шаг 4:
На этом шаге путешественник делает то же самое, что и на предыдущих шагах, но уже с группами, содержащими по одному человеку.

На четвертом шаге у него остается по одному рыцарю и хитрецу. Теперь он точно знает, какая группа является группой рыцарей и группой хитрецов.

Таким образом, путешественник задаст общее количество вопросов:
а) 1 + 2 + 2 + 4 = 9 вопросов;
б) 1 + 2 + 2 + 2(k-2) = 2k - 3 вопросов;
в) 1 + 2 + 2 + 2(k-2) - 1 = 2k - 4 вопроса.

Таким образом, путешественник может установить, кем является каждый человек в собрании, задав:
а) 9 вопросов;
б) 2k - 3 вопроса;
в) 2k - 4 вопроса.