Есть идея!

…положить 55 отобранных пилюль на одну чашу весов и взвесить их. Предположим, что пилюли весили бы 5510 мг, или на 10 мг больше, чем следует. Тогда мисс Блек заключила бы, что среди отобранных пилюль имеется 1 пилюля с повышенной дозой лекарства, а ровно 1 пилюля была извлечена из первого флакона.

Если бы вес 55 пилюль оказался на 20 мг больше нормы, то это означало бы, что среди отобранных пилюль имеются 2 пилюли с повышенной дозой лекарства. Их можно было извлечь только из второго флакона. Так мисс Блек сумела понизить число взвешиваний до 1. Меньше не бывает!

Большой переполох в аптеке

Через 6 месяцев в аптеку доставили еще 10 флаконов того же лекарства. И на этот раз не успели распаковать коробку с флаконами, как почтальон принес телеграмму с извещением о том, что на этот раз фармацевт допустил более серьезную ошибку.

В посылке могло оказаться от 1 до 10 флаконов с пилюлями, каждая из которых на 10 мг тяжелее нормы. Мистер Уайт был вне себя от ярости.

Мистер Уайт. Что делать, мисс Блек? Ваш метод, который позволил нам так блестяще выйти из затруднения в прошлый раз, неприменим!

Мисс Блек задумалась.

Мисс Блек. Вы правы, мистер Уайт. Но если слегка модифицировать мой метод, то при помощи 1 взвешивания и на этот раз можно определить, в каких флаконах пилюли содержат повышенную дозу лекарства.

Что имела в виду мисс Блек?

Как определить непригодные пилюли?

По условиям первой задачи на взвешивание пилюль все более тяжелые пилюли находятся в одном флаконе. Взяв из различных флаконов различное число пилюль (проще всего взять из каждого флакона число пилюль, равное его номеру), мы установим взаимно-однозначное соответствие между множеством номеров и множеством флаконов.

Чтобы решить вторую задачу, необходимо воспользоваться последовательностью, которая бы сопоставляла каждому флакону отличный от других номер и обладала бы еще одним дополнительным свойством: сумма членов любой ее подпоследовательности должна быть отличной от суммы членов любой другой ее подпоследовательности. Существуют ли такие последовательности? Да, существуют. Примером может служить хотя бы геометрическая прогрессия со знаменателем 2 и первым членом 1: 1, 2, 4, 8, 16… Все члены этой последовательности — степени числа 2, причем показатель возрастает от 0 с единичным шагом. Именно эта последовательность лежит в основе двоичной системы счисления.

Решение задачи состоит в том, чтобы, выстроив флаконы в ряд, взять 1 пилюлю из первого флакона, 2 пилюли из второго флакона, 4 пилюли из третьего флакона и т. д., затем собрать все отобранные пилюли и взвесить. Предположим, что пилюли оказались на 270 мг тяжелее, чем нужно. Так как каждая пилюля с повышенной дозой лекарства тяжелее нормальной на 10 мг, то, разделив 270 на 10, мы получим 27 — число более тяжелых пилюль.

Запишем число 27 в двоичной системе: 11011. Двоичные разряды, в которых стоят единицы, говорят нам, какие степени числа 2 в сумме дают двоичное число 11011 (или десятичное число 27): 1, 2, 8 и 16. Единицы стоят в первом, втором, четвертом и пятом двоичных разрядах. Следовательно, непригодные пилюли с повышенным содержанием лекарства находятся в первом, втором, четвертом и пятом флаконах.

Двоичная система счисления находит столь широкое применение именно потому, что каждое положительное целое число можно представить в виде суммы степеней числа 2 единственным способом. Без двоичной системы счисления в наши дни немыслима работа ЭВМ. Немалую роль двоичная система играет во многих областях прикладной математики. Почетное место отведено двоичной системе и в занимательной математике.

Вот простой карточный фокус, который позволит вам удивить и позабавить ваших друзей. Хотя внешне он ничем не напоминает задачу об отыскании флаконов с непригодными пилюлями, и задача, и фокус по существу «двоичны» — в основе их лежит двоичная система счисления.

Пусть кто-нибудь из зрителей тщательно перетасует колоду карт. Положив ее в карман, попросите вашего помощника назвать любое число от 1 до 15, после чего, сунув руку в карман, достаньте карты, значения которых в сумме равны названному числу (туз считается равным 1).

Секрет фокуса прост. Вы заранее кладете в карман туз, двойку, четверку и восьмерку. Определить на глаз недостачу четырех карт в колоде невозможно, и ваши зрители будут пребывать в уверенности, что вы попросили перетасовать полную колоду. Перетасованную колоду вы подкладываете под четыре карты, уже лежащие в кармане. После того как число названо, вы мысленно представляете его в виде суммы степеней числа 2 (например, если названо число 10, то вы мысленно разлагаете его в сумму 8 + 2=10) и, сунув руку в карман, достаете двойку и восьмерку.

На том же двоичном принципе построены и карточки «для чтения мыслей на расстоянии». На рис. 1 из гл. 3 показаны 6 карт, позволяющие безошибочно отгадывать любое задуманное число от 1 до 63. Попросите кого-нибудь, задумав любое число в этом диапазоне (например, свой возраст), отобрать и вручить вам все карточки, на которых оно встречается, и вы немедленно назовете задуманное число. Секрет этого фокуса также прост: вы просто суммируете степени числа 2, стоящие в левом верхнем углу каждой таблицы. Например, если были отобраны и вручены вам таблицы C и F, то вы суммируете числа 4 и 32 и узнаете, что было задумано число 36.

