Есть идея! - [57]
Общая задача о построении минимальной сети, соединяющей n заданных точек на плоскости (при условии, что разрешается вводить новые вершины), известна под названием задачи Штейнера. Она решена лишь в отдельных частных случаях. Эффективный алгоритм, позволяющий определять положение «точек Штейнера» (новых вершин) минимального дерева Штейнера, соединяющего n заданных точек плоскости, не известен. Задача Штейнера имеет многочисленные приложения в технике — от элементов микросхем, используемых в ЭВМ, до прокладки кратчайших сетей железных дорог, воздушных маршрутов, телефонных линий и любых других видов транспорта и связи.
Хирурги и инфекция
В чаще тропических джунглей расположен госпиталь, в котором работают три хирурга: Джонс, Смит и Робисон.
Вождь местного племени поступил в госпиталь по подозрению в опасном инфекционном заболевании, требовавшем неотложного хирургического вмешательства. Ввиду особой сложности операции, ее должны были проводить, сменяя друг друга, все три хирурга. При осмотре вождя они могли заразиться и стать носителями инфекции.
Каждый хирург оперирует в тонких резиновых перчатках. Если он болен, то инфицируется внутренняя поверхность перчаток, соприкасающаяся с его руками. Если болен вождь, то инфицируется наружная поверхность перчаток.
Перед самым началом операции в комнату, где хирурги мыли руки, вбежала старшая сестра мисс Клини.
Мисс Клини. У меня для вас плохие новости, уважаемые эскулапы.
Мисс Клини. У нас остались только две пары стерильных перчаток: одна пара белых и одна пара синих.
Доктор Джонс. Только две пары? Если я оперирую первым, то обе стороны моих перчаток могут оказаться зараженными. После Смита, если он будет оперировать вторым, окажутся зараженными обе стороны другой пары перчаток, и Робисону не в чем будет оперировать.
Вдруг лицо доктора Смита просветлело.
Доктор Смит. А что если я надену две пары перчаток — синие поверх белых. Одна сторона каждой пары инфицируется, а другая останется стерильной.
Джонс быстро схватил мысль коллеги.
Доктор Джонс. После вас я надену синие перчатки стерильной стороной внутрь, а Робисон, вывернув, наденет белые перчатки стерильной стороной внутрь. При этом каждый из нас избежит опасности заразиться.
Сестра Клини. А о вожде вы не подумали? Ведь если кто-нибудь из вас является носителем инфекции, то вы можете заразить вождя во время операции.
Справедливое замечание медсестры повергло хирургов в замешательство. Что делать? И тут мисс Клини осенило.
Сестра Клини. Я придумала, как вам втроем оперировать вождя, не подвергая ни себя, ни его риску заражения.
Никто из трех врачей так и не смог ничего предложить, но когда мисс Клини объяснила, в какой последовательности надлежит надевать и выворачивать перчатки, все согласились, что ее план действительно обеспечивает полную безопасность и вождя и хирургов. Как предложила действовать мисс Клини?
Прежде чем объяснять великолепный выход из затруднительного положения, предложенный мисс Клини, постараемся основательно разобраться в первом варианте решения, исключавшем опасность заражения только для хирургов.
Пусть Б1 — внутренняя, а Б2 — наружная сторона белых перчаток, С1 — внутренняя, а С2 — наружная сторона синих перчаток.
Доктор Смит надевает обе пары перчаток: сначала он натягивает белые перчатки, а поверх них синие. Сторона Б1 инфицируется, так как соприкасается с руками доктора Смита, сторону С2 может инфицировать вождь. После операции Смит снимает обе пары перчаток. Доктор Джонс надевает синие перчатки стерильной стороной С1 внутрь, а доктор Робинсон выворачивает белые перчатки наизнанку и надевает их стерильной стороной Б2 внутрь.
Переходим теперь к описанию процедуры, предложенной мисс Клини.
Доктор Смит по-прежнему надевает 2 пары перчаток. Стороны Б1 и С2 могут оказаться после операции инфицированными, но стороны Б2 и С1 останутся стерильными.
Доктор Джонс надевает синие перчатки стороной С1 внутрь.
Доктор Робисон выворачивает белые перчатки наизнанку и надевает их стороной Б2 внутрь. Поверх белых перчаток он натягивает синие перчатки стороной С2 наружу.
Во всех трех случаях вождя касается только сторона С2 синих перчаток, поэтому он не подвергается опасности заразиться от кого-нибудь из хирургов.
Насколько известно, общий случай этой задачи никогда не рассматривался, хотя он и небезынтересен для любителей занимательной математики. Приведем его для тех, кто захочет испытать свои силы: сколько перчаток необходимо заготовить хирургической сестре, чтобы при самом жестком режиме экономии полностью исключить возможность заражения хирургов и пациентов, если известно, что n хирургам предстоит прооперировать k пациентов?
Глава 6
Словесные находки
Неожиданные решения различного рода задач о буквах, словах и предложениях
Математики любят играть в слова. Например, в серьезной книге Ф. Хараря и Э. Палмера «Перечисление графов»[5] мы встречаем примечание: «Рид сообщил Райту, что и он, и Райт допустили ошибку. Затем Рид и Райт, чтобы исправить положение вещей, указали в совместной работе на допущенную ранее ошибку. Возможно, что все это выглядело несколько иначе, ибо Райт утверждает, что он первый написал Риду». Примеров можно было бы привести так много, что они могли бы составить целую книгу.
