Рыцари и лжецы

Все сидящие за столом разбиваются на пары друзей; значит, рыцарей и лжецов поровну. Рассмотрим любую пару друзей. Если они сидят рядом, то рыцарь на заданный вопрос ответит “Да”, а лжец — “Нет”. Если же они не сидят рядом, то их ответы будут противоположными. В любом случае ровно один из пары друзей даст ответ “Да”. Значит, все остальные ответов будут “нет”.

Докажем, что ни в один момент времени ни про какое множество волшебников нельзя доказать, что в нём четное число рыцарей (из этого будет следовать оценка, ведь если нам в какой-то момент удалось определить сущность двоих волшебников, то либо мы доказали, что в их паре четное число рыцарей, либо это рыцарь и лжец, и мы еще за одну операцию сделаем из них двух рыцарей, подействовав рыцарем на лжеца).

Изначально такого множества точно нет. Рассмотрим первый момент, когда удалось про некоторое множество доказать, что в нем четное число рыцарей. Пусть последним ходом «Вжух!» говорил волшебник . Несложным переборов вариантов можно убедится, что на прошлом ходу симметрическая разность и тоже содержала четное количество рыцарей, что противоречит выбранному первому такому моменту.

_________________________________________________________________________________________________________________________________________________________________________________

Пример. Пусть все волшебники с -го по -го поменяют сущность -го. Легко видеть, что в результате он в любом случае станет рыцарем.

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

Пример. Покажем, что возможна ситуация, в которой пар друзей рыцарь-лжец ровно Обозначим рыцарей а лжецов — Пусть рыцарь дружит только со лжецом рыцарь — только со лжецом , рыцарь — только со лжецом (и при этом лжецы больше ни с кем не дружат). Рыцари пусть дружат только друг с другом, и лжецы — тоже только друг с другом. Тогда пар рыцарь-лжец ровно человек произносят фразу "Все мои друзья - лжецы а остальные человек произносят фразу "Все мои друзья – рыцари".

Фразу могли сказать все. Раскрасим доску в шахматную раскраску. На белые клетки поставим рыцарей, а на чёрные — лжецов. Тогда у каждого рыцаря соседи по стороне находятся в чёрных клетках, так что его соседи действительно лжецы. А у каждого лжеца все соседи находятся в белых клетках, поэтому он врёт про соседа-лжеца.

Ни один островитянин не мог назвать себя троллем. Поэтому утверждение Толи точно неверно. Значит, Толя тролль.

Предположим, что произнесенная фраза неверна. Но тогда сказать ее мог только тролль, и мы получаем противоречие, ведь тогда тролли все-таки есть. Значит, произнесенная фраза верна. Поэтом произнес ее эльф. Но так как фраза верна, то второй должен быть троллем. Итак, произнесший фразу эльф, а собеседник — тролль.

Фраза “Я тролль или ты эльф” может быть неверна только в одном случае: если ее произносящий не тролль, а его собеседник не эльф. Но в таком случае произносящий должен быть эльфом, а соврать он не может. Значит, произнесенная фраза верна, и сказавший ее эльф. Тогда часть фразы “Я тролль” неверна, поэтому должна быть верна фраза “ты эльф”. Таким образом, оба островитянина — эльфы.

Во-первых отметим, что все собравшиеся не могут быть троллями: тогда каждый из них сказал бы правду. Значит, среди них есть эльф. Рассмотрим одного из эльфов, вставших в круг, и назовем первым, остальных островитян также пронумеруем по часовой стрелке. Чтобы произнесенная первым фраза была верна, следующие четверо, то есть островитяне со по , тролли.

Далее, после второго островитянина следующие трое по часовой стрелке — тролли. Поэтому, чтобы высказывание второго островитянина было неверным, шестой островитянин должен быть эльфом. Тогда следующие четверо после шестого островитянина опять же тролли. Итого эльфами являются первый и шестой, а остальные — тролли. Нетрудно убедиться, что в этом случае все собравшиеся сделали высказывания согласно своему мировоззрению: эльфы сказали правду, а тролли солгали.

