Форум умных людей

Задачи и головоломки => Помогите решить! => Тема начата: Черная кошка от Май 12, 2011, 15:38:58



Название: стол
Отправлено: Черная кошка от Май 12, 2011, 15:38:58
 За круглым столом сидит компания из тридцати человек. Каждый из них либо дурак, либо умный. Всех сидящих спрашивают: «Кто ваш сосед справа — умный или дурак?» В ответ умный говорит правду, а дурак может сказать как правду, так и ложь. Известно, что количество дураков не превосходит F. При каком наибольшем значении F всегда можно, зная эти ответы, указать на умного человека в этой компании?


Название: Re: стол
Отправлено: Sirion от Май 12, 2011, 17:03:58
Интересная задача. И актуальная, да.

Пятнадцать дураков заведомо много. Дальше буду решать по возвращении с пьянки)


Название: Re: стол
Отправлено: Sirion от Май 12, 2011, 18:27:34
Ага, десяти дураков тоже многовато. Пьянка отменилась =(


Название: Re: стол
Отправлено: Валерий от Май 12, 2011, 19:03:17
Думаю, что должно быть 7, что бы если и дураки скажут дурак, то сумма ответов не превысила половины общей суммы ответов.

Но это пока бездоказательно.


Название: Re: стол
Отправлено: Sirion от Май 12, 2011, 19:07:09
Ставлю свои любимые носки, что 9. Сейчас попью чайку и формализую.


Название: Re: стол
Отправлено: moonlight от Май 12, 2011, 19:22:59
точно меньше чем 10. если дураками будет назван каждый 6-й будет неопределенность. оставшимися 4-мя может быть  любая четверка подряд между двумя которых назвали дураками. 


Название: Re: стол
Отправлено: moonlight от Май 12, 2011, 19:33:11
в случае если не более 9 умный гарантированно будет тот кто последний в самой длинной цепочке из тех кто назван умным


Название: Re: стол
Отправлено: Sirion от Май 12, 2011, 19:42:47
moonlight, да, это именно то, что я написал бы, если бы мне не было лень. А вот как строго доказать последнее утверждение?


Название: Re: стол
Отправлено: moonlight от Май 12, 2011, 19:46:28
я думаю что у тебя оно уже есть в более готовом виде так что давай своё доказательство, я смогу позже.


Название: Re: стол
Отправлено: Sirion от Май 12, 2011, 19:50:27
В том-то и проблема - пока что как собака. Всё чувствую, а сказать не могу.


Название: Re: стол
Отправлено: Sirion от Май 12, 2011, 20:06:22
А вот нет, кстати. Есть контрпример для девяти. Я проспорил свои любимые носки. Хотя, видимо, придумав этот контрпример, я сам их у себя и выиграл, ня.


Название: Re: стол
Отправлено: Sirion от Май 12, 2011, 20:26:44
Итак, доказательство.

Рассадим 8 дураков и 22 умных людей за стол. При этом образуется N<=8 серий из подряд сидящих умных (и, соответственно, подряд сидящих дураков). Мы их спрашиваем, они нам отвечают. Теперь мы хотим доказать, что последний умный человек в самой длинной серии умных людей незаменяем. Докажем от противного.

Чтобы рассадить компанию иначе, нам нужно несколько дураков поменять местами с умными людьми. Чтобы заменить дураком последнего умного человека в серии, нам нужно заменить и остальных умных людей в серии - по очевидным причинам. Откуда ж мы возьмём столько дураков? Мы не можем заменять умными людьми дураков, сидящих в начале серии - иначе умный человек перед ними изменил бы ответ. Единственное исключение - если мы этого умного человека тоже заменяем дураком. Таким образом, для подмены самой длинной серии умных людей дураками мы можем взять одного дурака из начала последующей серии дураков, а остальных - из "хвостов" дураковых серий. Нетрудно подсчитать, что всего дураков, НЕ первых в своих сериях, будет 8-N. Соответственно, самая длинная серия умных людей должна быть не длиннее 9-N. С другой стороны, по принципу Дирихле найдётся серия умных людей не короче 22/N. Получаем неравенство: 22/N<=9-N. Тупым перебором доказываем, что для N от 1 до 8 неравенство не выполняется.
Контрпример для девяти: умных людей рассаживаем семью группами по 3, между этими группами - дураков произвольным образом. Всех дураков заставляем отвечать, что сосед справа умный. У нас получается два "мобильных" дурака в хвостах серий; любая серия умных может быть заменена  с помощью этих двух дураков и ещё одного дурака сразу после этой серии.


Название: Re: стол
Отправлено: Леший от Май 12, 2011, 22:30:36
В ответ умный говорит правду, а дурак может сказать как правду, так и ложь.

Я один считаю, что дураков и умных в условие надо поменять местами?


Название: Re: стол
Отправлено: Sirion от Май 12, 2011, 22:46:59
Таки нет)


Название: Re: стол
Отправлено: Лев от Май 13, 2011, 09:11:27
В ответ умный говорит правду, а дурак может сказать как правду, так и ложь.

Я один считаю, что дураков и умных в условие надо поменять местами?


Просто указанная фраза ложь - все на своих местах :)


Название: Re: стол
Отправлено: infant от Май 13, 2011, 17:17:32
=)