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

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

Занятие 11. Средневековая логика

Часть первая. Кто говорит правду?

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

1.

Сидят леди Джейн и леди Нинэт. «Я — Джейн» — сказала первая. «Я — Нинэт», — сказала вторая. Хотя бы одна из них врет. Кто Джейн, а кто — Нинэт?

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

Ответ. Первая — Нинэт, вторая — Джейн.

Решение. Если одна из леди врет, то она не та, за кого себя выдает. Значит, это же относится и ко второй. Значит, каждая леди назвала вместо своего имени имя соседки.

2.

Леди Кэт сказала: «Я самая прекрасная. Мэри не самая прекрасная». Джейн сказала: «Кэт не самая прекрасная. Я самая прекрасная». А Мэри просто сказала: «Я самая прекрасная». Белый рыцарь предположил, что все утверждения прекраснейшей из девушек истинны, а все утверждения остальных дам ложны. Исходя из этого, определите прекраснейшую из дам.

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

Ответ. Кэт.

Решение. Предположим, что Джейн самая прекрасная. Значит, она говорит правду, а Кэт и Мэри лгут. Но Кэт говорит, что Мэри не самая прекрасная, а Мэри утверждает обратное. Поскольку обе говорят неправду, то они противоречат друг другу. Значит, этот случай невозможен. Если предположить, что Мэри самая прекрасная, то противоречить друг другу будут Джейн и Кэт. Этот случай тоже невозможен. Остается убедиться, что если Кэт говорит правду, то никаких противоречий не возникает, и она действительно самая прекрасная.

3.

После битвы с драконом трех рыцарей спросили об исходе битвы. Вот что они ответили. Белый рыцарь: «Дракона убил Черный рыцарь». Красный рыцарь: «Дракона убил Белый рыцарь». Черный рыцарь: «Дракона убил я». Кто убил дракона, если только один из рыцарей сказал правду?

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

Ответ. Белый рыцарь.

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

4.

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

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

Ответ. Леди Джейн.

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

5.

Четверо рыцарей обсуждали количество камней драгоценных камней в короне короля. Сэр Джон сказал: «Это число 9». Сэр Эндрю сказал: «Это простое число». Леди Нинэт: «Это четное число». А леди Джейн сказала, что это число 15. Назовите это число, если правду сказала только одна леди и только один рыцарь.

Примечание: в условиях задач, выдававшихся на занятии, вопрос задачи был сформулирован иначе: «Назовите это число, если и леди, и рыцари ошиблись ровно по одному разу.» Этот вопрос следует понимать так, как написано выше. И конечно же, имелось в виду, что, по словам леди Джейн, это число 15, а не -15 (в условии была допущена опечатка).

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

Ответ. Два драгоценных камня.

Решение. Если сэр Джон был прав, то искомое число 9. Но тогда и леди Нинэт, и леди Джейн неправы. Значит, прав был сэр эндрю, сказав, что число простое. Но 15 — не простое число, значит, леди Джейн была неправа. Права была леди Нинэт, утверждая, что число четное. Но существует только одно число, являющееся одновременно простым и четным — это число 2. Именно столько драгоценных камней и было в короне короля.

6.

Один из пяти рыцарей победил на турнире. И они расказывают о турнире леди Марии. Сэр Ланселот сказал: «Это Сэр Гавейн или Сэр Джон». Сэр Гавейн сказал: «Победил не я и не Сэр Джероми». Сэр Джон сказал: «Вы оба шутите!». Сэр Эрик сказал: «Нет, один из них сказал правду, а другой нет». Сэр Джероми сказал: «Нет, Сэр Эрик, ты неправ». Про троих рыцарей (но неизвестно, про кого именно) леди Мария знает, что они никогда не лгут. Кто победил на турнире?

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

Ответ. Сэр Джон.

Решение.

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

Теперь нужно определить еще одного рыцаря, который не всегда говорит правду. Слова Эрика противоречат словам Джероми, значит, одновременно быть абсолютно правдивыми они не могут. То есть второй не правдивый рыцарь — один из них, а Ланселот и Гавейн всегда говорят правду. Поскольку кому-то из последних Эрик противоречит, он не может быть правдивым. Значит, правдивые рыцари — Гавейн, Ланселот и Джероми.

Осталось разобраться, что же все-таки произошло на турнире. Тот факт, что Джероми всегда говорит правду, означает, что неправ был Эрик. То есть либо и Гавейн и Ланселот были правы, либо оба они были неправы. Но мы знаем, что они всегда говорят правду. По словам Ланселота, победил сэр Гавейн или сэр Джон. Но сам Гавейн отрицает свою победу. Значит, победил сэр Джон.

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

Часть вторая. Все писать в таблицу

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

Бывает, что каждый персонаж обладает не одним, а двумя и более признаками. В этом случае возможны разные подходы. Один из них заключается в том, чтобы составить большую таблицу, включив в нее все признаки, и постепенно ее заполнять. Скорее всего, для этого придется пройтись по всем условиям задачи несколько раз, все время делая новые выводы с учетом уже полученных. Таким способом решены, например, задачи №9 и №11.