Рассмотрим первого жителя. Если бы он был эльфом, то фраза “Все мы тролли” была бы ложной, и получается, что эльф соврал, чего быть не может. Значит, первый житель тролль.

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

Далее отдельно разберем два случая.

Случай 1. Третий житель все-таки эльф. Тогда в компании два тролля, и мы уже обоих троллей знаем: это первый и второй жители. Поэтому четвертый житель эльф.

Случай 2. Третий житель тролль. Вернемся тогда к фразе первого жителя: “Все мы тролли.” Так как он сам тролль, то эта фраза неверна. Значит, среди них должен быть эльф, и им может быть только последний, четвертый житель. В этом случае мы тоже получили, что четвертый житель эльф.

Итак, вне зависимости от случая, четвертый житель — эльф.

Замечание. Обратите внимание, что оба случая возможны, то есть данная ситуация бывает ровно в двух случаях: когда первый и второй тролли, четвертый — эльф, а третий может быть как эльфом, так и троллем.

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

Заметим, что если два жителя ответили одно и то же, то они одного типа: либо оба эльфы, либо оба тролли. Так как на острове есть и эльфы, и тролли, то все эльфы сказали одно, а тролли — другое. Поэтому одно из утверждений верное, а другое — неверное. Значит, количество эльфов и количество троллей одной четности, поэтому общее количество жителей четно.

Рассмотрим рассадку аборигенов во второй день. Рядом с каждым эльфом сидят два тролля. Более того, ни с одним из этих троллей никакие другие эльфы рядом не сидят, иначе он скажет правду. Отсюда следует, что на каждого эльфа приходится не менее двух троллей, поэтому эльфов не больше трети от собравшихся, значит, не больше .

В первый же день никакие три тролля не могут сидеть подряд. Рассмотрим одного эльфа и любого его соседа. Всех остальных разобьем на тройки подряд сидящих. В каждой такой тройке сидит хотя бы один эльф. Значит, всего эльфов не меньше . Таким образом, во второй день эльфов было меньше, чем в первый. Поэтому заболел эльф.

Рассмотрим в круге эльфа, если такой, конечно, там есть. Тогда его правый сосед действительно эльф. Следующий справа — снова эльф, и так далее. В итоге мы получаем, что все сидящие в круге эльфы, и такой случай действительно подходит. Остался единственный вариант, когда эльфов нет вообще и все сидящие в круге — тролли. И такой вариант тоже подходит, так как тогда все тролли действительно солгут. Значит, возможны два варианта: все сидящие в круге эльфы и все сидящие в круге тролли. Поэтому эльфов могло быть или .

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

Заметим, что эти соседи говорят друг про друга, что их оппонент экзамен не сдаст. Поэтому оба сдать экзамен они не могут. Значит, один из них все-таки экзамен не сдал. Но тогда его оппонент верно сказал, что все, кроме, возможно, него самого и соседей экзамен не сдали. Таким образом, из двух соседей Флоренца ровно один экзамен сдаст. Поэтому всего сдавших экзамен двое.

Рассмотрим одного эльфа, если такой есть. По условию, рядом с ним стоит нечетное число эльфов. Всего у него два соседа, и единственное нечетное число эльфов, которое может рядом с ним стоять, — эльф. Значит, рядом с ним с одной стороны стоит эльф, а с другой — тролль. То же верно для каждого эльфа в кругу. Поэтому все эльфы стоят парами: один эльф стоять не может, так как тогда рядом с ним будет четное число эльфов, а именно , а если подряд стоят больше двух эльфов, то рядом с не крайними эльфами стоят эльфа, что опять же не является нечетным числом.

