Мартин Гарднер - Есть идея!

• Название: Есть идея!
• Автор: Мартин Гарднер
• Издательство: Мир
• Жанр: Прочая научная литература
• Год: 1982

Книга известного американского популяризатора науки Mapтина Гарднера, посвященная поиску удачных идей для решений задач из области комбинаторики, геометрии, логики, теории чисел и игр со словами.

Рассчитана на самый широкий круг читателей.

---

Если вам понравилась задача о шофере такси и болтливой даме, то мы можем предложить вам еще две задачи о такси.

Пассажир, которому нужно добраться до аэропорта Кеннеди, садится в такси у отеля «Уолдорф-Астория» в Нью-Йорке. Поскольку городские улицы забиты машинами и почти на каждом перекрестке возникает пробка, такси развивает среднюю скорость всего лишь 30 км/ч. Общее время в пути составляет 80 мин, и пассажир уплачивает по счетчику соответствующую сумму. В аэропорту в такси садится другой пассажир, которому по удивительному стечению обстоятельств также нужно добраться до отеля «Уолдорф-Астория». Водитель едет по тому же маршруту с той же средней скоростью, но на этот раз дорога занимает у него 1 ч 20 мин. Чем объяснить, что на дорогу туда и обратно уходит различное время?

Большинство людей не сразу сознает, что различие во времени на дорогу от гостиницы до аэропорта и от аэропорта до гостиницы лишь кажущееся: 80 мин по продолжительности ничем не отличаются от 1 ч 20 мин. Испытав эту незамысловатую задачу-шутку на своих знакомых, вы убедитесь, как часто попадаются в почти не замаскированную «ловушку».

А вот еще задача о такси того же толка.

Представьте себе, что вы водитель такси. Ваша машина окрашена в желтый и черный цвета, и вы ездите на ней 7 лет. Один стеклоочиститель у машины сломан, карбюратор барахлит. Бак вмещает 20 галлонов бензина, но сейчас наполнен лишь на три четверти. Сколько лет водителю такси?

Это задача — еще более «злая» шутка, чем предыдущая, хотя ее условия логически непротиворечивы. С самого начала в ней говорится, что вы водитель такси. Значит, и лет водителю столько же, сколько вам.

В костюмах одного цвета

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

Оказавшись во время танцев рядом с девушкой в зеленом, юноша в красном обратился к ней.

Фрэнк. Не правда ли, Мабель, забавно получается: ни у кого из нас цвет костюма не совпадает с цветом костюма партнера.

Можете ли вы с уверенностью сказать, в костюме какого цвета был юноша, танцевавший в паре с девушкой в красном?

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

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

Таким образом, девушка в красном могла танцевать только с юношей в зеленом.

Цвета против цветов

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

Прописные буквы слева означают цвета костюмов, в которые были одеты юноши: К — красный, 3 — зеленый, С — синий. Строчные буквы сверху означают цвета платьев, в которые были одеты девушки.

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

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

Поскольку нам уже известно, что девушка в синем танцевала с юношей в красном, то она не могла танцевать с партнером в зеленом. Следовательно, клетку Зс можно закрасить, после чего во втором ряду остается незакрашенной только одна клетка Зк. Значит, юноша в зеленом танцевал с девушкой в красном, и в клетке Зк можно поставить «птичку».

Но если девушка в красном танцевала с юношей в зеленом, то она не могла танцевать с юношей в синем, что позволяет нам закрасить клетку Ск. В ряду С остается только одна незакрашенная клетка Сз. Мы поставим в ней «птичку», означающую, что юноша в синем танцевал с девушкой в зеленом. Задача полностью решена.

А вот более трудная логическая задача по существу того же рода. Решить ее без матричного, или табличного, метода под силу лишь немногим.

Пол, Джон и Джордж — три звезды «рока». Один из них гитарист, другой ударник, третий пианист (разумеется, мы отнюдь не утверждаем, что Пол непременно играет на гитаре, Джон на ударных и Джордж на фортепьяно: Пол вполне может быть, например, пианистом, Джордж ударником и т. д.).

1. На запись грампластинки популярной «рок»-музыки ударник хотел пригласить гитариста, но того не оказалось в городе: он отбыл на гастроли вместе с пианистом.

2. Пианисту платят больше, чем ударнику,

3. Полу платят меньше, чем Джону.

4. Джордж никогда не слышал о Джоне.

На каком инструменте играет каждый из трех музыкантов?

Удастся ли вам, построив матрицу 3×3 решить задачу по аналогии с предыдущей?

Получив правильное решение, вы узнаете, что Пол гитарист, Джон ударник, а Джордж пианист.

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

А вот задача более сложная, чем предыдущие. Она познакомит вас с одним из наиболее важных двухместных отношений формальной логики — так называемой импликацией, или утверждением «Если…, то…».

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

1. Мира не занималась маникюром и не читала.

2. Мод не прихорашивалась перед зеркалом и не занималась маникюром.

3. Если Мира не прихорашивалась перед зеркалом, то Мона не занималась маникюром.

4. Мэри не читала и не занималась маникюром.

5. Мона не читала и не прихорашивалась.

Что делала каждая девушка?

Начертить матрицу 4×4 для четырех имен и занятий не составит особого труда. Обратите внимание на то, что каждое из утверждений 1, 2, 4 и 5 позволяет закрасить 2 клетки (и исключить из рассмотрения соответствующие комбинации имен и занятий).

Утверждение 3 — импликация. В нем говорится, что если Мира не прихорашивалась перед зеркалом, то Мона не занималась маникюром. Пусть A означает посылку импликации (утверждение, стоящее после «если»), а B — ее заключение (утверждение, стоящее после «то»). Двухместное отношение «если A, то B» ложно, когда A истинно, а B ложно, но ничего не говорит нам о значениях истинности утверждения B в тех случаях, когда A ложно.

Следовательно, утверждение 3 допускает 3 различные комбинации значений истинности.

1. Мира не прихорашивалась перед зеркалом, и Мона не занималась маникюром.

2. Мира прихорашивалась перед зеркалом, и Мона не занималась маникюром.

3. Мира прихорашивалась перед зеркалом, и Мона занималась маникюром.

После того как вы исключите 8 комбинаций (заштриховав или закрасив в таблице 8 клеток), запрещаемых утверждениями 1, 2, 4 и 5, останется проверить каждую из 3 пар простых высказываний, содержащихся в утверждении 3. Две пары приводят к противоречию: приняв их, вы получили бы, что две девушки занимались одним и тем же. Лишь пара высказываний «Мира прихорашивалась перед зеркалом, и Мона занималась маникюром» не противоречит информации, содержащейся в остальных утверждениях. Итак, окончательное решение имеет вид:

Мира прихорашивалась перед зеркалом.

Мод читала.

Мэри расчесывала волосы.

Мона занималась маникюром.

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