Задачник :: СМЕКАЛКИ.НЕТ

<< Предыдущая задача

К списку задач

Задача 1. Сколько среди вас лжецов?

На одном острове все люди были либо рыцарями, либо лжецами. Лжецы всегда говорили неправду, а рыцари - правду. Всего жителей было N. Однажды к ним приехал путешественник, который мог каждый день выбрать произвольную группу жителей и спросить у них: "сколько в вашей группе лжецов?" Сколько дней нужно путешественнику, чтобы гарантированно выявить всех лжецов на острове?

Автор: Agnis Andžāns и др.

07.01.2018

Ваш ответ

Правильно! Авторский ответ: 2 дня

Неправильно, попробуйте обдумать задание ещё раз!

Подсказка

Вы уверены, что хотите получить подсказку? Это действие необратимо и может не позволить Вам получить максимальное удовольствие от решения задачи! Если вы абсолютно уверены, то нажмите сюда.

Ответ не зависит от N

Решение и ответ

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

Авторский ответ: 2 дня

Если вы хотите подсмотреть ещё и авторский ход решения задачи, то нажмите сюда.

Авторское решение: В первый день необходимо собрать всех жителей и спросить, сколько среди них лжецов. Понятно, что все рыцари назовут одно и то же (правдивое) число, но могут быть и другие группы людей (лжецов), назвавших одно и то же число. Во второй день достаточно взять из каждой группы (пускай число таких групп - K), назвавшей разное число лжецов, по 1 представителю и всем им задать вопрос. Рыцарь и только он должен ответить, что лжецов ровно K-1. Таким образом, путешественник узнал рыцаря и всех членов его группы по первому дню.