МАЛЫЙ МЕХМАТ МГУ

Кружок 5 класса

Занятие 19. На острове рыцарей и лжецов

Старик постоянно говорил, что всё вокруг — неправда. Правда, потом оказалось, что он лгал.

Дуглас Адамс «Автостопом по Галактике»

На этом занятии мы предпримем путешествие на остров, где живут только два племени: рыцари и лжецы. Рыцари всегда говорят правду, а лжецы — всегда лгут.

1.

Вы только что прибыли на остров и собираетесь спросить первого встречного аборигена, из какого он племени. Что он вам ответит?

Ответ Решение

Ответ. Абориген ответит, что он рыцарь.

Решение. Если встеченый абориген — рыцарь, он скажет правду, то есть что он рыцарь; если же он лжец, то скажет неправду, то есть опять-таки что он рыцарь.

2.

Не ограничившись одним ответом, вы опросили всех аборигенов, собравшихся в порту, и все они ответили: «Все остальные собравшиеся — лжецы». Сколько рыцарей собралось в порту?

Ответ Решение

Ответ. Один.

Решение. Если в порту нет ни одного рыцаря, то получается, что все говорят правду, но тогда они не могут быть лжецами. Если рыцарей больше одного, то каждый рыцарь лжёт, потому что кроме него самого есть ещё хотя бы 1 рыцарь. Значит, рыцарь один: в этом случае действительно все лжецы лгут, а единственный рыцарь говорит правду.

3.

Гуляя по городу, вы услышали интересный диалог. Один из аборигенов сказал другому: «По крайней мере один из нас — рыцарь». «Ты — лжец», — ответил ему второй. Кто из них кто?

Ответ Решение

Ответ. Первый — рыцарь, а второй — лжец.

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

4.

а)

Проголодавшись, вы зашли в трапезную. За круглым столом сидело девять аборигенов. При виде вас каждый из них тут же сказал: «Мои соседи из разных племён». Сколько рыцарей и сколько лжецов было за столом?

b)

А если за столом было семь аборигенов?

Ответ Решение

Ответ. а) Либо все лжецы, либо 3 лжеца и 6 рыцарей; б) все лжецы.

Решение. Может оказаться, что за столом сидят только лжецы: тогда рядом с каждым из них сидят два человека из одного племени, то есть все они лгут. Если же за столом есть хоть один рыцарь, то с одной стороны от него обязательно сидит рыцарь, а с другой — лжец. Рядом с этим лжецом должен сидеть ещё один рыцарь (так как он солгал, что его соседи из разных племен, а значит, они из одного племени). Значит, всех сидящих за столом можно разделить на тройки «лжец, рыцарь, рыцарь». Так как 9 на 3 делится, а 7 не делится, то в случае а) такая ситуация возможна (тогда за столом 3 лжеца и 6 рыцарей), а в случае б) такая ситуация невозможна.

5.

После обеда, вы вышли в сад, где группами стояли и разговаривали островитяне. Вы подошли к одной такой группке из островитян Антонио, Бена и Стива. На ваш вопрос кто они такие, Бен ответил: «Мы все лжецы», а Стив сказал: «Среди нас только один рыцарь». Сможете ли вы определить, кто из этих троих кто?

Ответ Решение

Ответ. Антонио и Бен — лжецы, Стив — рыцарь.

Решение. Бен не может быть рыцарем: рыцарь не сказал бы, что все они лжецы. Значит, Бен лжец. Тогда среди Антонио и Стива один или два рыцаря. Если Стив лжец, то среди них двое рыцарей, чего быть уже не может, так как Бен и Стив лжецы. Значит, Стив рыцарь; поскольку он говорит правду, то он и является единственным рыцарем.

6.

Подойдя к другой группке из островитян Остапа, Сидора и Прохора, вы спросили у Остапа: «Вы рыцарь или лжец?» Тот ответил, но так неразборчиво, что вы не смогли ничего понять, и пришлось переспрашивать у Сидора: «Что сказал Остап?» «Остап сказал, что он лжец», — ответил Сидор. «Не верьте Сидору! Он лжет!» — вмешался в разговор Прохор. Определите, кто из Сидора и Прохора рыцарь и кто лжец?

Ответ Решение

Ответ. Сидор — лжец, Прохор — рыцарь.

Решение. В задаче 1 мы выяснили, что на вопрос «Кто вы, рыцарь или лжец?» все отвечают «рыцарь». Значит, и Остап ответил «рыцарь». Таким образом, Сидор солгал, поэтому он лжец. А Прохор сказал, что Остап лжец; значит, он сказал правду, то есть он рыцарь.