Одна из самых известных задач такого рода — загадка Эйнштейна, каждый персонаж которой обладает аж пятью признаками. Существует несколько вариантов условия этой задачи; один из них можно найти, например, на сайте ru.wikipedia.org. Там же приведено и решение, но прежде чем его читать, попробуйте ее решить самостоятельно!

7.

Встретились три рыцаря: Красный, Белый и Черный. У них были белый, красный и черный щиты. Рыцарь с белым щитом сказал Черному рыцарю: «Интересно, что цвет щита на каждого из нас не соответствует имени». Какой цвет щита у каждого?

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

Ответ. У Красного рыцаря белый щит, у Черного рыцаря красный щит и у Белого рыцаря — черный щит.

Решение. Составим таблицу: по строкам будем писать имена рыцарей, а по столбцам — цвета их щитов.

	Красный щит	Белый щит	Черный щит
Красный рыцарь
Белый рыцарь
Черный рыцарь

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

	Красный щит	Белый щит	Черный щит
Красный рыцарь	−
Белый рыцарь		−
Черный рыцарь		−	−

В нижней строке уже есть два минуса, значит, на свободном месте ставим плюс и добавляем недостающий минус в столбце «Красный щит». Во второй строке тоже остается одно свободное место, туда ставим плюс. Третий плюс теперь ставится очевидным образом. Заполненная таблица выглядит так:

	Красный щит	Белый щит	Черный щит
Красный рыцарь	−	+	−
Белый рыцарь	−	−	+
Черный рыцарь	+	−	−

8.

Черный, Красный и Белый рыцари каждое утро прогуливаются по королевским владениям. Один из них ездит верхом, другой — на колеснице, а третий прогуливается пешком. Однажды утром Белый рыцарь встретил своего друга, прогуливающегося на лошади. Когда мимо них проезжала колесница, третий рыцарь (ехавший на колеснице) крикнул: «Господин Черный рыцарь, Вас в замке ожедает прекрасная дама!». Кто из рыцарей на чем любит прогуливаться утром?

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

Ответ. Черный рыцарь прогуливается верхом, Белый — пешком, а Красный — на колеснице.

Решение. Решение этой задачи аналогично решению задачи 7. С учетом всех условий задачи таблица принимает таой вид:

	Пешком	Верхом	На колеснице
Красный рыцарь
Белый рыцарь		−	−
Черный рыцарь			−

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

	Пешком	Верхом	На колеснице
Красный рыцарь	−	−	+
Белый рыцарь	+	−	−
Черный рыцарь	−	+	−

9.

На турнире присутствовали три сестры короля: леди Мэри, леди Катерина и леди Нинэт. Они были в белом, красном и золотом платьях. Та, что была в белом не любит лошадей и меньше всех ростом. Нинэт и Мэри каждое воскресенье катаются верхом, причем Нинэт ростом выше той, что была в красном. Скажите, как была одета каждая из дам.

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

Ответ. Мэри была в красном платья, Нинэт — в золотом, а Катерина — в белом.

Решение. Составим таблицу таким образом: по строкам запишем сестер короля, в первых трех столбцах таблицы будем указывать цвет платья, а в следующих трех — рост.

	Красное платье	Белое платье	Золотое платье		Самая высокая	Cреднего роста	Самая низкая
Леди Мэри
Леди Нинэт
Леди Катерина

Сразу заметим следующее: так как Нинэт и Мэри регулярно катаются на лошадях, то не любит лошадей Катерина; значит, она была в белом платье и ниже всех ростом. Укажем это в таблице. При этом в столбцах, где уже есть один плюс, на свободные места расставим минусы. В строках можно делать то же самое, но не во всей строке сразу, а только в каждой половинке по отдельности (отдельно про цвет платья, отдельно про рост). Получится вот что:

	Красное платье	Белое платье	Золотое платье		Самая высокая	Среднего роста	Самая низкая
Леди Мэри		−					−
Леди Нинэт		−					−
Леди Катерина	−	+	−		−	−	+

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

	Красное платье	Белое платье	Золотое платье		Самая высокая	Среднего роста	Самая низкая
Леди Мэри		−					−
Леди Нинэт	−	−	+		+	−	−
Леди Катерина	−	+	−		−	−	+

Оставшиеся ячейки таблицы заполняем по уже знакомым нам правилам:

	Красное платье	Белое платье	Золотое платье		Самая высокая	Среднего роста	Самая низкая
Леди Мэри	+	−	−		−	+	−
Леди Нинэт	−	−	+		+	−	−
Леди Катерина	−	+	−		−	−	+

10.

В свите королевы 5 фрейлин: леди Мэри, леди Нинэт, леди Аннет, леди Катерина и леди Джейн. У каждой из них есть домашнее животное: кошка, собака, горностай, соловей и кролик. Королева помнит, что:

