Текст книги "Есть идея!"
Автор книги: Мартин Гарднер
сообщить о нарушении
Текущая страница: 14 (всего у книги 17 страниц)
Ленивый донжуан
Джек считал себя величайшим в мире сердцеедом. Он решил снять квартиру в Вашингтоне.
В этом городе у него жили три приятельницы, и он решил поселиться как можно ближе ко всем трем.
На плане города Джек отметил те места, где живут его приятельницы.
Джек. Я бы хотел поселиться в таком месте, откуда было бы удобно добираться до всех моих приятельниц, то есть чтобы сумма расстояний от моего дома до тех мест, где живут они, была бы минимальной.
Джек прикидывал так и этак, но все было безуспешно: найти нужную точку никак не удавалось. Вдруг ему пришло в голову неожиданное и простое решение.
Джек. Есть идея! Теперь я знаю, как легко и просто выбрать, где мне поселиться.
Джек мысленно опрашивал своих приятельниц, как бы они отнеслись к тому или иному его «переселению» и те «голосовали» либо за, либо против. Для начала Джек выбрал на карте точку в достаточно разумном месте и «переселился» на 1 квартал к востоку от нее.
Джек. Анита и Банни проголосовали бы за такое переселение, так как я перебрался бы поближе к ним, а Вика проголосовала бы против. Но в расстоянии я выиграл бы больше, чем проиграл, поэтому я подчинюсь мнению, за которое подано большинство голосов.
Всякий раз, когда большинство голосов было за очередное переселение, Джек оставался на новом Месте, а если большинство голосов было против, возвращался на старое. Наконец, он достиг точки, из которой нельзя было переместиться ни в одну сторону, чтобы девушки не проголосовали против. Там он и решил поселиться.
К его радости, квартирная плата в выбранном месте была ему по карману. Но через неделю Банни переехала на новую квартиру в 7 кварталах от своего прежнего дома.
Джек. Жаль, но придется переезжать на новую квартиру.
Но когда Джек достал план города, то, к своему удивлению, обнаружил, что может оставаться на месте.
Как это может быть?
Алгоритм с голосованием
Если Банни переедет на 7 кварталов к востоку от того места, где жила раньше, то ее переезд никак не скажется на выборе резиденции Джека. Более того, Банни могла бы переехать сколь угодно далеко на восток, и место, выбранное для своей квартиры Джеком, по-прежнему оставалось бы оптимальным.
Эффективность алгоритма с голосованием вы сможете лучше оценить, применив к более обширной территории с прямоугольной планировкой, на которой отмечено более трех точек. Вы обнаружите, что алгоритм Джека позволяет быстро находить положение точки x, сумма расстояний от которой до всех отмеченных точек минимально, если число отмеченных точек нечетно. Почему алгоритм перестает работать при четном числе точек? Причина довольно ясна: при четном числе отмеченных точек не исключен «ничейный» исход голосования, а как только голоса разбиваются поровну, алгоритм не срабатывает.
Попробуйте самостоятельно ответить на следующие вопросы:
1. Не могли бы вы предложить эффективный алгоритм, действующий при четном числе отмеченных точек?
2. При каких условиях перемещение одной или нескольких отмеченных точек не сказывается на положении точки x?
3. Изменится ли алгоритм с голосованием, если мы вздумаем учесть ширину улиц?
4. Изменится ли алгоритм, если точка x и отмеченные точки могут не располагаться на перекрестках?
5. Применим ли алгоритм с голосованием в том случае, если сеть улиц образована прямыми, идущими в самых разных, а не только в двух взаимно перпендикулярных направлениях?
6. Останется ли алгоритм в силе, если улицы будут кривыми или зигзагообразными?
Хотя алгоритм с голосованием применим к любым сетям, на «чистой» плоскости без выделенной сети он сразу утрачивает силу, и это понятно: по чистой плоскости мы можем перемещаться в любом направлении, не придерживаясь заданных маршрутов. Общая задача ставится так. На плоскости заданы n точек. Требуется найти такую точку x, чтобы сумма кратчайших расстояний от нее до заданных точек была минимальной. Рассмотрим, например, три города A, B и C. Где следовало бы построить аэропорт, чтобы суммарная протяженность воздушных маршрутов из него в эти города была минимальной? Ясно, что если бы речь шла о длине автомобильных маршрутов, связывающих некоторую точку на карте с городами A, B и C, то ответ был бы другой. Иначе говоря, идеальное место для аэропорта может не совпадать с идеальным местом для автобусной станции.
Ответ, основанный на довольно сложных геометрических соображениях, гласит: идеальным местом для строительства аэропорта была бы такая точка на карте, в которой лучи, проведенные к трем городам, образовывали бы между собой углы в 120°. Если бы число городов возросло до четырех, причем города располагались в вершинах выпуклого четырехугольника, то аэропорт выгоднее всего было бы построить в точке пересечения диагоналей. Доказать это утверждение совсем не трудно. Общая задача (найти точку x, сумма кратчайших расстояний от которой до n заданных точек плоскости минимальна) более трудная.
Может быть, вам удастся придумать простое механическое устройство (аналоговую вычислительную машину), позволяющее быстро находить положение точки x для трех заданных точек на плоскости? Пусть плоскость изображает плоскость стола. В каждой из заданных точек просверлим в крышке стола отверстие. Затем пропустим через эти отверстия по веревочке, верхние концы веревочек свяжем в один узел, а к нижним подвесим одинаковые грузики. Равные силы, действуя на веревочки, заставят их «проголосовать» за жителей трех населенных пунктов, и узел расположится в точке x. Наша аналоговая машина основана на использовании изоморфизма между математической структурой задачи и структурой физической модели.
Усложним теперь исходную задачу. Предположим теперь, что в точках A, B и C находятся не населенные пункты с одинаковым количеством жителей, а три дома, причем в доме A живут 20 школьников, в доме B – 30 школьников и в доме C – 40 школьников. Все дети ходят в одну школу. Где следует выстроить школу, чтобы свести до минимума сумму расстояний, проходимых всеми детьми?
Если дети идут в школу по улицам города, то можно воспользоваться алгоритмом с голосованием, считая, что каждый ребенок обладает одним голосом. Он позволяет довольно быстро указать, где именно следует построить школу. Но если три дома возведены в чистом поле и школьники могут идти в школу по прямой, то как следует усовершенствовать нашу аналоговую вычислительную машину, чтобы и эта задача была ей под силу?
Нужно взять грузики с массами, пропорциональными числу детей в каждом доме. Положение узла покажет, где именно следует построить школу.
Сработает ли наше аналоговое устройство, если в одном доме учеников окажется больше, чем в двух других домах, вместе взятых, например, если 20 школьников живут в доме A, 30 школьников – в доме B и 100 школьников – в доме C? Да, сработает: грузик весом в 100 единиц будет тянуть свою веревочку до тех пор, пока узел не совместится с отверстием C. Это означает, что школу следует построить в точке C!
Будет ли наше аналоговое вычислительное устройство работать также безотказно при числе точек больше трех? Попробуйте придумать такое расположение четырех точек, при котором наше устройство даст заведомо неверный результат. Указание: что произойдет, если четыре точки расположены в вершинах невыпуклого четырехугольника?
Изучением систем точек (вершин), соединенных линиями (ребрами), занимается теория графов – обширный и быстро развивающийся раздел современной математики. Существуют десятки теорем теории графов, позволяющие находить минимальные пути. Одни задачи, связанные с отысканием минимальных путей, давно решены, другие ожидают своего решения. Примером знаменитой решенной задачи может служить следующая.
На плоскости заданы n точек. Требуется соединить их отрезками прямых так, чтобы суммарная протяженность сети была наименьшей. Добавлять новые вершины к заданным запрещается. Сеть, которую требуется построить, естественно назвать минимальным деревом. Можете ли вы предложить алгоритм для построения минимального дерева?
Алгоритм Крускала (названный в честь Джозефа Б. Крускала, который впервые предложил его) позволяет свести построение минимальной сети к следующим этапам.
Определить расстояния между любыми двумя точками и расположить все расстояния в порядке возрастания (напомним, что расстоянием между двумя вершинами в графе называется число ребер, ведущих из одной вершины в другую). Кратчайшее расстояние равно 1, затем идет расстояние 2 и т. д. Если два расстояния одинаковы, то безразлично, какое из них считать первым. Соединить отрезками прямых все точки, расстояние между которыми равно 1. Затем соединить отрезками прямых все точки, расстояние между которыми равно 2, 3, 4, 5 и т. д. Никогда не проводить отрезок, замыкающий цикл. Если проведенная линия замыкает цикл, отбросить соответствующую пару точек и перейти к рассмотрению точек, разделенных следующим по величине расстоянием. Проделав все эти операции, мы получим минимальное дерево, соединяющее все заданные точки.
Минимальные деревья обладают интересными свойствами. Например, все рёбра пересекаются только в вершинах, причем в одной вершине пересекается не более 5 ребер.
Минимальные деревья отнюдь не обязательно совпадают с кратчайшей сетью, соединяющей n точек. Напомним, что дополнять сети новыми вершинами не разрешается. Если снять запрет на новые вершины, то сети могут стать короче. В качестве простого примера достаточно рассмотреть четыре вершины единичного квадрата. Минимальное дерево состоит из любых трех сторон квадрата (рис. 13, слева). Предположим, что разрешается вводить новые вершины. Существует ли тогда сеть короче 3, соединяющая четыре вершины?
Большинство людей считает, что минимальную сеть образуют две диагонали квадрата (рис. 13, посредине), но это не верно. Правильное решение изображено на рис. 13, справа. Суммарная длина двух диагоналей квадрата равна 2√2 ≈ 2,82… Суммарная длина сети на правом рисунке меньше, она равна лишь 1 + √3 ≈ 2,73…
Общая задача о построении минимальной сети, соединяющей n заданных точек на плоскости (при условии, что разрешается вводить новые вершины), известна под названием задачи Штейнера. Она решена лишь в отдельных частных случаях. Эффективный алгоритм, позволяющий определять положение «точек Штейнера» (новых вершин) минимального дерева Штейнера, соединяющего n заданных точек плоскости, не известен. Задача Штейнера имеет многочисленные приложения в технике – от элементов микросхем, используемых в ЭВМ, до прокладки кратчайших сетей железных дорог, воздушных маршрутов, телефонных линий и любых других видов транспорта и связи.
Хирурги и инфекция
В чаще тропических джунглей расположен госпиталь, в котором работают три хирурга: Джонс, Смит и Робисон.
Вождь местного племени поступил в госпиталь по подозрению в опасном инфекционном заболевании, требовавшем неотложного хирургического вмешательства. Ввиду особой сложности операции, ее должны были проводить, сменяя друг друга, все три хирурга. При осмотре вождя они могли заразиться и стать носителями инфекции.
Каждый хирург оперирует в тонких резиновых перчатках. Если он болен, то инфицируется внутренняя поверхность перчаток, соприкасающаяся с его руками. Если болен вождь, то инфицируется наружная поверхность перчаток.
Перед самым началом операции в комнату, где хирурги мыли руки, вбежала старшая сестра мисс Клини.
Мисс Клини. У меня для вас плохие новости, уважаемые эскулапы.
Мисс Клини. У нас остались только две пары стерильных перчаток: одна пара белых и одна пара синих.
Доктор Джонс. Только две пары? Если я оперирую первым, то обе стороны моих перчаток могут оказаться зараженными. После Смита, если он будет оперировать вторым, окажутся зараженными обе стороны другой пары перчаток, и Робисону не в чем будет оперировать.
Вдруг лицо доктора Смита просветлело.
Доктор Смит. А что если я надену две пары перчаток – синие поверх белых. Одна сторона каждой пары инфицируется, а другая останется стерильной.
Джонс быстро схватил мысль коллеги.
Доктор Джонс. После вас я надену синие перчатки стерильной стороной внутрь, а Робисон, вывернув, наденет белые перчатки стерильной стороной внутрь. При этом каждый из нас избежит опасности заразиться.
Сестра Клини. А о вожде вы не подумали? Ведь если кто-нибудь из вас является носителем инфекции, то вы можете заразить вождя во время операции.
Справедливое замечание медсестры повергло хирургов в замешательство. Что делать? И тут мисс Клини осенило.
Сестра Клини. Я придумала, как вам втроем оперировать вождя, не подвергая ни себя, ни его риску заражения.
Никто из трех врачей так и не смог ничего предложить, но когда мисс Клини объяснила, в какой последовательности надлежит надевать и выворачивать перчатки, все согласились, что ее план действительно обеспечивает полную безопасность и вождя и хирургов. Как предложила действовать мисс Клини?
Снаружи и внутри
Прежде чем объяснять великолепный выход из затруднительного положения, предложенный мисс Клини, постараемся основательно разобраться в первом варианте решения, исключавшем опасность заражения только для хирургов.
Пусть Б1 – внутренняя, а Б2 – наружная сторона белых перчаток, С1 – внутренняя, а С2 – наружная сторона синих перчаток.
Доктор Смит надевает обе пары перчаток: сначала он натягивает белые перчатки, а поверх них синие. Сторона Б1 инфицируется, так как соприкасается с руками доктора Смита, сторону С2 может инфицировать вождь. После операции Смит снимает обе пары перчаток. Доктор Джонс надевает синие перчатки стерильной стороной С1 внутрь, а доктор Робинсон выворачивает белые перчатки наизнанку и надевает их стерильной стороной Б2 внутрь.
Переходим теперь к описанию процедуры, предложенной мисс Клини.
Доктор Смит по-прежнему надевает 2 пары перчаток. Стороны Б1 и С2 могут оказаться после операции инфицированными, но стороны Б2 и С1 останутся стерильными.
Доктор Джонс надевает синие перчатки стороной С1 внутрь.
Доктор Робисон выворачивает белые перчатки наизнанку и надевает их стороной Б2 внутрь. Поверх белых перчаток он натягивает синие перчатки стороной С2 наружу.
Во всех трех случаях вождя касается только сторона С2 синих перчаток, поэтому он не подвергается опасности заразиться от кого-нибудь из хирургов.
Насколько известно, общий случай этой задачи никогда не рассматривался, хотя он и небезынтересен для любителей занимательной математики. Приведем его для тех, кто захочет испытать свои силы: сколько перчаток необходимо заготовить хирургической сестре, чтобы при самом жестком режиме экономии полностью исключить возможность заражения хирургов и пациентов, если известно, что n хирургам предстоит прооперировать k пациентов?
Глава 6
Словесные находки
Неожиданные решения различного рода задач о буквах, словах и предложениях
Математики любят играть в слова. Например, в серьезной книге Ф. Хараря и Э. Палмера «Перечисление графов»[5]5
Харари Ф., Палмер Э. Перечисление графов. – М.: Мир, 1977, С. 29.
[Закрыть] мы встречаем примечание: «Рид сообщил Райту, что и он, и Райт допустили ошибку. Затем Рид и Райт, чтобы исправить положение вещей, указали в совместной работе на допущенную ранее ошибку. Возможно, что все это выглядело несколько иначе, ибо Райт утверждает, что он первый написал Риду». Примеров можно было бы привести так много, что они могли бы составить целую книгу.
Нетрудно понять, почему математикам нравятся такие шутки. Слова представляют собой не что иное, как комбинации букв, составленных в определенном порядке, так же как предложения – линейные последовательности слов, составленные в соответствии с формальными правилами синтаксиса. Таким образом, многое роднит лингвистику с комбинаторной математикой. Словесные квадраты по своей структуре аналогичны магическим квадратам. Знаки препинания в предложении соответствуют математическим символам (скобкам, плюсам, минусам и т. д.), вводящим «пунктуацию» в алгебраические предложения.
Все эти (и многие другие) приятные аналогии между языком и математикой собраны в последней, шестой главе нашей книги. Палиндромы – слова или фразы, которые читаются одинаково от начала к концу и от конца к началу, – аналогичны палиндромным числам. Как мы увидим, в теории чисел существует известная «гипотеза о палиндромных числах», не доказанная и не опровергнутая. О палиндромных простых и составных числах, являющихся квадратами и кубами, доказано немало интересных теорем. Другие головоломки в этой главе связаны с разбиением слов на части, во многом напоминающим разбиение чисел на суммы.
Если буквы рассматривать как геометрические фигуры, то мы сразу же вступаем в область необычных геометрических задач и головоломок. Мы увидим, каким образом эти задачи связаны с существованием двух важных разновидностей операции симметрии: симметрии относительно поворота на 180° и зеркальной симметрии. Мы обнаружим, что некоторые слова и даже целые предложения выдерживают поворот на 180°, и некоторые цифры на индикаторе микрокалькуляторов переходят в буквы латинского алфавита.
Буквы не обязательно считать жесткими и нерастяжимыми. Если мы будем рассматривать их не как геометрические фигуры, сохраняющие форму при поворотах и отражениях, а как топологические фигуры, которые можно изгибать, сжимать, растягивать, как резиновые жгуты, то перед нами откроется еще одна обширная область занимательных задач, с решением которых вам также предстоит познакомиться. Именно в этих задачах вы увидите «за работой» простейшие топологические понятия.
Наконец, вам предстоит встреча с задачами, связанными с важными понятиями математической логики. Простейшая задача о высказывания, противоположном высказыванию «не в», познакомит вас со свойствами отрицания и правилами обращения с отрицательными величинами в алгебре. Многие из наших шуточных задач становятся понятными, если вы четко осознаете, что говорить о словах и предложениях живого языка можно, лишь построив язык следующего, более высокого уровня, который логики называют метаязыком.
Мы умышленно стремились сделать заключительную главу нашей книги самой легкой и занимательной. Может быть, вас удивляет, почему для словесных забав и игр вообще, нашлось место в книге по занимательной математике? По существу мы уже ответили на ваш недоуменный вопрос. Дело, разумеется, не в том, что математики любят играть в слова или что лингвистике присущи определенные комбинаторные аспекты. Мы хотели лишь показать, что даже игра в слова может приоткрыть перед вами неожиданные и важные аспекты серьезной математики.
Проф. С. О. Слог
Перед вами знаменитый математик проф. Сэм О. Слог.
Проф. Слог ведущий и автор популярной телевизионной программы «Состязание любителей слова». Гости этой передачи, которым удается правильно ответить на вопросы проф. Слога, получают ценные призы.
Проф. Слог. Игра в слова имеет много общего с математикой. Символами служат буквы и слова, а правила грамматики позволяют отличать допустимые комбинации от недопустимых.
Проф. Слог. Позвольте привести несколько примеров. Какая надпись по своему значению противоположна известной надписи «Не входить»?
Проф. Слог. Какое слово из 11 букв все выпускники Йельского университета пишут неправильно?
Проф. Слог. Вы, конечно, успешно справились с этими двумя заданиями. Надписи «Не входить» противоположна по значению надпись «Входить».
Слово «неправильно» все выпускники Йельского университета так и пишут: неправильно. А сейчас позвольте представить вам нашего первого гостя.
Не не
Попросите кого-нибудь назвать действие, противоположное действию «не входить», и вы, как правило, услышите в ответ: «Выходить». Между тем действию «не входить» противоположно его отрицание «не не входить», то есть «входить». Два минуса дают плюс и в арифметике, и в формальной логике. Приведем несколько примеров, подтверждающих это правило.
1. x = (7 − 3) − [(−4 + 1)]³.
2. Заголовок из газеты «Нью-Йорк тайме» от б мая 1965 г.: «Албания выступает против отмены закона о запрете контроля над рождаемостью».
3. Известный специалист по математической логике А. Н. Уайтхед однажды поблагодарил докладчика за то, что тот «изложил весьма темный предмет не без ясности».
4. Молодой человек получает письмо от своей подруги: «Должна сказать, что мои слова о том, что я всерьез подумываю о том, чтобы передумать, не следует принимать всерьез. Я и не думаю передумывать».
5. Преподаватель математики: «Не могу не заметить, что мне так и не удалось объяснить вам смысл отрицания, поэтому я не стану утомлять вас повторением».
Студент: «Я понял все, что вы сказали, и признателен вам за вашу готовность перейти к новому материалу».
6. Иногда в нарушение правила двойное отрицание употребляется для усиления отрицания. Вот несколько примеров:
Не вздумайте не сказать мне, что за сплетни она распускает.
Никому не запрещается не прибегать к двойным отрицаниям.
Небезупречное поведение.
7. Профессор логики упомянул во время лекции о том, что, насколько ему известно, ни в одном естественном языке два утверждения никогда не означают отрицание. Из задних рядов раздается саркастический голос: «Ну, ну!»
Вопрос о слове «неправильно» ставит людей в тупик потому, что они воспринимают это слово как наречие, относящееся к глаголу «пишут», а не как само слово «неправильно». В современной семантике любой вопрос о слове или предложении относится к так называемому «метаязыку», в то время как слово и предложение принадлежат к предметному, или объектному, языку. Чтобы отличить эти два языка, утверждения и слова объектного языка принято заключать в кавычки. Например, кавычки позволяют избавиться от неоднозначности (или по крайней мере уменьшить ее) в вопросе, заданном проф. Слогом: «Какое слово из 11 букв все выпускники Йельского университета пишут «неправильно»? При смешении двух уровней языка нередко возникает путаница.
Приведем несколько примеров.
Как – вы – думаете была кличка этой лошади.
Я, Ли, китайский математик.
Можете ли вы объяснить, что означает следующая фраза: «То то означает совсем не то, что я имею в виду».
