. В комнате собрались три человека. Каждый из них либо рыцарь, который всегда говорит правду, либо лжец, который всегда лжёт, либо хитрец, который может и го- ворить правду и лгать по своему желанию. Один из собравшихся сказал: «Среди нас есть лжец». Другой сказал: «Среди любых двух из нас есть лжец». Третий сказал: «Все мы — лжецы». Докажите, что среди собравшихся есть хитрец

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

Выдвинем предположение

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

• первый сказал: «среди нас есть лжец»;
• второй сказал: «среди любых двух из нас есть лжец»;
• третий сказал: «все мы — лжецы».

Проанализируем эти высказывания.

Анализ высказываний

1. Третий солгал точно, иначе получилось бы , что лжец говорит правду. Третий - лжец. Тогда первый сказал правду и он рыцарь. Осталось невыясненным, кто тогда второй.
2. Допустим, что второй солгал. Тогда он лжец, и всего среди собравшихся два лжеца: второй и третий. Но тогда получается, что из любых двух собравшихся есть один лжец, и получается, что второй сказал правду, то есть лжец сказал правду. Получили противоречие.
3. Допустим, что второй сказал правду. Тогда среди собравшихся два рыцаря: первый и второй. Но в таком случае получается, что среди двоих — первого и второго — нет лжеца, и , что второй солгал. Опять противоречие.

Мы получили противоречие в высказываниях. Значит, наше предположение, что среди собравшихся нет хитрецов неверно, и они обязательно есть.

Начнем с третьего утверждения "все мы лжецы". Если оно истинно, то его автор говорит правду, а значит является хитрецом. Если же утверждение "все мы лжецы" ложно, то его автор либо лжец, либо хитрец. Рассмотрим ситуацию, когда "все мы лжецы" ложно, а автор лжец (поскольку если он хитрец доказывать больше ничего не нужно). В этом случае выражение "среди нас есть лжец" правдиво. Значит, первый из собравшихся рыцарь или хитрец (если хитрец доказывать дальше ничего не нужно). Допустим, он рыцарь. Тогда утверждение второго собравшегося "среди любых двух из нас есть лжец" относительно себя и рыцаря будет правдивым только если он сам лжец. Но лжец всегда говорит неправду, поэтому это утверждение должно быть ложным. Также он не может быть и рыцарем, поскольку тогда выражение "среди любых двух из нас есть лжец" относительно него и первого будет ложным. В этом случае второй находящийся в комнате может быть только хитрецом. Один из них должен быть хитрецом: либо третий, либо первый, либо второй.