Теперь посмотрим на какую-то группу из двух эльфов и разберемся, сколько троллей может стоять после них. Один тролль там обязательно стоит, так как больше двух эльфов подряд, как было доказано выше, стоять не может. Рассмотрим этого тролля. Рядом с ним уже стоит один эльф. Если с другой стороны будет стоять тролль, то рядом с этим эльфом будет стоять ровно эльф, то есть нечетное число эльфов, и тогда тролль скажет правду. Поэтому с другой стороны стоит эльф. Значит, пары эльфов разделены группами по одному троллю. Тогда мы получаем единственную возможную расстановку: ЭЭТЭЭТЭЭТ…. Отметим, что так как общее число островитян в кругу делится на , то такая расстановка действительно возможна, получается групп по островитянина: два эльфа и тролль. В таком случае эльфов .

Вспомним, что все эти рассуждения проходили в предположении, что в круге есть хотя бы один эльф. Если предположение неверно, то в кругу стоят одни тролли. И такой случай также подходит: тогда каждый эльф стоит рядом с эльфов, а  — четное число. Значит, все тролли врут, и все сходится. В таком случае эльфов .

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

Единственный оставшийся без рассмотрения случай — когда эльфов нет вообще. Но тогда по кругу стоят одни лжецы, и такой вариант тоже подходит. В итоге получаем два ответа: или эльфов.

Заметим, что “Ты тролль” говорят только островитяне разного типа: эльф так скажет про тролля, а тролль про эльфа. Таким образом, эльфы и тролли в этом кругу чередуются. Поэтому эльфов ровно половина от общего числа, то есть .

Рассмотрим эльфа, если такой есть. Рядом с ним сидит нечетное число троллей. С другой стороны, у него только соседа, поэтому единственное нечетное число троллей, которое может сидеть рядом с ним, — тролль. Получается, что с одной стороны от эльфа сидит тролль, а с другой эльф. Рассмотрим эльфа. Рядом с ним уже сидит один эльф, и значит следующий его сосед — тролль. Получается, что эльфы сидят парами. Между парами эльфов сидит ровно один тролль, так как иначе крайний тролль сидел бы между эльфом и троллем, то есть говорил бы правду. Получаем рассадку ТЭЭТЭЭТЭЭТЭЭ…В таком случае мы получаем, что все сидящие за кругом разбиваются на десять троек ТЭЭ, поэтому эльфов .

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

Замечание. На самом деле так как соседей у каждого сидящего в круге всего двое, то утверждение “Среди моих соседей нечетное число троллей” значит в точности то же, что и “Среди моих соседей нечетное число эльфов”. А эту задачу мы разбирали на уроке, поэтому отнюдь не удивительно, что мы получили такой же ответ.

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

Заметим, что эти соседи говорят друг про друга, что они тролли. Поэтому оба быть эльфами они не могут. Значит, один из них все-таки тролль. Но тогда другой верно сказал, что все, кроме, возможно, него самого и соседей тролли. Таким образом, из двух соседей первого рассмотренного эльфа один эльф, а другой тролль. Поэтому всего эльфов двое.

Предположим, что мы нашли двух эльфов, стоящих подряд; докажем, что все стоящие в кругу эльфы. Действительно, рассмотрим этих эльфов и рассмотрим их соседа справа. Если бы тот был троллем, то его сосед-эльф солгал бы: рядом с ним стоят эльф и тролль, значит, соседей-троллей все-таки нечетное количество. Поэтому следующий за этой парой эльфов тоже эльф. Рассуждая так далее, получаем, что в кругу стоят одни эльфы, и этот случай подходит.

Остался случай, когда нет двух эльфов, стоящих подряд. Тогда по кругу сидят эльфы-одиночки, разделенные группами троллей. Посмотрим, сколько может быть троллей в таких группах. Если тролль всего один, то среди его соседей троллей, то есть четное число, и в таком случае тролль говорит правду. Если троллей больше двух, то тролли, стоящие не с краю, говорят правду, ведь у них тролля-соседа. Получается, что тролли стоят парами. Значит, расстановка такая: ЭТТЭТТЭТТ…, то есть десять троек, в каждой тройке один эльф и два тролля. В таком случае эльфов .

Итак, мы получили два ответа: или эльфов.