2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2  След.
 
 Как найти звезду в группе?
Сообщение09.05.2012, 23:02 
Здравствуйте, друзья!
Подскажите, пожалуйста, вот с такой задачей:

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

bool first_knows_second(int first, int second);

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

 
 
 
 Re: Как найти звезду в группе?
Сообщение10.05.2012, 09:49 
Аватара пользователя
$N-1$

 
 
 
 Re: Как найти звезду в группе?
Сообщение10.05.2012, 12:45 
worm2
Я думаю так же, но не могу обосновать.

 
 
 
 Re: Как найти звезду в группе?
Сообщение10.05.2012, 12:48 
Аватара пользователя
По индукции.

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

 
 
 
 Re: Как найти звезду в группе?
Сообщение04.06.2012, 19:34 
В "противном случае" бывают разные.

 
 
 
 Re: Как найти звезду в группе?
Сообщение02.07.2012, 09:17 
Аватара пользователя
Donald Capacine в сообщении #569211 писал(а):
его знают все, а он не знает никого.

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

 
 
 
 Re: Как найти звезду в группе?
Сообщение02.07.2012, 11:20 
Аватара пользователя
Shadow в сообщении #569430 писал(а):
Каждый вызов функции элиминирует одного человека. Если функция возвращает True, значит first не может быть звездой, а если False, то second не может быть. Необходимо элиминировать человек.

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

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

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

 
 
 
 Re: Как найти звезду в группе?
Сообщение02.07.2012, 20:16 
AnDe в сообщении #591235 писал(а):
Откуда Вы знаете, что для того, чтобы указать звезду необходимо элиминировать всех остальных?
Потому что каждый из оставшихся не проиграл ни одного матча. (даже если вообще не играл). И может стать чемпионом.

 
 
 
 Re: Как найти звезду в группе?
Сообщение04.07.2012, 08:47 
Аватара пользователя
AnDe в сообщении #591235 писал(а):
Shadow в сообщении #569430 писал(а):
Каждый вызов функции элиминирует одного человека. Если функция возвращает True, значит first не может быть звездой, а если False, то second не может быть. Необходимо элиминировать человек.

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

Из условия.
Цитата:
есть один и только один

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

 
 
 
 Re: Как найти звезду в группе?
Сообщение05.07.2012, 17:06 
Аватара пользователя
Евгений Машеров в сообщении #591940 писал(а):
Откуда Вы знаете, что для того, чтобы указать звезду необходимо элиминировать всех остальных?

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

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

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

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

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

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

 
 
 
 Re: Как найти звезду в группе?
Сообщение05.07.2012, 18:28 
Аватара пользователя
Профессор Снэйп в сообщении #592416 писал(а):
Для каждой последовательности True и False длины необходимо подобрать таких варианта группы, чтобы в этих вариантах были разные "звёзды", а ответы бы шли согласно последовательностям.
Думаю, это возможно.

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

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

 
 
 
 Re: Как найти звезду в группе?
Сообщение06.07.2012, 10:44 
Аватара пользователя
Да, с цитатами тут сильно запуталось.

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

 
 
 
 Re: Как найти звезду в группе?
Сообщение06.07.2012, 13:20 

(Оффтоп)

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}$ указать звезду. И все.

 
 
 [ Сообщений: 17 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group