Могу предложить только номер за 20 долларов в сутки. Плата наличными.
Глория. Простите, сэр, у меня нет при себе денег. Есть только этот золотой браслет. Каждое из его 7 звеньев стоит дороже 20 долларов.
Портье. Так и быть, давайте сюда ваш браслет.
Глория. Не торопитесь. Я попрошу какого-нибудь ювелира распилить браслет и буду отдавать вам по 1 звену в день, а к концу недели, когда мне пришлют из дому деньги, отдам браслет в починку.
После долгих споров портье согласился. Но перед Глорией встала задача: как распилить браслет?
Глория. Торопиться не следует. Ведь ювелир потребует с меня плату за каждое распиленное и вновь запаянное звено браслета.
Поразмыслив, Глория поняла, что ей вовсе не нужно распиливать все звенья, поскольку отдельные части браслета можно комбинировать так, чтобы число оставшихся у портье звеньев каждый раз соответствовало плате за номер. Сколько звеньев вы бы приказали распилить на месте Глории?
Достаточно распилить лишь одно-единственное звено: третье с любого конца цепи. Браслет распадется на 3 части длиной в 1 звено, 2 звена и 4 звена. Отдавая их в необходимой комбинации портье и получая предыдущие, Глория сможет оставлять у портье каждый день на 1 звено больше, чем накануне.
Чтобы решить эту задачу, необходимо принять во внимание два соображения. Во-первых, понять, что наименьший набор отрезков золотой цепочки, позволяющий оставить у портье любое число звеньев от 1 до 7, состоит из 3 отрезков длиной в 1, 2 и 4 звена. Как мы уже знаем из решения предыдущей задачи, эти числа — не что иное, как последовательные степени числа 2, положенные в основу двоичной системы счисления.
Во-вторых, необходимо понять, что разделить браслет на части длиной в 1, 2 и 4 звена можно распилив одно-единственное звено.
Задача допускает обобщение на случай, когда браслет или цепочка состоят более чем из 7 звеньев. Например, пусть у Глории имеется с собой золотая цепочка из 67 звеньев, которую необходимо распилить с той же целью, что и злосчастный браслет, — для уплаты за проживание в гостиничном номере от 1 до 67 суток по 1 звену за сутки. Оказывается, что в этом случае достаточно распилить лишь 3 звена. Вы знаете, какие именно? Может быть, вы можете предложить общий метод решения задачи, позволяющий распиливать минимальное число звеньев цепи произвольной длины?
Интересный вариант этой задачи возникает в том случае, если первоначально концы n-звенной цепочки соединены так, что цепочка превратилась в замкнутую петлю. Например, предположим, что у Глории есть золотая цепочка из 79 звеньев. Сколько звеньев необходимо распилить, чтобы Глория могла оплатить от 1 до 79 суток пребывания в гостинице из расчета по 1 звену за сутки?
Глава 2Геометрические находки
Неожиданные решения задач о геометрических телах и фигурах
Геометрия занимается изучением свойств тел и фигур, хотя такое определение настолько широко, что почти лишено смысла. Так, оно позволяет считать геометром члена жюри любого конкурса красоты, поскольку тот судит о «свойствах тел и фигур», хотя под телами и фигурами он понимает нечто иное, чем геометр. Когда о какой-нибудь линии кто-либо замечает, что она необычайно изящна или выразительна, то, хоть речь идет о кривой, то есть объекте, действительно изучаемом в геометрии, само высказывание относится скорее к области эстетики, чем к математике.
Попробуем уточнить, что такое геометрия, и определим ее с помощью такого понятия, как симметрия. Под симметрией принято понимать такое преобразование фигуры, которое оставляет фигуру неизменной. Например, буква H симметрична относительно поворота на 180°. Это означает, что если букву H повернуть на 180° (поставить «вверх ногами»), то она перейдет в фигуру, неотличимую от буквы H в исходном положении (разумеется, при условии, если перекладина в букве H находится строго посредине). Слово «AHA», стоящее на обложке этой книги, обладает зеркальной, или двусторонней симметрией: если приставить к нему справа или слева зеркало, то зеркальное отражение слова будет неотличимо от оригинала.
Любой раздел геометрии можно определить как науку о свойствах фигур, не изменяющихся при определенных преобразованиях симметрии. Например, евклидова геометрия на плоскости занимается изучением свойств, остающихся неизменными (инвариантных) при движении фигуры по плоскости, поворотах, зеркальных отражениях и равномерных сжатиях и растяжениях. Аффинная геометрия занимается изучением свойств, инвариантных относительно «перекашивания» фигуры. Проективная геометрия изучает свойства, инвариантные относительно проецирования. Топология имеет дело со свойствами, которые сохраняются неизменными, когда фигура претерпевает сколь угодно сильные искажения без разрывов и склеиваний, аналогичные деформациям фигуры, изготовленной из гибкого, растяжимого и прочного материала.
Хотя геометрические мотивы встречаются во всех главах нашей книги, в этой главе мы собрали задачи, в которых геометрический аспект имеет явное преимущество перед всеми остальными. При отборе предпочтение отдавалось таким задачам, которые при надлежащем подходе (и «везении») допускают простые и ясные решения. Первая же задача — о разрезании сыра — отчетливо показывает, как тесно переплетаются даже в простейших задачах «сферы влияния» самых различных разделов математики: ее можно рассматривать как задачу по планиметрии, стереометрии, комбинаторике, теории чисел. В этой же задаче нетрудно усмотреть и зачатки исчисления конечных разностей.
«Пасутся кони на другом поле», как ни странно, — топологическая задача. Метод нитей и пуговиц позволяет свести ее к задаче о точках на простой замкнутой кривой. Форма замкнутой кривой для решения задачи не имеет ни малейшего значения — важны лишь топологические свойства кривой. Мы приводим решение задачи для случая, когда точки расположены на окружности, но с тем же успехом мы могли взять кривую, образующую периметр квадрата или треугольника.
Следующие две задачи («Невиданный меч» и «Пари на полюсе») снова выводят нас из плоскости в евклидову геометрию трехмерного пространства. При взгляде на маршруты полетов невольно вспоминается другая знаменитая задача о путях — задача о четырех черепахах. На ее примере мы видим, что иногда простые идеи позволяют избежать применения несравненно более сложных методов математического анализа. Задача об искусном землемере Рэнсоме возвращает нас на плоскость и знакомит с такими главами евклидовой геометрии, как теория разрезаний и разбиений. Задачи на разбиение земельных участков относятся к так называемой комбинаторной геометрии плоскости. Задача мисс Евклид о разрезании куба принадлежит к комбинаторной геометрии пространства.
Задача о ковровом покрытии для кольцевого коридора и ее трехмерный аналог — задача о просверленной насквозь сфере — могут служить прекрасными примерами того, как некая величина, которая, казалось бы, должна изменяться в зависимости от значений других параметров, в действительности принимает лишь одно значение. Кто мог бы ожидать, что при просверливании в сфере сквозного цилиндрического канала заданной длины объем оставшейся части сферы при постоянной длине канала не зависит ни от радиуса сферы, ни от диаметра канала? Впервые столкнувшись с теоремой о таком удивительном постоянстве, математик выразит свое изумление и почти заведомо скажет: «Красивый результат!»
Что именно имеют в виду математики, называя теорему или формулу красивой, точно не известно. Красота в их понимании каким-то образом связана с неожиданной простотой, но сколь ни трудно объяснить, в чем состоит эстетическая привлекательность математического утверждения, все математики умеют отличать красивую теорему или изящное доказательство с такой же легкостью, с какой мы отличаем красавицу от дурнушки. Геометрия, изучающая объекты, доступные не только мысленному взору, но и непосредственному созерцанию, необычайно богата красивыми теоремами и доказательствами. Некоторые из них вы встретите в этой главе.
Как разделить головку сыра
Кухня в ресторане «У Джо» оставляет желать лучшего, зато выбор сыров у Джо отменный.
Цилиндрическая головка сыра таит в себе немало интересных задач на разрезание. Проведя лишь 1 прямолинейный разрез, ее нетрудно разделить на 2 одинаковые части.
Два прямолинейных разреза позволяют разделить головку сыра на 4 одинаковые части, а 3 прямолинейных разреза — на 6 равных частей.
Однажды официантка Рози попросила Джо разрезать сыр на 8 одинаковых частей.
Джо. Хорошо, Рози. Сделать это совсем нетрудно. Я разделю сыр на 8 одинаковых частей четырьмя прямолинейными разрезами.
Подавая сыр на стол, Рози вдруг поняла, что Джо мог действовать и более экономно: чтобы разделить головку на 8 одинаковых частей, достаточно провести лишь 3 прямолинейных разреза.
Как это сделать?
Рози пришло в голову, что цилиндрическая головка сыра представляет собой не плоскую фигуру, а тело, которое можно разрезать по горизонтальной плоскости, проходящей через его центр. На рис. 1 показано, как тремя разрезами разделить сыр на 8 одинаковых порций. В этом решении предполагается, что все три разреза проведены одновременно. Если же разрезы проводить последовательно, один за другим, и перед каждым разрезом переставлять куски сыра наиболее удобным образом, то тремя разрезами сыр можно разрезать по-другому (так, как он разрезан^на подносе в руках Рози): для этого один из двух кусков, получившихся после первого разреза, нужно поставить на другой, провести еще один разрез, взять одну из «двухэтажных» половин, поставить на другую и провести третий разрез. После третьего разреза головка сыра окажется разделенной на 8 одинаковых порций.
Решение Рози столь просто, что кажется почти травиальным, и тем не менее оно может служить хорошим введением в серию важных задач на разрезание, теория которых связана с исчислением конечных разностей, а многие доказательства проводятся методом математической индукции. Конечные разности служат мощным средством получения формул общих членов числовых последовательностей. Интерес к числовом последовательностям неуклонно возрастает, что объясняется по крайней мере двумя причинами: во-первых, тем, что числовые последовательности встречаются во многих числовых задачах, и, во-вторых, быстротой, с которой ЭВМ позволяют производить над числовыми последовательностями любые действия.