Олимпиада имени Леонарда Эйлера2013-2014 учебный год, III тур дистанционного этапа

30 человек выстроены в шесть шеренг по пять человек в каждой. Каждый из них либо рыцарь, всегда говорящий правду, либо лжец, который всегда лжёт, и всем им известно, кто из них рыцарь, а кто — лжец. Журналист спросил у каждого из них: «Верно ли, что найдутся хотя бы 4 шеренги, в каждой из которых лжецов больше половины?». Какое наибольшее количество ответов "да" он мог услышать?

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.     Ответ. 21.
Решение. Назовем шеренгу синей, если в ней больше половины (то есть не меньше трёх) лжецов и красной, если лжецов в ней не больше двух. Пусть «да» сказали рыцари. Тогда у нас не больше двух красных и не меньше четырёх синих шеренг. В красных шеренгах стоят не больше 10 рыцарей, в синих — не больше $2 \cdot 4 = 8$ рыцарей. Поэтому ответов «да» в этом случае не больше 18. Пусть «да» сказали лжецы. Тогда у нас не больше трёх синих шеренг и не меньше трёх красных. В синих шеренгах не больше 15 лжецов, в красных — не больше $ 2 \cdot 3 = 6$ лжецов, всего — не больше 21 лжеца, то есть ответов «да» в этом случае не больше 21. Ровно 21 ответ «да» возможен, если в трёх шеренгах стоит по 5 лжецов, а в трёх других — по 2 лжеца.