Как найти звезду в группе?

[Donald Capacine]

Здравствуйте, друзья!
Подскажите, пожалуйста, вот с такой задачей:

"Дана группа из $N$ человек. Каждый человек в этой группе имеет уникальный номер от $1$ до $N$.
Какие-то члены этой группы знакомы друг с другом, какие-то нет.
В этой группе есть один и только один особенный человек (будем называть его "звезда"),
который отличатся от других членов группы тем, что его знают все, а он не знает никого.
Существует функция (уже реализована):

bool first_knows_second(int first, int second);

Эта функция возвращает $true$, если $first$ знает $second$, в противном
случае возвращает $false$.
Какого количество вызовов этой функции необходимо и достаточно, что бы
найти в этой группе звезду?"

[worm2]

$N-1$

[Donald Capacine]

worm2
Я думаю так же, но не могу обосновать.

[gris]

По индукции.

[Shadow]

Каждый вызов функции элиминирует одного человека. Если функция возвращает True, значит first не может быть звездой, а если False, то second не может быть. Необходимо элиминировать $n-1$ человек.

[Monkey]

В "противном случае" бывают разные.

[Профессор Снэйп]

Donald Capacine в сообщении #569211 писал(а):

его знают все, а он не знает никого.

Знает ли он сам себя?

[AnDe]

Shadow в сообщении #569430 писал(а):

Каждый вызов функции элиминирует одного человека. Если функция возвращает True, значит first не может быть звездой, а если False, то second не может быть. Необходимо элиминировать человек.

Это говорит только о достаточности N-1 хода. Откуда Вы знаете, что для того, чтобы указать звезду необходимо элиминировать всех остальных?

Профессор Снэйп в сообщении #591193 писал(а):

Знает ли он сам себя?

С одной стороны его все (т.е. и он сам) знают, а с другой он никого не знает (т.е. и самого себя). Выходит, что задача с противоречием в условии

[Shadow]

AnDe в сообщении #591235 писал(а):

Откуда Вы знаете, что для того, чтобы указать звезду необходимо элиминировать всех остальных?

Потому что каждый из оставшихся не проиграл ни одного матча. (даже если вообще не играл). И может стать чемпионом.

[Евгений Машеров]

AnDe в сообщении #591235 писал(а):

Shadow в сообщении #569430 писал(а):

Каждый вызов функции элиминирует одного человека. Если функция возвращает True, значит first не может быть звездой, а если False, то second не может быть. Необходимо элиминировать человек.

Это говорит только о достаточности N-1 хода. Откуда Вы знаете, что для того, чтобы указать звезду необходимо элиминировать всех остальных?

Из условия.

Цитата:

есть один и только один

[AnDe]

Евгений Машеров
Не понимаю, можете объяснить? По сути условие "есть один и только один" - лишнее, можно было бы сказать, что просто есть один, больше одного их не могло быть по определению звезды. И это же условие говорит все таки о достаточности, мол отсеяли N-1, а последний точно - звезда. А вот необходимость я понял так: если у нас осталось больше одного кандидата, то мы можем построить модели, когда выполняется все что мы уже узнали, и звездами являются разные люди, а значит мы не можем однозначно определить звезду.

[Профессор Снэйп]

Евгений Машеров в сообщении #591940 писал(а):

Откуда Вы знаете, что для того, чтобы указать звезду необходимо элиминировать всех остальных?

Для каждой последовательности True и False длины $\leqslant N - 2$ необходимо подобрать таких $2$ варианта группы, чтобы в этих вариантах были разные "звёзды", а ответы бы шли согласно последовательностям.

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

-- Чт июл 05, 2012 20:09:31 --

Но, надо сказать, нудное это дело. Я помню, как решал подобную штуку про минимальное число взвешиваний для определения фальшивой монеты. Всё делается, но рассмотрения довольно кропотливые. Хотя, возможно, стоит почитать какую-нибудь продвинутую книжку по теории игр, там эти вещи наверняка разобраны.

-- Чт июл 05, 2012 20:12:57 --

А вообще-то тут довольно простая индукция по $N$. При $N=2$ хотя бы один вопрос необходим. При переходе от $N$ к $N+1$ при обоих вариантах ответа на первый вопрос легко выделяется ситуация, когда после первого ответа остаётся $N$ человек, про которых по прежнему ничего не известно...

[AnDe]

Профессор Снэйп в сообщении #592416 писал(а):

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

А вроде это легко на графах делается. Считаем людей за точки и проводим между ними разноцветные вектора. Например красный вектор от человека A до человека B, означает, что A не знает B. Синий вектор, что знает. А отсутствие за неопределенность. Если задали меньше N-1 вопроса осталось больше одного человека к которому не идет красных стрелок и от которых не идет синих стрелок, соответственно любой из них может стать звездой.

P.S. Вообще-то Вы цитируете мой вопрос, просто потом Евгений Машеров неудачно его цитировал. Какая-то последовательность неудачных цитирований

[Евгений Машеров]

Да, с цитатами тут сильно запуталось.

А по необходимости N-1 - ну, давайте рассмотрим задачу проще. Нам уже сказали, кто звезда. Надо этот факт лишь проверить. И всё равно менее N-1 проверки не выйдет...

[Shadow]

(Оффтоп)

AnDe в сообщении #592433 писал(а):

Какая-то последовательность неудачных цитирований

И начали ее Вы.
Internet Explorer - это браузер, предназначенный для скачивания другого браузера.
Если инструментарий не позволяет вам цитировать мои слова полностью, то нужно сделать это вручную.

AnDe в сообщении #591235 писал(а):

Shadow в сообщении #569430 писал(а):

Каждый вызов функции элиминирует одного человека. Если функция возвращает True, значит first не может быть звездой, а если False, то second не может быть. Необходимо элиминировать человек.

Shadow в сообщении #569430 писал(а):

Каждый вызов функции элиминирует одного человека. Если функция возвращает True, значит first не может быть звездой, а если False, то second не может быть. Необходимо элиминировать $n-1$ человек.

Единственное, что можно добится после $n-2$ вопросов - с вероятностью $\dfrac{n-1}{n}$ указать звезду. И все.