За круглым столом сидит компания из тридцати человек. Каждый из них либо дурак, либо умный. Всех сидящих спрашивают: «Кто ваш сосед справа — умный или дурак?». В ответ умный говорит правду, а дурак может сказать как правду, так и ложь. Известно, что количество дураков не превосходит $F$. При каком наибольшем значении $F$ всегда можно, зная эти ответы, указать на умного человека в этой компании?
Если $F=0$, то можно указать на любого человека, сидящего за столом.
Пусть теперь $F\ne0$. Разобьём всех сидящих за столом на непустые группы подряд сидящих умных и подряд сидящих дураков; число этих групп обозначим через $2k$ ($k$ групп умных и $k$ групп дураков). Количество людей в $i$-й группе умных обозначим через $w_i$, а количество людей в $i$-й группе дураков — через $f_i$ ($1\le i\le k$). Тогда
$$
w_1+w_2+\ldots+w_k+f_1+f_2+\ldots+f_k=30
$$
и $f_1+f_2+\ldots+f_k\le F$. Рассмотрим последовательность подряд идущих ответов «умный» и последнего человека $x$, про которого так говорят. Группа их $w_i$ умных даёт такую последовательность длиной не меньше $w_i-1$, при этом $x$ — действительно умный. Если же $x$ — дурак и находится в $i$-й группе дураков, то длина такой последовательности ответов не более $f_i-1$. Следовательно, если $\max w_i\gt\max f_i$, то можно утверждать, что последний человек, который назван умным в самой длинной последовательности ответов «умный», действительно умный. Так как
$$
\max_if_i\ge\dfrac{30-(f_i+\ldots+j_k)}k\ge\dfrac{30-F}k,\quad
\max_if_i\le (f_i+\ldots+f_k)-k+1\le F-k+1,
$$
то если неравенство $\dfrac{30-F}{k}\gt F-k+1$ выполняется при всех $k$ от 1 до $F$, то можно указать на умного человека, сидящего за столом. Это неравенство равносильно такому:
$$
k^2-(F+1)k+30-F\gt0.
$$
Оно справедливо для всех $k$, если $$D=(F+1)^2+4(F-30)\lt0,$$ т. е. при $F\lt-3+\sqrt{128}\lt-3+12=9$. Итак, при $F\le8$ можно на основании данных ответов указать на умного человека. При $F=9$ это не всегда возможно. Действительно, рассмотрим компанию, сидящую за столом так, как показано на рисунке (рядом со стрелочками даны ответы: $w$ — «умный», $f$ — «дурак»; дураки показаны заштрихованными кружочками).
Будем поворачивать эту картинку вокруг центра на углы $60^\circ$, $120^\circ$, $180^\circ$, $240^\circ$ и, наконец, $300^\circ$ по часовой стрелке. При этом, как нетрудно проверить, на каждом месте может оказаться как умный, так и дурак, а последовательность ответов останется той же самой. Поэтому в такой компании указать на умного человека на основании данных ответов невозможно.
