Текст книги "Есть идея!"
Автор книги: Мартин Гарднер
сообщить о нарушении
Текущая страница: 12 (всего у книги 17 страниц)
В кресле у парикмахера
Парикмахера Билла вряд ли кто-нибудь мог назвать молчуном. Едва Джон уселся в кресло, как Билл принялся болтать без умолку.
Билл. Должно быть, вы не здешний, сэр? Люблю стричь нездешних!
Билл. По мне, так лучше подстричь двух нездешних, чем одного здешнего!
Джон. Почему?
Билл. Потому, что за две стрижки я заработаю вдвое больше, чем за одну стрижку!
Джон. Ловко вы меня поймали! Попробую расквитаться с вами. Дней 10 назад баскетбольная команда нашего колледжа выиграла встречу со счетом 76 : 40, хотя ни один баскетболист не забросил ни одного мяча.
Как вы это объясните?
Когда Билл, перебрав несколько вариантов ответа, признал себя побежденным, Джон все объяснил.
Джон. В баскетбольной команде нашего колледжа нет ни одного баскетболиста. В ней одни баскетболистки: наша команда женская.
Удивительные разгадки
Все задачи в этом разделе носят шуточный характер и основаны на неоднозначности языка. А вот еще 8 задач «с подвохом».
1. Миллиардер Говард Юз, известный своими эксцентрическими выходками, назначил приз в полмиллиона долларов тому из гонщиков, чья машина придет к финишу последней. В состязании вызвались участвовать 10 гонщиков, но необычные условия смущали даже признанных ассов трека.
– Как нам вести гонку? – спросил один из них. – Каждый из нас захочет выиграть, мы будем ехать все медленнее и медленнее, и такая, с позволения сказать, гонка никогда не кончится!
Вдруг один из гонщиков воскликнул:
– Я знаю, как провести гонку!
Что он придумал?
2. Можете ли вы сделать так, чтобы обыкновенная спичка горела под водой?
3. Преступник отправился с женой в кинотеатр, где шел вестерн с драками, лихими погонями и оглушительной пальбой. Улучив момент, когда на экране завязалась такая перестрелка, что у зрителей лопались барабанные перепонки, он выстрелом в голову убил свою жену. Затем он вместе с трупом жены выбрался из кинотеатра, причем его никто не остановил. Как ему удалось это сделать?
4. Профессор Квиббл утверждает, что может поставить бутылку в центре комнаты и вползти в нее. Правда ли это?
5. Знаменитый предсказатель Урия Фуллер берется с уверенностью предсказать счет любого баскетбольного матча до того, как тот начнется. В чем секрет этих безошибочных предсказаний?
6. Житель небольшого городка за сравнительно короткий срок зарегистрировал брак более 20 раз. Каждый раз в брак вступала другая женщина. Тем не менее житель, о котором идет речь, не развелся ни с одной из 20 с лишним женщин и не стал многоженцем. Как вы это объясняете?
7. «Эта редкая птица, – заверил покупательницу продавец зоомагазина, – повторяет каждое слово, которое услышит». Через неделю разгневанная покупательница вернула птицу в магазин, заявив, что та не произнесла ни слова. Тем не менее продавец не лгал. Объясните, как это может быть?
8. Наполовину пустая бутылка заткнута пробкой. Можете ли вы опорожнить бутылку, не разбивая ее и не вытаскивая пробку?
Ответы на все вопросы приведены в конце книги.
Убийство в Солнечной долине
В тот день, когда Джон приехал в Лас-Вегас, утренние выпуски газет поместили на первых полосах сообщение о профессиональном игроке, подвизавшемся в казино Лас-Вегаса, и – его жене. Супруги отправились в горы покататься на лыжах…
…и жена лала жертвой несчастного случая. Во время катания она сорвалась в пропасть. Единственным свидетелем ее гибели был муж.
Узнав из газет о несчастном случае, клерк из туристского агентства в Лас-Вегасе позвонил в полицейское управление штата Айдахо. Игрок был арестован по подозрению в убийстве своей жены.
Репортерам местных газет клерк поведал удивительную историю.
Клерк. Я не знаком ни с игроком, ни с его женой и не подозревал о злом умысле, пока не прочитал в газетах о несчастном случае в горах.
Почему клерк счел необходимым позвонить в полицию?
Клерк вспомнил, что игрок купил себе билет до Солнечной долины туда и обратно, а жене только туда.
Билет в один конец
Сумеете ли вы разгадать еще две загадочные истории? Как и в нашумевшей истории об убийстве в Солнечной долине, их тайну невозможно раскрыть, если придерживаться определенного алгоритма или действовать по какому-то заранее намеченному плану, в то время как удачная догадка быстро приводит к ответу.
1. По автостраде, ведущей к Сан-Франциско, мчалась автомашина. За рулем был отец, а рядом с ним восседал малолетний сынишка. Чтобы избежать столкновения с неожиданно затормозившей машиной, которая шла впереди, отец резко свернул в сторону, машина потеряла управление и врезалась в ограждение. Отец не пострадал, а у малыша оказалась сломана нога. Скорая помощь доставила их обоих в ближайшую больницу. Когда мальчика ввезли на каталке в операционную, дежурный хирург побледнел и воскликнул:
– Я не смогу оперировать этого мальчика! Ведь это мой сын!
Как вы это объясните?
2. Следующая история заимствована нами из сборника задач-головоломок Дж. Гамова и М. Стерна. Действие происходит во время второй мировой войны в оккупированном немцами Париже. В гостиничном лифте поднимаются четверо: нацистский офицер в форме, француз, сражающийся в одной из групп Сопротивления, молодая девушка и дама преклонного возраста. Все четверо не знакомы друг с другом.
Внезапно выключают электроэнергию. Лифт останавливается, и кабина погружается в кромешную тьму. В наступившей тишине раздается звук поцелуя и вслед за ним звонкая пощечина. Через секунду вспыхивает свет. У нацистского офицера под глазом красуется внушительный синяк, которого раньше не было.
Престарелая дама подумала:
– Так ему и надо! Как я рада, что современные девушки умеют постоять за себя!
Девушка подумала:
– Какие странные вкусы у этих бошей! Вместо того чтобы, поцеловать меня, он, должно быть, попытался поцеловать старуху или этого симпатичного молодого человека. Мне этого в жизни не понять!
Нацистский офицер подумал:
– Что произошло? Я стоял тихо, никого не трогал. Может быть, француз попытался в темноте поцеловать девушку, а она по ошибке ударила меня?
И только француз знал, что произошло на самом деле. А вы не догадались, что случилось в лифте?
Ответы помещены в конце книги. Попробуйте разгадать обе загадочные истории самостоятельно, а потом проверьте ваши решения.
Сцена у фонтана
В один из дней Джон, с удобством расположившись в кресле, читал юмористические заметки в местной газете, как вдруг в холл вбежала хорошенькая девушка.
Она стремглав бросилась к фонтанчику с питьевой водой и, сделав большой глоток, так же стремительно скрылась.
Через несколько минут она вновь появилась, стремительно подбежала к фонтанчику и сделала еще один глоток. На этот раз за ней по пятам крался мужчина довольно странного вида.
В стене за фонтанчиком было зеркало. Когда девушка подняла голову и увидела, что у нее за спиной в угрожающей позе с огромным кинжалом в руке стоит мужчина, она громко вскрикнула.
Джон упал в обморок.
Если бы он не поторопился, его глазам предстала бы неожиданная сцена: мужчина опустил руку с кинжалом, обнял девушку за плечи, и они как ни в чем не бывало весело рассмеялись.
Что произошло в холле гостиницы?
Видение в зеркале
Странное поведение девушки объясняется очень просто: ее мучила икота, а мужчина пытался испугать ее (как вы должно быть знаете, по весьма распространенному поверью, испуг – лучшее средство от икоты).
Предоставляем вам последний шанс проверить вашу способность находить оригинальные, неожиданные решения логических задач. Сначала мы предлагаем вам практическую задачу на «исследование операций», а затем – задачу, которая решается совсем просто, если не обременять ее дополнительными неявными допущениями.
1. Клеопатра держала свои бриллианты в шкатулке с выдвигающейся верхней крышкой. Чтобы воры не могли похитить сокровища, в шкатулке вместе с драгоценностями она держала небольшую змейку, аспида, укус которой смертелен.
Однажды по недосмотру дворецкого раб остался на считанные минуты один в спальне, где царица хранила свои драгоценности, и ухитрился похитить бесценные камни, не вынимая змею из шкатулки, не прикасаясь к ней, не усыпляя ее и не воздействуя на нее какими-либо другими способами. Раб действовал голыми руками. Кража была совершена за какие-то мгновения. Когда раб тайком покинул царскую опочивальню, всё в ней было по-прежнему, если не считать, что в шкатулке не хватало нескольких бриллиантов. Каким хитроумным способом раб их похитил?
2. У некой дамы не было при себе лицензии на право вождения автомашины. Она не остановилась на железнодорожном переезде, хотя шлагбаум был опущен и, не обращая внимания на знак одностороннего движения, двинулась в противоположном направлении и остановилась лишь миновав три квартала. Все это происходило на глазах полисмена, который, однако, не счел необходимым задержать даму. Почему?
Ответы на эти загадки приведены в конце книги.
Глава 5
Процедурные находки
Неожиданные решения задач на исследование операций
С появлением современных ЭВМ слово «алгоритм» прочно вошло в математический лексикон. Означает оно процедуру решения, состоящую из множества шагов, выполняемых в строго определенной последовательности. Если требуется разделить одно большое число на другое, то найти частное вам помогает алгоритм деления. ЭВМ не умеет решать задачи самостоятельно: программисту приходится каждый раз составлять точный перечень тех действий, которые необходимо произвести, чтобы получить решение. Искусство программирования для ЭВМ сводится главным образом к искусству построения эффективных алгоритмов. Мы говорим об искусстве, а не о технике программирования потому, что таинственные озарения, удачные догадки и интуиция играют решающую роль в создании хороших алгоритмов.
Под хорошим мы понимаем алгоритм, позволяющий решать задачу в кратчайшее время. Эксплуатация ЭВМ и содержание обслуживающего персонала обходится в изрядную сумму, поэтому хороший (эффективный) алгоритм дает немалую экономию. Существует даже быстро развивающаяся область современной математика, называемая исследованием операций, которая только тем и занимается, что ищет наиболее эффективные способы решения сложных задач.
Хотя в этой главе собраны процедурные задачи занимательного характера, они позволят вам легко и приятно познакомиться со многими глубокими математическими понятиями. Например, первая задача позволит вам составить весьма ясное представление о том, что имеют ввиду математики, когда толкуют об изоморфизме двух, казалось бы, не связанных между собой задач: игра в 15, в которой так силен мистер Ярмар, оказывается структурно-изоморфной знаменитой игре в «крестики-нолики». В свою очередь эта весьма популярная игра изоморфна хитроумной игре в слова, изобретенной канадским математиком Лео Мозером, и еще одной игре на «дорожной сети». Все эти игры обладают стратегиями, основанными на использовании одного из наиболее древних комбинаторных курьезов – магического квадрата 3×3.
Вы познакомитесь также с законом Архимеда (в задаче о взвешивании священного гиппопотама), с нерешенной задачей о справедливом разделе (в задаче о распределении домашних обязанностей), с некоторыми классическими комбинаторными задачами (в комментариях к задаче о краже веревки с колокольни) и с важными задачами теории графов (в задаче о ленивом искателе любовных приключений).
Теория графов занимается изучением различных множеств точек (вершин), соединенных линиями (ребрами). Многие практические задачи исследования операций допускают моделирование на графах. Некоторые из таких задач допускают изящные решения, например задача о построении минимального дерева, решаемая при помощи алгоритма Крускала. С задачей о минимальном дереве тесно связана еще одна задача – так называемая задача о дереве Штейнера. Общее решение ее пока не известно. Деревья Штейнера находят многочисленные приложения, поэтому специалисты по теории графов ведут весьма интенсивный поиск эффективных алгоритмов построения таких деревьев на ЭВМ.
Задача Штейнера принадлежит к числу так называемых NP-полных задач. Эти задачи неразрешимы в том смысле, что эффективные алгоритмы их решений не известны и, возможно, не существуют. Например, даже при использовании лучшего из известных алгоритмов построения дерева Штейнера для n точек время, затрачиваемое на решение, с увеличением n возрастает экспоненциально. Даже при сравнительно небольшом числе точек (порядка нескольких сотен) на построение дерева Штейнера лучшее решение может быть найдено… через несколько миллионов лет! Вот что значит экспоненциальный рост.
Между NP-полными задачами существует удивительная взаимосвязь: если бы для решения одной из них удалось построить эффективный алгоритм, но он был бы применим и ко всем остальным задачам, а если бы удалось доказать, что для решения какой-то из задач эффективного алгоритма не существует, то это означало бы отсутствие эффективного алгоритма для решения и всех остальных задач. Математики подозревают, что в случае NP-полных задач мы имеем дело со второй альтернативой. Ведется широкий поиск эффективных алгоритмов, позволяющих находить не оптимальное дерево Штейнера, а дерево, достаточно близкое к оптимальному.
В этой главе чаще, чем в других, упоминаются последние результаты исследований, проводимых лучшими умами современной математики.
Игра в 15 на новый лад
Когда на окраине городка открывается ярмарка, всех от мала до велика охватывает радостное возбуждение (говоря о всех, я имею в виду «всех, кроме коров»).
В этом году в одном из павильонов ярмарки желающие могли сыграть в новую игру, которая так и называется – «игра в 15».
Мистер Ярмар. Рад приветствовать вас! Добро пожаловать к нам! Правила игры в 15 очень просты. Мы с вами по очереди ставим по монете на эти числа от 1 до 9. Кто ходит первым, безразлично.
Мистер Ярмар. Вы отмечаете свои ходы центами, я отмечаю свои ходы серебряными долларами. Выигрывает тот, кто первым накроет своими монетами 3 числа, дающие в сумме 15. Выигравший забирает все монеты, выложенные на стол.
Посмотрим, как играют в 15. Первый ход – дама ставит цент на 7. Поскольку цифра 7 накрыта, ставить на нее в дальнейшем нельзя; ни доллары, ни центы. То же можно сказать и обо всех остальных цифрах: ни одну из них нельзя накрывать монетами дважды, будь то центы или доллары.
Мистер Ярмар ставит доллар на 8.
Дама делает второй ход и ставит цент на 2. Если ей удастся поставить цент на 6, она выиграет.
Мистер Ярмар, желая воспрепятствовать выигрышу партнера, ставит доллар на 6. Он выиграет, если ему удастся поставить доллар на 1.
Дама замечает угрозу и блокирует мистеру Ярмару путь к выигрышу, ставя цент на 1.
Мистер Ярмар с усмешкой ставит доллар на 4. Дама замечает, что если он следующим ходом поставит доллар на 5, то выиграет, и отрезает ему этот путь к выигрышу.
Дама ставит цент на 5.
Но мистер Ярмар ставит доллар на 3 и выигрывает, так как 8 + 4 + 3 = 15. Дама проиграла свои 4 цента.
Мэру города игра в 15 очень понравилась. Пронаблюдав за игрой в течение почти целого дня, он пришел к убеждению, что мистер Ярмар придерживается тайной беспроигрышной стратегии.
Всю ночь напролет мэр пытался разгадать, в чем состоит тайная стратегия мистера Ярмара.
Внезапно мэра озарила поразительная по простоте идея.
Мэр. Я так и знал, что должна быть какая-то система! У доверчивых простаков, надеющихся заполучить серебряные доллары мистера Ярмара, нет ни шанса на выигрыш.
Какая идея осенила мэра? Не могли бы вы самостоятельно разработать беспроигрышную стратегию для игры в 15?
Старые добрые «крестики-нолики»!
Выигрышную стратегию указать нетрудно, если догадаться, что игра в 15 мистера Ярмара математически эквивалентна игре в «крестики-нолики». Установить эквивалентность нам поможет ло-шу – магический квадрат 3×3, впервые открытый в древнем Китае.
Чтобы в полной мере оценить изящество этого магического квадрата, выпишем прежде всего все возможные тройки однозначных чисел (попарно не равных и отличных от нуля), которые в сумме дают 15. Существует 8 таких троек:
1 + 5 + 9 = 15,
1 + 6 + 8 = 15,
2 + 4 + 9 = 15,
2 + 5 + 8 = 15,
2 + 6 + 7 = 15,
3 + 4 + 8 = 15,
3 + 5 + 7 = 15,
4 + 5 + 6 = 15.
Теперь присмотримся повнимательнее к единственному магическому квадрату 3×3:
2 9 4
7 5 3
6 1 8
Если считать, что каждое число вписано в единичный квадрат (составляющий 1/9 от квадрата 3×3), то можно выделить 8 троек единичных квадратов, лежащих: на одной прямой: 3 горизонтали, 3 вертикали и 2 диагонали. Каждая из прямых соответствует одной из троек чисел, дающих в сумме 15. Следовательно, любой набор из 3 чисел, обеспечивающий победу в игре мистера Ярмара, соответствует либо горизонтали, либо вертикали, либо диагонали магического квадрата.
Нетрудно видеть, что любая партия в 15 эквивалентна партии а «крестики-нолики», разыгрываемой на магическом квадрате. У мистера Ярмара имеется магический квадрат, начерченный на листке бумаги, в который он тайком поглядывает. Хотя существует единственный квадрат ло-шу, но его можно повернуть четырьмя разными способами и, если угодно, подвергнуть зеркальному отражению. Любая из 8 разновидностей магического квадрата может служить тайным ключом к гроссмейстерской стратегии при игре в 15.
Играя с посетителем павильона в 15, мистер Ярмар мысленно играет с ним в «крестики-нолики» на магическом квадрате. Если игра в «крестики-нолики» происходит по всем правилам, то партия в 15 кончается вничью. Но легковерные посетители павильона, вздумавшие сразиться с мистером Ярмаром в 15, лишены огромного преимущества, так как не сознают, что в действительности играют в «крестики-нолики». Это облегчает задачу мистеру Ярмару, и он подстраивает своим партнерам каверзы и ловушки, вынуждая их делать ходы, ведущие к его выигрышу.
Чтобы разобраться, как действует мистер Ярмар, рассмотрим подробно партию, изображенную на картинках. Ходы приведены на диаграммах, показанных на рис. 1. Даже если мистер Ярмар ходит вторым (ставит нолики), то на шестом ходу он может поставить даме западню, которая обеспечит ему выигрыш на восьмом ходу независимо от того, как именно пойдет дама на седьмом ходу. Всякий, кто умеет играть на гроссмейстерском уровне в «крестики-нолики», взяв на вооружение магический квадрат, станет непобедимым игроком в 15.
Понятие изоморфизма (математической эквивалентности) – одно из важнейших в математике. Во многих случаях трудная задача легко решается, если ее удается свести к изоморфной уже решенной задаче. По мере того как математика разрастается вглубь и вширь, она становится все более единой, все более упрощается по мере открытия все новых и новых изоморфизмов. Например, найденное в 1976 г. решение знаменитой проблемы четырех красок позволило доказать десятки других важных гипотез в иных разделах математики, которые были изоморфны проблеме четырех красок.
Чтобы помочь вам глубже разобраться в сущности такого фундаментального понятия, как изоморфизм, рассмотрим следующую игру в слова, Берется 9 слов:
БУСЫ
ХЛЕБ
БАНЯ
ПЛУГ
СНЕГ
ГАТЬ
УРОН
ОРЕХ
МАРС
Двое игроков по очереди вычеркивают по одному слову, помечая каждый сделанный ход своими инициалами или условным значком. Выигрывает тот, кому первым удастся вычеркнуть три слова, имеющие общую букву. Пройдет немало времени, прежде чем игроки поймут, что и на этот раз они играют в добрые старые «крестики-нолики». Изоморфизм игр нетрудно установить, если вписать слова в клетки таблички, расчерченной для игры в «крестики-нолики» (рис. 2). Как нетрудно проверить, общая буква имеется лишь у трех слов, расположенных по горизонталям, вертикалям и диагоналям. Тем самым доказано, что играть в слова означает по существу играть в «крестики-нолики», и наоборот (или в 15).
Попробуйте подобрать другие 9 слов для игры. Разумеется, отнюдь не обязательно играть именно в слова родного языка. С тем же успехом можно воспользоваться и абстрактными символами, как это сделано на рис. 3.
Еще лучше играть во все эти игры, записав слова, знаки или цифры на 9 карточках. Разложив точки на столе исписанной стороной вверх, игроки могут по очереди брать по одной карточке до тех пор, пока одни из них не выиграет.
Разобравшись в изоморфизме игры в 15, «крестики-нолики» и игры в слова, приступим к новой игре – на дорожной сети. В нее играют на карте дорог, изображенной на рис. 4.
Между восемью городами проложены дороги. Вооружившись цветными карандашами (один игрок пусть выберет красный карандаш, а другой – синий), игроки по очереди закрашивают по одной дороге (каждую дорогу необходимо закрашивать целиком). Обратите внимание, что некоторые дороги проходят через города не обрываясь. В таких случаях закрашивать дорогу нужно не только до ближайшего города, а на всем ее протяжении. Выигрывает тот, кому первым удастся закрасить три дороги, ведущие в один и тот же город. На первый взгляд кажется, что новая игра не имеет ни малейшего отношения к трем уже рассмотренным нами играм. В действительности же и она изоморфна игре в «крестики-нолики»!
Чтобы установить изоморфизм, достаточно перенумеровать дороги так, как показано на рис. 4. Каждая дорога соответствует клетке магического квадрата, помеченной тем же числом. Каждый город на карте соответствует горизонтали, вертикали или диагонали в магическом квадрате. Как и в предыдущих случаях, изоморфизм полный. Всякий, кто умеет на гроссмейстерском уровне играть в «крестики-нолики», не будет знать горечи поражений и в новой игре.
На рис. 5 изображен один из 880 различных (не переходящих друг в друга под действием поворотов и отражений) магических квадратов 4×4. Постоянная этого квадрата (сумма чисел, стоящих на любой горизонтали, вертикали и диагонали) равна 34. Может ли такой квадрат служить ключом для беспроигрышной игры в 34, то есть игры, в которой игроки по очереди выбирают число от 1 до 16 (ни одно число не разрешается выбирать дважды) до тех пор, пока у одного из игроков не наберется четыре числа, дающие в сумме 34. Изоморфна ли игра в 34 игре в «крестики-нолики» на магическом квадрате, изображенном на рис. 5? Нет, не изоморфна! Почему?
Можно ли так изменить правила игры в «крестики-нолики», чтобы победную комбинацию образовывали четыре клетки, не лежащие на одной горизонтали, вертикали или диагонали, и утраченный изоморфизм был восстановлен?