7.

К третьей группе из четырёх аборигенов вы обратились с вопросом: «Сколько рыцарей среди вас?» На этот вопрос они дали такие ответы. Первый: «Все мы лжецы», второй: «Среди нас один лжец», третий: «Среди нас два лжеца», четвёртый: «Я ни разу не солгал и сейчас не лгу». Сможете ли вы определить, кем являлся четвёртый абориген?

Ответ Решение

Ответ. Рыцарем.

Решение. Первый не может быть рыцарем. (Если бы он был рыцарем, то говорил бы правду; но он говорит, что все лжецы, в том числе и он сам.) Значит первый — лжец. Если второй — рыцарь, то он говорит правду, и, поскольку первый — лжец, то второй, третий и четвертый — рыцари. Но слова третьего противоречат словам второго, значит, они не могут быть рыцарями одновременно. Поэтому второй — тоже лжец. Если третий — лжец, то четвёртый — рыцарь (если он тоже лжец, то первый сказал правду, что неверно). Если же третий — рыцарь, то лжецов двое. Нам известно, что первый и второй — лжецы, а значит, четвёртый и в этом случае — рыцарь.

8.

Выйдя на улицу, вы встретили на дороге троих аборигенов и спросили каждого: «Сколько рыцарей среди твоих спутников?» Первый ответил: «Ни одного», второй ответил: «Один». Что сказал третий?

Ответ Решение

Ответ. Один.

Решение. Если первый — рыцарь, то второй и третий — лжецы, но тогда второй сказал правду, чего быть не может. Значит, первый — лжец. Если второй — тоже лжец, то, поскольку он солгал, лжецов среди его спутников больше одного. Но все трое лжецами быть не могут (иначе первый сказал бы правду, а мы уже выяснили, что он лжец). Так что второй — рыцарь. Тогда третий — тоже рыцарь, так как второй сказал правду. Значит, и третий должен сказать правду. Первый — лжец, второй — рыцарь, значит, третий ответит «один».

9.

Вам стало интересно, сколько всего жителей на острове. Некоторые аборигены заявили, что на острове чётное число рыцарей, а остальные заявили, что на острове нечётное число лжецов. Так чётно или нечётно число жителей острова?

Ответ Решение

Ответ. Чётно.

Решение.

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

Пердположим сначала, что те, кто говорил, что рыцарей чётное число, — рыцари. Тогда рыцарей действительно чётное число. Если остальные — лжецы, то на острове на самом деле чётное число лжецов. Тогда общее число жителей острова чётно. Если же остальные — тоже рыцари, то лжецов должно быть нечётное количество. Но в этом случае получается, что все аборигены — рыцари, а лжецов на острове 0, то есть чётное число, поэтому такой вариант невозможен.

Теперь предположим, что те, кто говорили, что рыцарей чётное число, — лжецы, тогда рыцарей нечётное количество. Если остальные — рыцари, то лжецов нечётное количество, тогда общее число аборигенов чётно. Если же остальные — тоже лжецы, то рыцарей на острове нет, но их должно быть нечётное количество, поэтому и этот случай невозможен.

10.

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

Ответ Решение

Ответ. «Если бы Вы были из другого племени, то подтвердили бы Вы, что на острове не водятся волнистые попугайчики?»

Решение. «Если бы Вы были из другого племени, то подтвердили бы Вы, что на острове не водятся волнистые попугайчики?» Если встреченный вами абориген — рыцарь, и на острове водятся волнистые попугайчики, он ответит «Да» (ведь лжец не подтвердил бы, что на острове водятся попугайчики). Убедитесь самостоятельно, что если на острове водятся попугайчики, то и лжец на ваш вопрос ответит «Да». Проверьте также, что если на острове волнистых попугайчиков нет, то любой абориген (как рыцарь, так и лжец) ответит на ваш вопрос «Нет».

11.

Вы страшно надоели аборигенам своими докучливыми вопросами, и они поймали вас и решили съесть. Но они готовы дать вам выбрать вариант вашего приготовления: если вы скажете утверждение, и оно окажется правдой — вас зажарят с перцем, а если ложью — потушат под маринадом. Что вам надо сказать, чтобы вопреки всему избежать участи быть поданным к обеду?

Ответ Решение

Ответ. «Я буду потушен под маринадом».

Решение. «Я буду потушен под маринадом». Тогда если это правда, то вас должны потушить с перцем, но тогда вы солгали. Если же вы солгали, то вас должны потушить с маринадом, но тогда вы сказали правду. Значит, островитяне не смогут сделать ни того, ни другого.