ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 109517
Темы:    [ Математическая логика (прочее) ]
[ Разбиения на пары и группы; биекции ]
[ Рекуррентные соотношения (прочее) ]
Сложность: 5+
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

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

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

Решение

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

i fi (f1+..+fk)-k+1 F-k+1,

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



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

Ответ

При F=8 .

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

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

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .