Разделы 
Дополнительно
Задача по математике - 1782
2019-01-20 
За круглым столом сидит компания из тридцати человек. Каждый из них либо дурак, либо умный. Всех сидящих спрашивают: «Кто Ваш сосед справа - умный или дурак?» В ответ умный говорит правду, а дурак может сказать как правду, так и ложь. Известно, что количество дураков не превосходит $F$. При каком наибольшем значении $F$ всегда можно, зная эти ответы, указать на умного человека в этой компании?
Решение:
Если $F = 0$, то можно указать на любого человека, сидящего за столом.
Пусть теперь $F = 0$. Разобьем всех сидящих за столом на непустые группы подряд сидящих умных и подряд сидящих дураков; число этих групп обозначим через $2k$ ($k$ групп умных и $k$ групп дураков). Количество людей в $i$-й группе умных обозначим через $w_i$, а количество людей в $i$-й группе дураков - через $f_i (1 \leq i \leq k)$. Тогда $f_1 + f_2 + \cdots + f_k \leq F$. Рассмотрим последовательность подряд идущих ответов «умный» и последнего человека $x$, про которого так говорят. Группа из $w_i$ умных дает такую последовательность длины не меньше $w_i - 1$, при этом $x$ - действительно умный. Если же $x$ - дурак и находится в $i$-й группе дураков, то длина такой последовательности не более $f_i - 1$. Следовательно, если $max_{i} w_i > max_{i} f_i$, то можно утверждать, что последний человек, который назван умным в самой длинной последовательности ответов «умный», действительно умный. Так как $max_{i} w_i \geq \frac{30 - (f_1 + \cdots + f_k)}{k} \geq \frac{30 - F}{k}$,
$max_{i} f_i \leq (f_1 + \cdots + f_k) - k + 1 \leq F - k +1$,
то если неравенство $\frac{30 - F}{k} > F - k +1$, выполняется при всех $k$ от 1 до $F$, то можно указать на умного человека, сидящего за столом. Это неравенство равносильно такому: $k^2 - (F +1)k + 30 - F > 0$. Оно справедливо для всех $к$, если $D = (F + 1)^2 + 4(F - 30) < 0$, т. е. при $F < - 3 + \sqrt{128} < -3 + 12 = 9$. Итак, при $F \leq 8$ можно на основании данных ответов указать на умного человека.
При $F = 9$ это не всегда возможно. Действительно, рассмотрим компанию, сидящую за столом так, как показано на рис. (на рисунке рядом со стрелочками даны ответы: $у$ - «умный», $д$ - «дурак»; дураки показаны заштрихованными кружочками).
Будем поворачивать эту картинку вокруг центра на углы $60^{\circ}, 120^{\circ}, 180^{\circ}, 240^{\circ}$ и, наконец, $300^{\circ}$ по часовой стрелке. При этом, как нетрудно проверить, на каждом месте может оказаться как умный, так и дурак, а последовательность ответов останется той же самой. Поэтому в такой компании указать на умного человека на основании данных ответов невозможно.
Ответ. При $F = 8$.
За круглым столом сидит компания из тридцати человек. Каждый из них либо дурак, либо умный. Всех сидящих спрашивают: «Кто Ваш сосед справа - умный или дурак?» В ответ умный говорит правду, а дурак может сказать как правду, так и ложь. Известно, что количество дураков не превосходит $F$. При каком наибольшем значении $F$ всегда можно, зная эти ответы, указать на умного человека в этой компании?
Решение:
Если $F = 0$, то можно указать на любого человека, сидящего за столом.
Пусть теперь $F = 0$. Разобьем всех сидящих за столом на непустые группы подряд сидящих умных и подряд сидящих дураков; число этих групп обозначим через $2k$ ($k$ групп умных и $k$ групп дураков). Количество людей в $i$-й группе умных обозначим через $w_i$, а количество людей в $i$-й группе дураков - через $f_i (1 \leq i \leq k)$. Тогда $f_1 + f_2 + \cdots + f_k \leq F$. Рассмотрим последовательность подряд идущих ответов «умный» и последнего человека $x$, про которого так говорят. Группа из $w_i$ умных дает такую последовательность длины не меньше $w_i - 1$, при этом $x$ - действительно умный. Если же $x$ - дурак и находится в $i$-й группе дураков, то длина такой последовательности не более $f_i - 1$. Следовательно, если $max_{i} w_i > max_{i} f_i$, то можно утверждать, что последний человек, который назван умным в самой длинной последовательности ответов «умный», действительно умный. Так как $max_{i} w_i \geq \frac{30 - (f_1 + \cdots + f_k)}{k} \geq \frac{30 - F}{k}$,
$max_{i} f_i \leq (f_1 + \cdots + f_k) - k + 1 \leq F - k +1$,
то если неравенство $\frac{30 - F}{k} > F - k +1$, выполняется при всех $k$ от 1 до $F$, то можно указать на умного человека, сидящего за столом. Это неравенство равносильно такому: $k^2 - (F +1)k + 30 - F > 0$. Оно справедливо для всех $к$, если $D = (F + 1)^2 + 4(F - 30) < 0$, т. е. при $F < - 3 + \sqrt{128} < -3 + 12 = 9$. Итак, при $F \leq 8$ можно на основании данных ответов указать на умного человека.
При $F = 9$ это не всегда возможно. Действительно, рассмотрим компанию, сидящую за столом так, как показано на рис. (на рисунке рядом со стрелочками даны ответы: $у$ - «умный», $д$ - «дурак»; дураки показаны заштрихованными кружочками).
Будем поворачивать эту картинку вокруг центра на углы $60^{\circ}, 120^{\circ}, 180^{\circ}, 240^{\circ}$ и, наконец, $300^{\circ}$ по часовой стрелке. При этом, как нетрудно проверить, на каждом месте может оказаться как умный, так и дурак, а последовательность ответов останется той же самой. Поэтому в такой компании указать на умного человека на основании данных ответов невозможно.
Ответ. При $F = 8$.
