Областная олимпиада по математике, 2007 год, 11 класс

Эльфы и тролли сидят за круглым столом, всего 60 существ. Тролли всегда лгут, эльфы говорят правду, кроме случаев, когда они «ошибаются». Каждый из сидящих утверждает, что сидит между эльфом и троллем, причем ровно два эльфа «ошиблись». Сколько троллей сидит за столом?

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

Посмотрим на расположение существ, если бы два эльфа не ошиблись. Рядом с эльфом обязательно сидел бы троль и эльф, то есть $ТЭЭ ТЭЭ $. Рядом со вторым эльфом будет сидеть справа троль, так как слева уже сидит эльф , то есть $ТЭЭТТЭЭТ $

.троли всегда лгут ,поэтому справа троля будет сидеть эльф. Получим $ТЭЭТЭЭ$

,то есть отношение эльфов к троллям 2 к 1. Вспомним, что два эльфа ошиблись. Посмотрим на такую цепочку. Должно быть $ЭЭТЭЭТЭЭ $, а получилось

В итоге получили на 2 тролля больше, и на 2 эльфа меньше, то есть 38 эльфов и 22 тролля

Докажем, что все тролли сидят по одному, т. е. левее и правее каждого тролля сидят эльфы. Действительно, в цепочке подряд сидящих троллей крайние тролли скажут правду.

Пусть количество троллей равно п. Основная масса эльфов сидят по двое, тогда левее и правее каждого эльфа будут эльф или тролль.

Только для двух эльфов это условие не выполняется. В записи точками сверху отмечены те эльфы, которые «ошиблись». Возможны случаи:

1) TEĖĖET; 2) TEĖETEĖET; 3) TEĖETĖT; 4) TĖTĖT.

В случаях (1) и (2) имеем 2n + 2 эльфов и n + 2n + 2 = 60, 3n = 58 - решения нет. В случае (3) имеем 2п эльфов и n + 2n = 60, n = 20. В случае (4), 2n - 2 эльфов и n + 2n - 2 = 60, 3n = 62 - решения нет.

Ответ: 20 троллей