Олимпиадная задача по математической логике для 9-11 классов — кто умный за круглым столом?

При 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 по часовой стрелке. При этом, как нетрудно проверить, на каждом месте может оказаться как умный, так и дурак, а последовательность ответов останется той же самой. Поэтому в такой компании указать на умного человека на основании данных ответов невозможно.