ЗАНИМАТЕЛЬНАЯ ЛОГИКА

Слова Шерлока Холмса: «Сколько раз я говорил вам, отбросьте все невозможное, тогда то, что останется, и будет ответом, каким бы невероятным он ни казался», — могли бы послужить эпиграфом к этой главе.

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

Чаще всего встречается тип задачи, который любители головоломок иногда называют «задачей о Смите — Джонсе — Робинсоне» (по аналогии со старой головоломкой, придуманной Г. Дьюдени).

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

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

В дальнейшем каждого пассажира мы будем почтительно называть «мистер» (м-р).

2. М-р Робинсон живет в Лос-Анджелесе.

3. Кондуктор живет в Омахе.

4. М-р Джонс давно позабыл всю алгебру, которой его учили в колледже.

5. Пассажир — однофамилец кондуктора живет в Чикаго.

6. Кондуктор и один из пассажиров, известный специалист по математической физике, ходят в одну церковь.

7. Смит всегда выигрывает у кочегара, когда им случается встречаться за партией в бильярд.

Как фамилия машиниста?

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

Рис. 139 Две таблицы к задаче о Смите, Джонсе и Робинсоне.

В каждую клетку впишем 1, если соответствующая комбинация допустима, или 0, если комбинация противоречит условиям задачи. Посмотрим, как это делается. Условие 7, очевидно, исключает возможность того, что Смит кочегар, поэтому в клетку, стоящую в правом верхнем углу левой таблицы, мы вписываем 0. Условие 2 сообщает нам, что Робинсон живет в Лос-Анджелесе, поэтому в левый нижний угол таблицы мы вписываем 1, а во все остальные клетки нижней строки и левого столбца — 0, чтобы показать, что м-р Робинсон не живет в Омахе или в Чикаго, а м-р Смит и м-р Джонс не живут в Лос-Анджелесе.

Теперь нам придется немного подумать. Из условий 3 и 6 известно, что специалист по математической физике живет в Омахе, но мы не знаем его фамилии. Он не может быть ни м-ром Робинсоном, ни м-ром Джонсом (ведь тот забыл даже элементарную алгебру).

Следовательно, им должен быть м-р Смит. Это обстоятельство мы отметим, поставив 1 в среднюю клетку верхней строки правой таблицы и 0 — в остальные клетки той же строки и пустые клетки среднего столбца. Третью единицу можно вписать теперь только в одну клетку: это доказывает, что м-р Джонс живет в Чикаго. Из условия 5 мы узнаем, что кондуктор тоже носит фамилию Джонс, и вписываем 1 в центральную клетку левой таблицы и 0 —во все остальные клетки средней строки и среднего столбца. После этого наши таблицы приобретают вид, показанный на рис. 140.

Рис. 140 Табл ицы, изображенные на рис. 139, после предварительного заполнения.

Теперь уже нетрудно продолжить рассуждения, приводящие к окончательному ответу. В столбце с надписью «Кочегар» единицу можно поставить только в нижней клетке. Отсюда сразу следует, что в левом нижнем углу должен стоять 0. Пустой остается лишь клетка в левом верхнем углу таблицы, куда можно поставить только 1. Итак, фамилия машиниста Смит.

Чрезвычайно сложные и хитроумные задачи такого рода любил изобретать Льюис Кэрролл. Декан математического факультета Дортмутского колледжа Джон Дж. Кемени запрограммировал одну из чудовищных (с 13 переменными и 12 условиями, из которых следует, что «ни один судья не нюхает табак») кэрролловских задач для компьютера IBM-704. Машина справилась с решением примерно за 4 минуты, хотя распечатка полной «таблицы истинности» задачи (таблицы, показывающей, истинны или ложны возможные комбинации значений истинности переменных задачи) заняла бы 13 часов!

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

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

2. Каждый муж доводился братом одной из жен, а каждая жена была сестрой одного из мужей, то есть среди присутствующих можно было указать три родственные пары «брат с сестрой».

3. Элен ровно на 26 недель старше своего мужа, который родился в августе.

4. Сестра м-ра Уайта замужем за свояком брата Элен и вышла за него замуж в день своего рождения, в январе.

5. Маргарет Уайт ростом ниже Уилльяма Блейка.

6. Сестра Артура красивее, чем Беатрис.

7. Джону исполнилось 50 лет.

Как зовут миссис Браун?

!!! Ещё одна задача – РЕШАЕМ!!!

Соревнования по плаванию были в самом разгаре, когда стало ясно, что первые четыре места займут мальчики из пятерки лидеров. Их имена: Валерик, Коля, Миша, Игорь, Эдик; фамилии: Симаков, Чигрин, Зимин, Копылов, Блинов. Нашлись знатоки, которые предсказали, что первое место займет Копылов, второе — Валерик, третье — Чигрин, четвертое — Эдик. Но, как это часто бывает, знатоки попали впросак — ни один из ребят не занял того места, которое ему предсказали. На самом деле первое место завоевал Миша, второе — Симаков, третье — Коля, четвертое — Блинов, а Чигрин не попал в четверку сильнейших. Назовите имя и фамилию каждого из лидеров.

Поиск по сайту: