Большинство людей считает, что минимальную сеть образуют две диагонали квадрата (рис. 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 пациентов?

Математики любят играть в слова. Например, в серьезной книге Ф. Хараря и Э. Палмера «Перечисление графов»[5] мы встречаем примечание: «Рид сообщил Райту, что и он, и Райт допустили ошибку. Затем Рид и Райт, чтобы исправить положение вещей, указали в совместной работе на допущенную ранее ошибку. Возможно, что все это выглядело несколько иначе, ибо Райт утверждает, что он первый написал Риду». Примеров можно было бы привести так много, что они могли бы составить целую книгу.

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

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