«Квант» — научно-популярный физико-математический журнал (издаётся с 1970 года)
Старый сайт журнала: kvant.ras.ru

Задача М1408

Условие задачи (1993, № 11/12) Задача М1408 // Квант. — 1993. — № 11/12. — Стр. 24; 1994. — № 3. — Стр. 24.

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

О. Ляшко


Решение задачи (1994, № 3) Задача М1408 // Квант. — 1993. — № 11/12. — Стр. 24; 1994. — № 3. — Стр. 24.

Ответ: при $F=8$‍.

Если $F=0$‍,‍ то можно указать на любого человека, сидящего за столом.

Пусть теперь $F\neq0$‍.‍ Разобьём всех сидящих за столом на непустые группы подряд сидящих умных и подряд сидящих дураков; число этих групп обозначим через 2$k$‍($k$‍‍ групп умных и $k$‍‍ групп дураков). Количество людей в $i$‍‍-й группе умных обозначим через $\omega_i$‍,‍ а количество людей в $i$‍‍-группе дураков — через $f_i$‍($1\le i\le k$‍).‍ Тогда $$ \omega_1+\omega_2+\ldots+\omega_k+f_1+f_2+\ldots+f_k=30 $$ и $f_1+f_2+\ldots+f_k\le F$‍.‍ Рассмотрим последовательность подряд идущих ответов «умный» и последнего человека $x$‍,‍ про которого так говорят. Группа их $\omega_i$‍‍ умных даёт такую последовательность длиной не меньше $\omega_i-1$‍,‍ при этом $x$‍‍ — действительно умный. Если же $x$‍‍ — дурак и находится в $i$‍‍-й группе дураков, то длина такой последовательности ответов не более $f_i-1$‍.‍ Следовательно, если $\max \omega_i\gt\max f_i$‍,‍ то можно утверждать, что последний человек, который назван умным в самой длинной последовательности ответов «умный», действительно умный. Так как $$\begin{gather*} \max_i f_i\ge\frac{30-(f_i+\ldots+j_k)}{k}\ge\frac{30-F}{k},\\ \max_i f_i\le (f_i+\ldots+f_k)-k+1\le F-k+1, \end{gather*}$$ то если неравенство $\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$‍‍ это не всегда возможно. Действительно, рассмотрим компанию, сидящую за столом так, как показано на рисунке (рядом со стрелочками даны ответы: $\omega$‍‍ — «умный», $f$‍‍ — «дурак»; дураки показаны заштрихованными кружочками).

Рисунок номер 1

Будем поворачивать эту картинку вокруг центра на углы $60^\circ$‍,$120^\circ$‍,$180^\circ$‍,$240^\circ$‍‍ и, наконец, $300^\circ$‍‍ по часовой стрелке. При этом, как нетрудно проверить, на каждом месте может оказаться как умный, так и дурак, а последовательность ответов останется той же самой. Поэтому в такой компании указать на умного человека на основании данных ответов невозможно.

О. Ляшко


Метаданные Задача М1408 // Квант. — 1993. — № 11/12. — Стр. 24; 1994. — № 3. — Стр. 24.

Предмет
Математика
Условие
Решение
Номера

1993. — № 11/12. — Стр.  [условие]

1994. — № 3. — Стр.  [решение]

Описание
Задача М1408 // Квант. — 1993. — № 11/12. — Стр. 24; 1994. — № 3. — Стр. 24.
Ссылка
https://www.kvant.digital/problems/m1408/