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

Покажем, что могло случиться так, что Станислав установил наличие не менее чем лжецов. Пусть человек ответят “”, и человек ответят “” (такая ситуация гипотетически возможна, например, если все жители попарно дружат, и при этом первые лжецы, а последние — рыцари). Очевидно, не может быть так, что и среди первой группы людей есть рыцарь, и среди второй. Поэтому Станислав может с уверенностью утверждать, что лжецов не менее

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

Пусть абориген, который сказал фразу "Я лжец или ты рыцарь" это абориген а абориген, которому сказали эту фразу, это абориген

Предположим, что абориген — лжец. Тогда утверждение "Я лжец или ты рыцарь"не верно. Построим отрацание к этому утверждению и получим: "Я рыцарь и ты лжец". То есть абориген — рыцарь, что противоречит нашему предположению.

Получается, абориген — рыцарь. Отсюда фраза "Я лжец или ты рыцарь"правдива, то есть верно либо если он лжец, либо если абореген рыцарь. Первое утверждение не верно, значит, верно второе, и абориген — рыцарь.

Итак, по этой фразе мы можем определить, что оба аборигена рыцари.

Заметим, что все островитяне не могут быть лжецами, потому что иначе они все говорили бы правду. Тогда поставим одного рыцаря в начало круга и присвоим ему номер Чтобы он сказал правду, следующие островитяне будут лжецами с номерами со по Теперь, чтобы островитянин под номером солгал, нужно поставить -ым рыцаря, так как следующие после -го являются лжецами. Так как -ой — рыцарь, то следующие островитянина будут лжецами. Итого в кругу будут стоять рыцаря.

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

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

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

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

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

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

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

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

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

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

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

Один островитянин может заявить другому “Ты тролль!” в том и только в том случае, когда они разного типа. Поэтому один из них эльф, а другой — тролль. Тогда фраза “По крайней мере один из нас эльф” является верной. Значит, именно первый житель эльф, а второй — тролль.

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

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

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

Рыцарь говорит правду, поэтому его соседи — рыцарь и лжец. Лжец говорит ложь, поэтому его соседи либо оба лжецы, либо оба рыцари. Если бы у какого-то лжеца соседями были лжецы, у этих соседей-лжецов тоже должны были бы быть соседи лжецы, и так далее, поэтому все в круге были бы лжецами, что по условию не так. Тогда у лжецов соседи обязательно рыцари. В таком случае, нетрудно заметить, что порядок аборигенов такой: РРЛРРЛРРЛРРЛ…Всего их было , поэтому рыцарей две трети от , т.е. .

Рыцарь на этот вопрос ответит «нет». Лжец ответит «да», поэтому лжецов перед нами нет. Конформист может дать ответ «нет» только если стоит рядом с лжецом. Но лжецов перед нами нет, поэтому конформист может отвечать только «да». Раз никто не сказал «да», то и конформистов перед нами нет. Значит, перед нами стоят три рыцаря.

Если рыцарей нет, то все говорящие врут, так как не является делителем какого-либо натурального числа.

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

Индукция по количеству городов:

База для одного города: сделаем лжеца мэром города, тогда он ответит удовлетворительно, потому что у него вообще нет соседей.

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

Рассмотрим любую четвёрку подряд идущих людей. Если бы в ней было хотя бы 3 рыцаря, то самый первый из рыцарей точно сказал бы неправду, что невозможно. Если бы в ней было хотя бы 3 лжеца, то самый первый из лжецов точно сказал бы правду, что тоже невозможно. Значит, в каждой четвёрке подряд идущих людей ровно 2 рыцаря и ровно 2 лжеца. Разбив всех людей на 15 таких четвёрок, получаем, что рыщарей .