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

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

Интересная задача. И актуальная, да.

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

Ага, десяти дураков тоже многовато. Пьянка отменилась =(

Думаю, что должно быть 7, что бы если и дураки скажут дурак, то сумма ответов не превысила половины общей суммы ответов.

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

Ставлю свои любимые носки, что 9. Сейчас попью чайку и формализую.

точно меньше чем 10. если дураками будет назван каждый 6-й будет неопределенность. оставшимися 4-мя может быть  любая четверка подряд между двумя которых назвали дураками. 

в случае если не более 9 умный гарантированно будет тот кто последний в самой длинной цепочке из тех кто назван умным

moonlight, да, это именно то, что я написал бы, если бы мне не было лень. А вот как строго доказать последнее утверждение?

я думаю что у тебя оно уже есть в более готовом виде так что давай своё доказательство, я смогу позже.

В том-то и проблема - пока что как собака. Всё чувствую, а сказать не могу.

А вот нет, кстати. Есть контрпример для девяти. Я проспорил свои любимые носки. Хотя, видимо, придумав этот контрпример, я сам их у себя и выиграл, ня.

Итак, доказательство.

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

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

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

Таки нет)

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

=)