По кругу стоят 11 человек. Правдолюбы - всегда говорят правду, лжецы-всегда лгут и хитрецы-правдолюбам и другим хитрецам говорят правду, а лгунам-лгут. Каждый сказал своему соседу справа, что среди его соседей есть лжец. Докажите, что там есть хотя бы 4 лжеца.

1. Предположим, что среди 11 человек не больше трех лжецов. Тогда найдется такой хитрец или правдолюб, рядом с которым также стоят хитрецы или правдолюбы. В этом случае он не мог говорить о том, что среди его соседей есть лжец. Следовательно, лжецов больше трех.

2. Покажем ситуацию с четырьмя лжецами. Пусть xi - человек в i-й позиции в кругу, i = 1 до 11, и пусть по кругу стоят следующим образом:

x1 = x4 = x7 = x10 - правдолюб; x2 = x5 = x8 = x11 - лжец; x3 = x6 = x9 - хитрец. a) Тогда каждый лжец окружен правдолюбом или хитрецом, и он солжет, сказав, что среди его соседей есть лжец; b) Каждый правдолюб окружен хотя бы одним лжецом, и он скажет правду, что среди его соседей есть лжец; b) А каждый хитрец окружен лжецом слева и правдолюбом справа, поэтому и он скажет правдолюбу правду, что среди его соседей есть лжец.

Что и требовалось доказать.