1. Леди Нинэт и Леди Катерина не любя кошек.
2. Леди Мэри и Леди Катерина думают завести себе собаку.
3. Леди Нинэт и Леди Джейн имеют покои на одном этаже с владелецей горностая.
4. Леди Аннет иногда прогуливается по утрам вместе с Леди Нинэт или с владелицей кролика.
5. Леди Мэри и Леди Нинэт в свободное время любят сплетничать с владелицей соловья.
6. Леди Катерина, леди Аннет и владелица кролика любят вышивать.
7. Владелица горностая вышиванием не увлекается.

Королева поняла, у какой из ее фрейлин какой любимец. А вы поняли?

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

Ответ. У Мэри горностай, у Нинэт Собака, у Аннет соловей, у Катерины кошка, у Джейн кролик.

Решение. Решение этой задачи аналогично решению задач 7 и 8. С учетом всех условий таблица примет такой вид (проверьте!):

	Кошка	Собака	Горностай	Соловей	Кролик
Леди Мэри		−		−
Леди Нинэт	−		−	−	−
Леди Аннет	−		−		−
Леди Катерина		−	−		−
Леди Джейн			−

В столбце «Горностай» осталось одно свободное место. Туда мы поставим плюс, а на оставшиеся свободные места в строке «Мэри» — минусы. То же самое проделаем со строкой «Джейн» и столбцом «Кролик»:

	Кошка	Собака	Горностай	Соловей	Кролик
Леди Мэри	−	−	+	−	−
Леди Нинэт	−		−	−	−
Леди Аннет	−		−		−
Леди Катерина		−	−		−
Леди Джейн	−	−	−	−	+

Становится ясно, что у Катерины кошка:

	Кошка	Собака	Горностай	Соловей	Кролик
Леди Мэри	−	−	+	−	−
Леди Нинэт	−		−	−	−
Леди Аннет	−		−		−
Леди Катерина	+	−	−	−	−
Леди Джейн	−	−	−	−	+

Наконец, получаем, что у леди Аннет — соловей, а у леди Нинэт — собака.

	Кошка	Собака	Горностай	Соловей	Кролик
Леди Мэри	−	−	+	−	−
Леди Нинэт	−	+	−	−	−
Леди Аннет	−	−	−	+	−
Леди Катерина	+	−	−	−	−
Леди Джейн	−	−	−	−	+

11.

Вчера леди Джейн, леди Мэри, леди Лилиан, леди Аннет, сэр Эрик, сэр Чарльз, сэр Джон, сэр Гавейн развлекались. Причем каждый из рыцарей пригласил с собой даму. Известно, что:

1. Сэр Джон был на балу.
2. Сэр Гавейн провёл всё время с леди Лилиан.
3. Сэр Эрик так и не увиделся с леди Аннет.
4. Леди Мэри побывала в замке короля Лира.
5. Леди Аннет каталась на лошади.
6. Кто-то из них поситил театр.

Кто с кем был и где?

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

Ответ. Джон и Джейн были на балу, Гавейн и Лилиан посетили театр, Эрик и Мэри были в замке, Чарльз и Аннет катались на лошадях.

Решение.

Как и для решения задачи №9, построим двойную таблицу. По строкам будем писать имена рыцарей, в первых четырех столбцах — имена дам, а в следующих четырех столбцах — места, которые они посещали. Правда, мы не сможем сразу же отразить все условия задачи в таблице, поэтому придется их прочитать несколько раз.

Начнем заполнять таблицу с учетом первых трех условий:

	Джейн	Мэри	Лилиан	Аннет		Бал	Замок	Лошади	Театр
Джон			-			+	-	-	-
Гавейн	-	-	+	-		-
Эрик			-	-		-
Чарльз			-			-

Теперь используем условие 5. Леди Аннет могла проводить время только с сэром Джоном или с сэром Чарльзом. Но она каталась на лошади, а сэр Джон — нет. Значит, леди Аннет проводила время с сэром Чарльзом, который, соответственно, тоже катался на лошади:

	Джейн	Мэри	Лилиан	Аннет		Бал	Замок	Лошади	Театр
Джон			-	-		+	-	-	-
Гавейн	-	-	+	-		-		-
Эрик			-	-		-		-
Чарльз	-	-	-	+		-	-	+	-

Теперь вернемся к условию 4 и будем рассуждать аналогично. Леди Мэри могла проводить время с сэром Джоном или сэром Эриком. Но она была в замке, а сэр Джон — нет. Значит, Мэри могла проводить время только с сэром Эриком, который, соответственно, был в замке:

	Джейн	Мэри	Лилиан	Аннет		Бал	Замок	Лошади	Театр
Джон		-	-	-		+	-	-	-
Гавейн	-	-	+	-		-	-	-
Эрик	-	+	-	-		-	+	-	-
Чарльз	-	-	-	+		-	-	+	-

Оставшиеся две ячейки заполняются очевидным образом:

	Джейн	Мэри	Лилиан	Аннет		Бал	Замок	Лошади	Театр
Джон	+	-	-	-		+	-	-	-
Гавейн	-	-	+	-		-	-	-	+
Эрик	-	+	-	-		-	+	-	-
Чарльз	-	-	-	+		-	-	+	-