По какому принципу выбраны числа на каждой карточке? Каждое число, имеющее в двоичной записи единицу в первом разряде справа, заносится в таблицу A. Следовательно, в эту таблицу вписаны все нечетные числа от 1 до 63. В карточку B заносятся все числа, имеющие в двоичной записи единицу во втором разряде справа, в карточку C — все числа, имеющие единицу в третьем разряде справа и т. д. Заметим, что число 63 в двоичной системе записывается как 111111, то есть имеет единицы во всех шести разрядах, и поэтому встречается на всех шести карточках.

Иногда фокусники придают этому фокусу налет таинственности, окрашивая карточки в различные цвета и запоминая, какой цвет соответствует той или иной степени числа 2. Пусть, например, красная карточка означает 1, оранжевая — 2, желтая — 4, зеленая — 8, голубая — 16 и фиолетовая — 32 (мы выбрали 6 цветов радуги по порядку, пропустив синий). Фокусник становится в дальнем конце комнаты и просит кого-нибудь из зрителей отложить в сторону карточки, на которых встречается задуманное число. По цвету отложенных карточек фокусник без промедления может назвать задуманное число.

Распиленный браслет

Однажды юная Глория из Арканзаса отправилась в Калифорнию. Ей необходимо было снять на неделю номер в гостинице.

Портье в гостинице встретил ее весьма нелюбезно.

Портье. Могу предложить только номер за 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 одинаковых порций.

Решение Рози столь просто, что кажется почти травиальным, и тем не менее оно может служить хорошим введением в серию важных задач на разрезание, теория которых связана с исчислением конечных разностей, а многие доказательства проводятся методом математической индукции. Конечные разности служат мощным средством получения формул общих членов числовых последовательностей. Интерес к числовом последовательностям неуклонно возрастает, что объясняется по крайней мере двумя причинами: во-первых, тем, что числовые последовательности встречаются во многих числовых задачах, и, во-вторых, быстротой, с которой ЭВМ позволяют производить над числовыми последовательностями любые действия.

Изобретенный Рози первый метод разрезания сыра (без перекладывания кусков) состоит в проведении прямолинейных или, лучше сказать, плоских разрезу проходящих через центр верхнего основания готовки сыра, плоского, как у круглого пирога. Выясним, какие числовые последовательности может порождать разрезание верхней поверхности сыра прямыми, пересекающимися в центре (ясно, что n одновременно проведенных разрезов позволяют разделить сыр не более чем на 2n кусков).

Можно ли считать, что 2n — максимальное число частей, на которые n прямых, проходящих через одну точку, могут разделить любую плоскую фигуру, ограниченную простой замкнутой кривой? Нет: нетрудно построить невыпуклую фигуру (например, такую, как на рис. 2), которую одной прямой можно разделить на значительно большее число частей. А можно ли построить фигуру, которую одной прямой можно было бы разделить на любое конечное число конгруэнтных частей? Если да, то какими свойствами должен обладать периметр фигуры, чтобы одной прямой от нее можно было отсечь п конгруэнтных частей?

Задача о разрезании пирога или сыра становится еще более интересной, когда линии разреза не пересекаются в одной точке. Нетрудно видеть, что начиная си = 3 при таком способе разрезания исходный круг будет распадаться более чем на 2n частей (пока нас не интересует, будут ли эти части конгруэнтными или равновеликими). На рис. 3 показано, каким образом достигается максимальное число частей при числе разрезов n, равном 1, 2, 3 и 4 (круг делится соответственно на 2, 4, 7 и 11 частей).

Числа 2, 4, 7 и 11 образуют отрезок известной последовательности с общим членом, задаваемым формулой

где n — число разрезов. Полагая п = 0, 1, 2, …, 9, получаем первые десять членов последовательности: 1, 2, 4, 7, 11, 16, 22, 29, 37, 46…. Первые разности равны 1, 2, 3, 4, 5, 6, 7, 8, 9, …, вторые разности равны 1, 1, 1, 1, 1, 1, 1, 1, … . Постоянство вторых разностей основательно подкрепляет нашу догадку о тем, что общий член этой последовательности квадратичен по n.

Мы говорим о догадке потому, что формула, получаемая при помощи конечных разностей, может оказаться «ограниченно применимой» — порождать лишь часть членов бесконечной последовательности. Применимость формулы «конечно-разностного происхождения» ко всем без исключения членам числовой последовательности каждый раз необходимо доказывать особо. В случае круглого пирога такое доказательстве действительно существует. Его нетрудно найти, если воспользоваться методом математической индукции.

После этих замечаний, носящих сугубо предварительный характер, вы достаточно вооружены, чтобы смело вступить на неизведанную территорию и проложить по ней десятки увлекательных маршрутов в самых разных направлениях, многие из которых приводят к необычным числовым последовательностям, формулам и доказательствам методом математической индукции. Определить максимальное число частей, на которые можно разделить:

1) подковообразный пирог n прямыми;

2) головку сыра в форме шара или цилиндра n плоскими разрезами;

3) пирог n круговыми разрезами, проводимыми специальным ножом;

4) пирог, испеченный в форме кольца (с круглым отверстием посредине) n прямыми;

5) бублик (тор) n плоскими разрезами.

Во всех этих задачах предполагается, что разрезы проводятся одновременно. Как изменятся ответы, если будет разрешено проводить разрезы последовательно и после каждого разреза перекладывать образовавшиеся куски?

Невидимые размеры

В центре городского парка находится, круглая площадка для игр. Магистрат вознамерился устроить на этой площадке бассейн в форме ромба.

Мэр города Дорис Райт, рассмотрев представленные архитектором проекты, высказала свое мнение.

Мэр Райт. Мне нравится вот этот проект бассейна, облицованного красным кафелем. Какова длина каждой стороны ромба?