Задача 109517

Темы:    [ Математическая логика (прочее) ] [ Разбиения на пары и группы; биекции ] [ Рекуррентные соотношения (прочее) ] [ Оценка + пример ]

Сложность: 5+ Классы: 9,10,11

Условие

Автор: Ляшко О.

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

Решение

При F=8 . Если F=0 , то можно указать на любого человека, сидящего за столом. Пусть теперь F0 . Разобьем всех сидящих за столом на непустые группы подряд сидящих умных и подряд сидящих дураков; число этих групп обозначим через 2k ( k групп умных и k групп дураков). Количество людей в i -й группе умных обозначим через w_i , а количество людей в i -й группе дураков – через f_i ( 1 i k ). Тогда f₁+f₂ f_k F . Рассмотрим последовательность подряд идущих ответов умный и последнего человека x , про которого так говорят. Группа из w_i умных дает такую последовательность длины не меньше w_i-1 , при этом x – действительно умный. Если же x – дурак и находится в i -й группе дураков, то длина такой последовательности не более f_i-1 . Следовательно, если w_i> f_i , то можно утверждать, что последний человек, который назван умным в самой длинной последовательности ответов умный, действительно умный. Так как w_i ,

_i f_i (f₁+..+f_k)-k+1 F-k+1,
то если неравенство >F-k+1 выполняется при всех k от 1 до F , то можно указать на умного человека, сидящего за столом. Это неравенство равносильно такому:
k²-(F+1)k+30-F>0.


Оно справедливо для всех k , если D=(F+1)²+4(F-30)<0 , т.е. при F<-3+<-3+12=9 . Итак, при F8 можно на основании данных ответов указать на умного человека. При F=9 это не всегда возможно. Действительно, рассмотрим компанию, сидящую за столом так, как показано на 104 (на рисунке рядом со стрелочками даны ответы: у – умный, д – дурак; дураки показаны заштрихованными кружочками). Будем поворачивать эту картинку вокруг центра на углы 60^o , 120^o , 180^o , 240^o и, наконец, 300^o по часовой стрелке. При этом, как нетрудно проверить, на каждом месте может оказаться как умный, так и дурак, а последовательность ответов останется той же самой. Поэтому в такой компании указать на умного человека на основании данных ответов невозможно.

Ответ

При F=8 .

Источники и прецеденты использования

олимпиада
Название	Всероссийская олимпиада по математике
год
Год	1993
Этап
Вариант	5
класс
Класс	10
задача
Номер	93.5.10.4