Республиканская юниорская олимпиада по математике. Заключительный этап. 2017-2018 учебный год

За круглым столом сидят рыцари, которые всегда говорят правду, лжецы, которые всегда лгут и хитрецы, которые могут лгать или говорить правду по своему выбору. Всего 2018 человек. Каждый из сидящих произнёс две фразы: «Мой левый сосед – лжец». «Мой правый сосед – хитрец». Какое наименьшее количество хитрецов могло сидеть за этим столом?

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

Ответ: 674 хитреца

Л-лжец, остальные аналогично

Заметим, что:

1) слева от Л обязательно сидит Х,

т.к Л сидеть не может иначе он говорит правду, а Р не может иначе Р будет лгать насчет правого соседа;

2) Справа от Л обязательно сидит Р,

т.к если сидит Х то Л говорит правду, а если еще один Л, то второй Л говорит правду, что невозможно

3) Также заметим, что слева от Р обязательно сидит Л, а справа Х(по условиям).

4) Рядом с Х очевидно может сидеть кто угодно.

Тогда при добавлении Л или Р(БОО) в круг следует появление такой цепочки: Х-Л-Р-Х.

Представим круг из 2018 Х, тогда при добавлении в круг Л или Р(БОО) обязательно будут меняться только 2 буквы( на Л и Р), и кол-во Х будет уменьшаться на 2, однако между парами Л-Р всегда будет стоять хотя бы 1 Х.

Т.к они стоят в кругу на каждую пару приходится один Х(стоящий рядом, легко заметить нарисовав круг), следовательно 2018:3=672(2 ост) , т.е. смотрим максимальное число таких троиц, которые могут поместиться в кругу. Т.к. в каждой троице 2 человека, не являющиеся Х, следует что 2018 - 672*2=674 Х, не поменяются.