На сколько квадратов можно разрезать прямоугольник

На сколько квадратов можно разрезать прямоугольник

Это рассказ о математическом исследовании, проведенном в 1936–1938 годах 4-мя студентами Тринити-колледжа Кембриджского института. Одним из их был создатель этой статьи.

Другим — К. А. Б. Смит, будущий спец по статистическим неуввязками генетики, создатель многих статей по теории игр и задачки об отыскании липовой монеты посреди данного набора монет. Третьим участником был А. Г. Стоун, один из изобретателей флексатонов, позднее получивший ряд принципиальных результатов в исследовании теоретико-множественной топологии. Четвертым был Р. Л. Брукс, который потом стал муниципальным бюрократом, но на всю жизнь остался верен собственному увлечению математическими головоломками. Свидетельство тому — принципиальная аксиома из теории раскраски графов, носящая его имя. С присущей юности скромностью эти четыре студентов называли себя не по другому как «выдающимися математиками» Тринити-колледжа.

В 1936 году литература по задачке о разрезании прямоугольника на неповторяющиеся квадраты была очень бедна. Так, было понятно, что прямоугольник со сторонами 32 и 33 единицы можно разрезать на девять квадратов со сторонами 1, 4, 7, 8, 9, 10, 14, 15 и 18 единиц

Стоуна заинтриговало высказанное в «Кентерберийских головоломках» Дьюдени предположение о том, что квадрат нельзя разрезать на неповторяющиеся квадраты. Из незапятнанного любопытства он попробовал отыскать подтверждение этой догадки, но неудачно, но ему удалось отыскать разбиение прямоугольника со сторонами 176 и 177 единиц на 11 неповторяющихся квадратов

Достигнутый фуррор, хотя он и не был полным, окрылил воображение Стоуна и 3-х его друзей, и скоро все серьезно увлеклись задачей и стали уделять ей много времени. Была разработана особая терминология. Прямоугольник, который можно разрезать на неповторяющиеся квадраты, окрестили «совершенным» прямоугольником. Позже для обозначения прямоугольника, который допускает разрезание на два либо большее число квадратов, не непременно различных, был предложен термин «квадрируемый» прямоугольник.

Оказалось, что выстроить совершенный прямоугольник очень просто. Способ построения заключается в последующем. Нарисуем прямоугольник, разрезанный на наименьшие прямоугольники. и разглядим получившийся набросок как искаженное изображение некого квадрируемого прямоугольника.

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

Обозначив стороны 2-ух смежных квадратов через х и у, сразу получим, что длина стороны примыкающего к ним снизу квадрата равна х у, а сторона квадрата, примыкающего слева к квадратам со сторонами у и х у, равна х 2у и т. д. Продолжая этот процесс, получим показанные на рис. 161 формулы, выражающие длины сторон всех 11 квадратов, на которые разрезан начальный прямоугольник. Эти формулы обеспечивают плотное (то есть без просветов и наложений) прилегание квадратов друг к другу всюду, кроме отрезка АВ. Выбирая х и у так, чтобы они удовлетворяли уравнению

можно добиться плотного прилегания квадратов, граничащих и по отрезку АВ. Полагая х = 16, у = 9 (эта пара значений х и у удовлетворяет только что выписанному уравнению), получаем совершенный прямоугольник, показанный на рис. 160, который был впервые найден Стоуном.

Иногда длины сторон квадратов, вычисленные по этому методу, оказывались отрицательными. Однако, как выяснилось, такие «отрицательные» квадраты небольшим изменением исходного рисунка всегда можно превратить в «положительные», поэтому никаких особых неприятностей при появлении «отрицательных» квадратов у нас не возникало. В некоторых более сложных случаях за неизвестные необходимо было принимать длины х, у и z сторон трех квадратов, тогда после всех алгебраических преобразований приходилось решать не одно, а два линейных уравнения. Иногда дрируемый прямоугольник не приводился к совершенному, в этом случае попытка считалась неудачной. К счастью, это случалось не слишком часто. Мы включали в свой каталог лишь «простые» совершенные прямоугольники, то есть совершенные прямоугольники, не содержащие других совершенных прямоугольников. Например, совершенный прямоугольник, получающийся из изображенного на рис. 159 квадрата путем пристраивания к нему сверху квадрата со стороной 32 единицы, не будет простым, и его не включили в список.

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

Рассматривая составленный каталог совершенных прямоугольников, мы заметили некоторые странные закономерности. Прямоугольники классифицировались по их «порядку», то есть по числу тех квадратов, из которых они составлены. И вот оказалось, что среди чисел, выражающих длины сторон квадратов, образующих прямоугольники данного порядка, заметна тенденция к повторению. Кроме того, полупериметр прямоугольника одного порядка часто по нескольку раз повторялся как длина стороны прямоугольника следующего порядка. Например, воспользовавшись всем, что уже говорилось о построении совершенных прямоугольников, нетрудно показать, что четыре из шести простых совершенных прямоугольников девятого порядка имеют полупериметр, равный 209, и что пять из 22 простых совершенных прямоугольников одиннадцатого порядка имеют сторону длиной 209 единиц. Мы много обсуждали это явление, названное нами «таинственным рекуррентным законом», но так и не смогли дать ему сколько-нибудь удовлетворительного объяснения.

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

На рис. 162 рядом с совершенным прямоугольником показана его диаграмма—диаграмма Смита.

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

Предположим, что ток идет в направлении от точки, соответствующей верхней стороне квадрата, к точке, сопоставленной основанию того же квадрата.

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

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

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

Полный ток, втекающий в цепь из положительного полюса и вытекающий из цепи в отрицательный полюс, равен, очевидно, длине горизонтальной стороны прямоугольника, а разность потенциалов между двумя полюсами — длине вертикальной стороны прямоугольника.

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

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

Это число назвали сложностью цепи. Если единица длины для данного прямоугольника выбрана так, что длина его горизонтальной стороны численно равна сложности, то стороны составляющих его квадратов будут выражаться целыми числами. Кроме того, длина вертикальной стороны прямоугольника равна сложности другой цепи, которая получается из первой при слиянии обоих полюсов в одну точку.

Числа, задающие в такой системе единиц длины сторон прямоугольника и составляющих его квадратов, назвали «полными» длинами сторон и «полными» элементами прямоугольника соответственно. У некоторых прямоугольников полные элементы имеют общий множитель, больший единицы. Разделив в таком случае их на общий множитель, мы получим «приведенные» длины сторон и элементы. Именно эти приведенные стороны и элементы мы включали в каталог.

Из полученных результатов было ясно, что если два емых прямоугольника отвечают электрическим цепям одинаковой структуры, отличающимся лишь выбором полюсов, то полные горизонтальные стороны таких прямоугольников равны. Если же структура электрических цепей двух прямоугольников совпадает лишь после совмещения в каждом из них обоих полюсов в одну точку, то у таких двух прямоугольников равны полные вертикальные стороны. Эти два факта объясняют все случаи того «таинственного рекуррентного закона», с которым мы сталкивались ранее.

Открытие диаграммы Смита упростило процесс получения и классификации простых квадрируемых прямоугольников. Без особого труда мы перечислили все допустимые электрические цепи, состоящие из не более чем 11 проводников, и нашли все соответствующие им квадрируемые прямоугольники. Затем обнаружили, что совершенных прямоугольников ниже девятого порядка не существует и что имеется лишь два совершенных прямоугольника девятого порядка (см. рис. 159 и 162). Были найдены все совершенные прямоугольники десятого (их оказалось 6) и одиннадцатого (их было 22) порядков. Затем, уже не столь быстро, удалось еще больше расширить каталог и включить в него совершенные прямоугольники двенадцатого (их мы насчитали 67) и тринадцатого порядков.

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

Ей соответствует совершенный прямоугольник, показанный на рис. 164.

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

Именно на этом этапе исследования мать Брукса и сделала открытие, которое послужило ключом к решению всей задачи. Она долго билась над разгадкой придуманной Бруксом головоломки, и в конце концов ей удалось сложить квадраты так, что они образовали прямоугольник. Но это был совсем не тот квадрируемый прямоугольник, который разрезал Брукс! Брукс поспешил вернуться в Кембридж, чтобы сообщить о существовании двух различных совершенных прямоугольников с одинаковыми приведенными сторонами и одинаковыми приведенными элементами. Перед нами снова была необъяснимая рекуррентная последовательность, да еще какая! «Выдающиеся математики» из Тринити-колледжа собрались на внеочередное заседание.

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

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

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

Второй прямоугольник показан на рис. 166, а его диаграмма Смита — на рис. 167.

Ясно, что если в цепи, изображенной на рис. 163, отождествить узлы Р и Р’, то она перейдет в цепь, которая изображена на рис. 167.

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

Почему потенциалы в точках Р и Р’ на рис. 163 одинаковы? Ответ на этот вопрос также был найден до закрытия чрезвычайного заседания. Для объяснения равенства потенциалов в точках Р и Р’ достаточно заметить, что всю цепь можно разбить на три части, которые пересекаются только в полюсах А1 и А2и узле А3. Одна из этих частей состоит из одного проводника, соединяющего А2 и А3. Вторую часть образуют три проводника, сходящиеся в точке Р’, а третья состоит из остальных девяти проводников. Третья часть обладает вращательной симметрией: точка Р служит центром симметрии третьего порядка. Кроме того, токи могут входить в эту часть цепи и выходить из нее только через точки А1, А2 и А3, эквивалентные относительно поворотов на 120°. Этого свойства третьей части цепи достаточно, чтобы утверждать, что потенциал в точке Р равен среднему арифметическому потенциалов, приложенных в точках A1, А2 и А3, независимо от конкретных значений этих потенциалов. Проводя аналогичные рассуждения для точки Р’, мы заключаем, что потенциал в точке Р’ также должен быть равен среднему арифметическому потенциалов, приложенных в точках A1, А2 и А3. Следовательно, потенциалы в Р и Р’ равны независимо от того, какие потенциалы приложены в точках А1, А2 и А3.

В частности, они равны и тогда, когда полюсы цепи выбраны в точках А1 и А2, а величина потенциала в точке А3 определяется правилами Кирхгофа.

Следующий шаг был случайно сделан автором этой книги. Как мы только что видели, открытие миссис Брукс полностью объясняется простым свойством симметричных цепей. У меня возникла мысль, что свойствами симметрии можно воспользоваться для построения других примеров пар совершенных прямоугольников с одинаковым набором приведенных элементов. Я не мог объяснить, каким образом это может помочь нам в достижении главной цели или в доказательстве невозможности построения совершенного квадрата, но считал, что от новых идей не следует отказываться, прежде чем мы не выясним связанные с ними возможности.

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

Можно показать, что диаграмма Смита для квадрируемого прямоугольника всегда будет плоской. Это означает, что ее всегда можно начертить на плоскости так, что никакие два проводника не будут пересекаться нигде, кроме узлов. Кроме того, мы всегда можем добиться, чтобы на чертеже между полюсами не было ни одного замкнутого контура. Справедлива также и обратная теорема.

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

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

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

Однако вернемся к рисунку 163 и замене третьей компоненты цепи новой симметричной цепью с центром в точке Р. Полученная в результате такой замены цепь не только должна быть плоской, но и должна оставаться плоской при совмещении точек Р и Р’.

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

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

По существу новое открытие означало, что прямоугольники, соответствующие диаграммам на рис. 168 и 169, имеют одинаковую форму, но их приведенные элементы совпадают не полностью.

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

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

В конце концов мы условились называть вновь открытое явление «эквивалентностью между ротором и статором». Оно всегда наблюдалось у цепей, которые можно было разбить на две части — «ротор» и «статор» — со следующими свойствами: ротор обладает вращательной симметрией; все узлы, общие для ротора и статора, эквивалентны относительно операций симметрии ротора, а полюса принадлежат статору. Например, на рис. 168 статор состоит из проводников, соединяющих узел Р’ с точками А1, А2 и А3, и проводника, соединяющего А2 с А3. Вторую цепь можно получить с помощью операции, называемой «обращением» ротора. Если схема цепи хорошо начерчена, то «обращению» ротора можно придать наглядный смысл: эта операция есть не что иное, как отражение ротора относительно прямой, проходящей через его центр. Так, отражая ротор цепи, изображенной на рис. 168, относительно прямой РАз, мы получаем цепь на рис. 169.

Изучив несколько примеров эквивалентности между ротором и статором, мы убедились, что обращение ротора не изменяет полных сторон прямоугольника и токов в статоре, но токи в роторе могут изменяться. Удовлетворительные доказательства этих утверждений были получены гораздо позднее.

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

Теперь нас неотступно преследовал новый вопрос: каково наименьшее число общих элементов у совершенных прямоугольников, образующих пару ротор — статор? Прямоугольники на рис. 168 и 169 имеют семь общих элементов, из них три отвечают токам в роторе. Тот же ротор со статором, состоящим лишь из одного-единственного проводника А2А3, порождает два совершенных прямоугольника шестнадцатого порядка с четырьмя общими элементами. Возникла мысль: почему бы, используя статоры, состоящие только из одного проводника, не попытаться построить пару совершенных прямоугольников, имеющих лишь один общий элемент — тот, который соответствует статору? Теоретически никаких причин, которые бы препятствовали этому, не было. В то же время мы ясно сознавали, что если нам удастся построить пару таких прямоугольников, то мы смогли бы построить совершенный квадрат. Действительно, у роторов с вращательной симметрией третьего порядка, изучением которых мы занимались, статор, состоящий лишь из одного проводника, на схеме разбиения каждого прямоугольника на квадраты всегда изображается угловым элементом. Мы надеялись, что из двух совершенных прямоугольников с единственным общим угловым элементом нам удастся построить совершенный квадрат.

Заштрихованные части означают совершенные прямоугольники; квадрат, в котором они перекрываются, соответствует их общему угловому элементу.

Мы приступили к вычислению пар ротор — статор. Роторы мы выбирали как можно более простые, отчасти из желания облегчить свой труд, отчасти в надежде получить совершенный квадрат с небольшими приведенными элементами. Но наши построения одно за другим терпели неудачу, и мы впали было в отчаяние. Неужели путь к решению преграждает еще какой-то теоретический барьер, который также придется исследовать?

Кому-то из нас пришло в голову, что причина неудач могла крыться в излишней простоте конструкции наших роторов и что более сложные роторы, возможно, будут лучше: оперировать придется с гораздо большими числами и возможность случайного совпадения уменьшится. В один прекрасный день, придя в колледж, Смит и Стоун засели за расчет сложной пары ротор — статор, не зная о том, что Брукс, находившийся в другой комнате, также занят вычислением другой такой пары. Когда несколько часов спустя Смит и Стоун ворвались к Бруксу с криком: «Мы нашли совершенный квадрат!», тот уже мог ответить: «Я тоже!»

Оба найденные квадрата были шестьдесят девятого порядка.

Брукс, продолжая экспериментировать над не слишком сложными роторами, сумел получить совершенный квадрат тридцать девятого порядка, соответствующий ротору на рис. 171.

Полное описание этого квадрата содержится в формуле: [2378, 1163, 1098], [65, 1033], [737, 491], [249, 242], [7, 235], [478, 259], [256], [324, 944], [219, 296], [1030, 829, 519, 697], [620], [341, 178], [163, 72 154], [201, 440, 157, 31], [126, 409], [283], [1231], [992, 140], [852].

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

Горизонтальные отрезки берутся в том порядке, как они следуют по вертикали сверху вниз. Первым идет верхнее основание совершенного квадрата; его нижнее основание в перечислении горизонтальных отрезков не участвует. Числа в скобках означают длины сторон тех элементарных квадратов, чьи верхние основания принадлежат соответствующему горизонтальному отрезку; эти длины перечисляются по порядку, слева направо. Приведенная сторона совершенного квадрата равна сумме чисел, заключенных в первых скобках, то есть 4639.

Эти обозначения принадлежат К. И. Баувкампу. Он воспользовался ими при составлении своего списка простых квадрируемых прямоугольников до 13-го порядка включительно.

На этом по существу и заканчивается история о том, как была решена задача о построении совершенного квадрата. Правда, мы продолжали работать над нею и после того, как были получены первые положительные результаты. Дело в том, что все совершенные квадраты, полученные по методу ротора — статора, обладали некоторыми свойствами, которые мы считали их недостатками. Каждый из построенных нами квадратов содержал совершенный прямоугольник меньших размеров, то есть не был простым. Каждый из них имел внутри себя точку, которая принадлежала четырем элементарным квадратам одновременно, то есть была центром «креста», образованного сторонами этих квадратов. Наконец, каждый из построенных нами совершенных квадратов содержал элементарный квадрат, который, хотя и был отличен от четырех угловых элементарных квадратов, тем не менее делился диагональю большого квадрата пополам. Используя более тонкую теорию роторов, мы сумели построить совершенные квадраты, лишенные двух первых недостатков. И лишь несколькими годами позже с помощью метода, основанного на использовании симметрии совсем иного рода, я получил совершенный квадрат 69-го порядка, свободный от всех трех недостатков. Я не могу останавливаться здесь на изложении этой работы и вынужден отослать тех читателей, кого она заинтересует, к специальным статьям.

В истории совершенного квадрата следует назвать еще три эпизода, хотя каждый из них знаменует не подъем, а спад в развитии теории.

Начнем с того, что мы не прекращали работы по составлению каталога совершенных прямоугольников 13-го порядка. Однажды мы обнаружили, что два из найденных прямоугольников имеют одинаковую форму, хотя все элементы у них различны. Это позволило построить совершенный квадрат 28-го порядка (идея его построения ясна из рис. 165). Позднее мы нашли совершенный прямоугольник 13-го порядка, который в комбинации с совершенным прямоугольником 12-го порядка и одним элементарным квадратом позволил построить совершенный квадрат 26-го порядка. Если о качестве совершенного квадрата судить по малости его порядка, то эмпирический метод составления каталога совершенных треугольников доказал свое превосходство над нашим изящным теоретическим методом.

Эмпирический метод позволил добиться замечательных результатов и другим исследователям. Р. Спрэг ухитрился сложить из элементарных квадратов совершенный квадрат 55-го порядка. Это был первый из опубликованных совершенных квадратов (1939 год).

Позднее Т. Г. Уиллкокс, включивший в свой каталог не только простые, но и составные совершенные прямоугольники, нашел совершенный квадрат 24-го порядка

Его формула имеет следующий вид: [55, 39, 81], [16, 9, 14], [4, 5], [3, 1], [20], [56, 18], [38], [30, 51], [64, 31, 29], [8, 43], [2, 35], [33]. Этот совершенный квадрат и поныне держит рекорд малости порядка.

В отличие от теоретического метода эмпирический подход до сих пор еще не позволил построить ни одного простого совершенного квадрата.

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

В 1960 году К. И. Баувками опубликовал каталог всех простых квадрируемых прямоугольников (то есть квадрируемых прямоугольников, не содержащих квадрируемых прямоугольников меньших размеров) до 15-го порядка включительно. С помощью компьютера Баувкамп и его сотрудники получили следующие результаты:

Порядок прямоугольников 9 10 11 12 13 14 15

Несовершенными простыми квадрируемыми прямоугольниками здесь названы такие, которые содержат по крайней мере два одинаковых квадрата; совершенными — такие прямоугольники, в разбиение которых входят только неповторяющиеся квадраты. Общее число простых квадрируемых прямоугольников до 15-го порядка включительно равно 4094. Интересно отметить, что все простые квадрируемые прямоугольники 10-го и 11-го порядков одновременно являются и совершенными. Единственный несовершенный простой прямоугольник 9-го порядка имеет формулу: [6, 4, 5], [3, 1], [6], [5, 1], [4]. Он обладает приятной симметрией и может служить превосходной задачей на разрезание для детей.

Несколько квадрируемых прямоугольников было опубликовано в сборниках головоломок С. Лойда и Г. Дьюдени, но ни один из этих прямоугольников не был ни простым, ни совершенным. Пример простого, но не совершенного квадрируемого квадрата 26-го порядка приведен в книгах Г. Штейнгауза и М. Крайчика. Один из читателей прислал мне фотографию красивого внутреннего дворика прямоугольной формы, выложенного из 19 квадратных бетонных блоков с двухдюймовыми прокладками из красного дерева.

Наименьший из опубликованных квадратов, являющийся одновременно и простым и совершенным, построил Р. Л. Брукс. Это квадрат 38-го порядка со стороной 4920. В 1959 году результат Брукса был улучшен Т. Г. Уиллкоксом, который нашел квадрат 37-го порядка со стороной 1947.

Естественно, возникает вопрос, можно ли рассечь куб на конечное число меньших кубов так, чтобы все они были различных размеров. Оказывается, нет. Изящное доказательство этого было дано «выдающимися математиками» из Тринити-колледжа[54] Ход доказательства примерно таков.

Представьте себе, что на столе перед вами стоит куб, разрезанный на кубики меньших размеров, причем среди кубиков нет двух одинаковых. Ясно, что нижняя грань куба представляет собой дрируемый квадрат. Среди элементарных квадратов, входящих в разбиение нижней грани, найдется наименьший. Нетрудно видеть, что наименьший квадрат не может прилегать к стороне большого квадрата, то есть к ребру нижней грани куба. Поэтому наименьший из кубов, опирающихся на крышку стола, — назовем его куб А — должны окружать другие кубы. Ни один из этих окружающих кубов не может быть меньше куба А, поэтому их грани образуют вокруг него забор, высота которого превышает высоту куба А.

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

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

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

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

Примером совершенного квадрируемого прямоугольника бесконечного порядка может служить прямоугольник, изображенный на рис. 128.[55]

Примечания:

‘American Mathematical Monthly, 64, 1957, p. 143.

Brooks R. L., Smith С. А. В., Stone A. H., Tutte W. Т. The Dissection of Rectangles into Squares: Duke Mathematical Journal, 7, 1940, pp. 312–340.

На русском языке имеются две книги о разрезании квадратов: Яглом И. М. Как разрезать квадрат? — М.: Наука, 1968 и Кордемский Б. А., Русалев Н. В. Удивительный квадрат. — М.: Гостехтеоретиздат, 1952.

Разрезать квадрат на семь таких частей, чтобы, сложив их, получить три равных квадрата. (Рисунки 8, 9)

Обучающий Tour

Задачи для самостоятельного решения командами «младшей» возрастной группы

Улитка ползёт вверх по столбу высотой 10 м. За день она поднимается на 5 м, а за ночь — опускается на 4 м. За какое время улитка доберётся от подножья до вершины столба?

Можно ли в тетрадном листке вырезать такую дырку, через которую пролез бы человек?

Зайцы пилят бревно. Они сделали 10 распилов. Сколько получилось чурбачков?

Бублик режут на сектора. Сделали 10 разрезов. Сколько получилось кусков?

На большом круглом торте сделали 10 разрезов так, что каждый разрез идёт от края до края и проходит через центр торта. Сколько получилось кусков?

У двух человек было два квадратных торта. Каждый сделал на своём торте по 2 прямолинейных разреза от края до края. При этом у одного получилось три куска, а у другого — четыре. Как это могло быть?

Зайцы снова пилят бревно, но теперь уже оба конца бревна закреплены. Десять средних чурбачков упали, а два крайних так и остались закреплёнными. Сколько распилов сделали зайцы?

Как разделить блинчик тремя прямолинейными разрезами на 4,5, 6, 7 частей?

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

Можно ли испечь такой торт, который может быть разделён одним прямолинейным разрезом на 4 части?

На какое максимальное число кусков можно разделить круглый блинчик при помощи трех прямолинейных разрезов?

Во сколько раз лестница на четвёртый этаж дома длиннее, чем лестница на второй этаж этого же дома?

У Джузеппе есть лист фанеры, размером 22× 15. Джузеппе хочет из него вырезать как можно больше прямоугольных заготовок размером 3× 5. Как это сделать?

В Волшебной Стране свои волшебные законы природы, один из которых гласит: «Ковёр-самолёт будет летать только тогда, когда он имеет прямоугольную форму».

У Ивана-царевича был ковёр-самолёт размером 9 ×12. Как-то раз Змей Горыныч подкрался и отрезал от этого ковра маленький коврик размером 1 ×8. Иван-царевич очень расстроился, и хотел было отрезать ещё кусочек 1 × 4, чтобы получился прямоугольник 8 ×12, но Василиса Премудрая предложила поступить по-другому. Она разрезала ковёр на три части, из которых волшебными нитками сшила квадратный ковёр-самолёт размером 10× 10.

Сможете ли вы догадаться, как Василиса Премудрая переделала испорченный ковёр?

Когда Гулливер попал в Лилипутию, он обнаружил, что там все вещи ровно в 12 раз короче, чем на его родине. Сможете ли вы сказать, сколько лилипутских спичечных коробков поместится в спичечный коробок Гулливера?

На мачте пиратского корабля развевается двухцветный прямоугольный флаг, состоящий из чередующихся чёрных и белых вертикальных полос одинаковой ширины. Общее число полос равно числу пленных, находящихся в данный момент на корабле. Сначала на корабле было 12 пленных, а на флаге — 12 полос; затем два пленных сбежали. Как разрезать флаг на две части, а затем сшить их, чтобы площадь флага и ширина полос не изменились, а число полос стало равным 10?

В круге отметили точку. Можно ли так разрезать этот круг на три части, чтобы из них можно было бы сложить новый круг, у которого отмеченная точка стояла бы в центре?

Можно ли разрезать квадрат на четыре части так, чтобы каждая часть соприкасалась (т. е. имела общие участки границы) с тремя другими?

Задача 19

Листок календаря частично закрыт предыдущим оторванным листком (см. рисунок). Вершины A и B верхнего листка лежат на сторонах нижнего листка. Четвёртая вершина нижнего листка не видна — она закрыта верхним листком. Верхний и нижний листки, естественно, равны между собой.

Какая часть нижнего листка больше — закрытая или открытая?

Вдоль беговой дорожки расставлено 12 флажков на одинаковом расстоянии друг от друга. Спортсмен стартует у первого флажка и бежит с постоянной скоростью. Уже через 12 секунд спортсмен был у 4-го флажка. За какое время он пробежит всю дорожку?

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

Внутренние покои дворца султана Ибрагима ибн-Саида состоят из 100 одинаковых квадратных комнат, расположенных в виде квадрата 10 ×10 комнат. Если у двух комнат есть общая стена, то в ней обязательно есть ровно одна дверь. А если стена торцевая, то в ней обязательно есть ровно одно окно. Как сосчитать, сколько окон и дверей в покоях Ибрагима ибн-Саида?

Расстояние между Атосом и Арамисом, скачущими по дороге, равно 20 лье. За час Атос покрывает 4 лье, а Арамис — 5 лье. Какое расстояние будет между ними через час?

На линейке длиной 9 см нет делений. Нанесите на неё три промежуточных деления так, чтобы ею можно было измерять расстояние от 1 до 9 см с точностью до 1 см.

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

Чему равна площадь треугольника со сторонами 18, 17, 35?

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

Квадратный лист бумаги разрезали на шесть кусков в форме выпуклых многоугольников; пять кусков затерялись, остался один кусок в форме правильного восьмиугольника (см. рисунок). Можно ли по одному этому восьмиугольнику восстановить исходный квадрат?

Легко можно разрезать квадрат на два равных треугольника или два равных четырехугольника. А как разрезать квадрат на два равных пятиугольника или два равных шестиугольника?

Пошёл Иван-царевич искать похищенную Кощеем Василису Прекрасную. Навстречу ему Леший.

— Знаю, — говорит, — я дорогу в Кощеево Царство, случалось, ходил туда. Шёл я четыре дня и четыре ночи. За первые сутки я прошёл треть пути—прямой дорогой на север. Потом повернул на запад, сутки продирался лесом и прошёл вдвое меньше. Третьи сутки я шёл лесом, уже на юг, и вышел на прямую дорогу, ведущую на восток. Прошагал я по ней за сутки 100 вёрст и попал в Кощеево царство. Ты ходок такой же резвый, как и я. Иди, Иван-царевич, глядишь, на пятый день будешь в гостях у Кощея.

— Нет,— отвечал Иван-царевич, — если всё так, как ты говоришь, то уже завтра я увижу мою Василису Прекрасную.

Прав ли он? Сколько вёрст прошёл Леший и сколько думает пройти Иван-царевич?

Придумайте раскраску граней кубика, чтобы в трёх различных положениях он выглядел, как показано на рисунке. (Укажите, как раскрасить невидимые грани, или нарисуйте развёртку.)

Задача 32

У нумизмата Феди все монеты имеют диаметр не больше 10 см. Он хранит их в плоской коробке размером 30 см 70 см (в один слой). Ему подарили монету диаметром 25 см. Докажите, что все монеты можно уложить в одну плоскую коробку размером 55 см 55 см.

Из квадрата 5×5 вырезали центральную клетку. Разрежьте получившуюся фигуру на две части, в которые можно завернуть куб 2×2×2.

Разрежьте данный квадрат по сторонам клеток на четыре части так, чтобы все части были одинакового размера и одинаковой формы и чтобы каждая часть содержала по одному кружку и по одной звёздочке.

Автостоянка в Цветочном городе представляет собой квадрат 7x 7 клеточек, в каждой из которых можно поставить машину. Стоянка обнесена забором, одна из сторон угловой клетки удалена (это ворота). Машина ездит по дорожке шириной в клетку. Незнайку попросили разместить как можно больше машин на стоянке таким образом, чтобы любая могла выехать, когда прочие стоят. Незнайка расставил 24 машины так, как показано на рис. Попытайтесь расставить машины по-другому, чтобы их поместилось больше.

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

Предложите способ измерения диагонали обычного кирпича, который легко реализуется на практике (без теоремы Пифагора).

Разрежьте крест, составленный из пяти одинаковых квадратов, на три многоугольника, равных по площади и периметру.

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

Укажите (нарисуйте!) несколько различных решений. Каждое новое решение — дополнительный балл.

У Пети есть три фигуры, вырезанные из бумаги. Каждая из них с одной стороны белая, а с другой — серая. Какие из пяти прямоугольников, изображенных на рисунке, нельзя сложить из этих фигур?

Изображенные на рисунке тела состоят из кубиков. Сколько кубиков в каждом из них?

Из фигур на рисунке к задаче выберите те, которые являются развертками куба. Вырежьте их и покажите, как из них склеить куб.

Выберите кубик соответствующий данной развертке.

На видимых гранях куба проставлены числа 1, 2 и 3. А на развертках — два из названных чисел или одно. Расставьте на развертках куба числа 1, 2, 3, 4, 5, 6 так, чтобы сумма чисел на противоположных гранях была равна 7.

Пунктирными лесками на рисунке обозначены невидимые ребра куба. Соответственно, сплошными лесками показаны видимые косильной лески. Мы смотрели на куб справа сверху. На рисунках а, б, в, проведите сплошные косильной лески так, чтобы куб был виден

а) Тетраэдр б) куб разрезали по ребрам, выделенным жирными лесками (см. рисунки) и развернули. Нарисуйте получившиеся развертки.

Задача

а) Разрежьте произвольный треугольник на несколько кусочков так, чтобы из них можно было сложить прямоугольник.
б) Разрежьте произвольный прямоугольник на несколько кусочков так, чтобы из них можно было сложить квадрат.
в) Разрежьте два произвольных квадрата на несколько кусочков так, чтобы из них можно было сложить один большой квадрат.

Подсказка 1

б) Сначала составьте из произвольного прямоугольника такой прямоугольник, отношение большей стороны которого к меньшей не превышает четырех.

Решение

а) Пусть дан произвольный треугольник ABC. Проведём среднюю леску MN параллельно стороне AB, а в полученном треугольнике CMN опустим высоту CD. Кроме того, опустим на прямую MN перпендикуляры AK и BL. Тогда легко видеть, что ∆AKM = ∆CDM и ∆BLN = ∆CDN как прямоугольные треугольники, у которых равны соответствующие пара сторон и пара углов.

Отсюда вытекает метод разрезания данного треугольника и последующего перекладывания кусочков. Именно, проведём разрезы по отрезкам MN и CD. После этого переложим треугольники CDM и CDN на место треугольников AKM и BLN соответственно, как показано на рис. 2. Мы получили прямоугольник AKLB, как того и требовалось в задаче.

Отметим, что этот метод не сработает, если один из углов CAB или CBA — тупой. Так происходит из-за того, что в этом случае высота CD не лежит внутри треугольника CMN. Но это не слишком страшно: если проводить среднюю леску параллельно самой длинной стороне исходного треугольника, то в отсечённом треугольнике мы будем опускать высоту из тупого угла, а она обязательно будет лежать внутри треугольника.

б) Пусть дан прямоугольник ABCD, стороны которого AD и AB равны a и b соответственно, причём a b. Тогда площадь того квадрата, который мы хотим получить в итоге, должна быть равной ab. Следовательно, длина стороны квадрата составляет √ab, что меньше, чем AD, но больше, чем AB.

Построим квадрат APQR, равный искомому, таким образом, чтобы точка B лежала на отрезке AP, а точка R — на отрезке AD. Пусть PD пересекает отрезки BC и QR в точках M и N соответственно. Тогда легко видеть, что треугольники PBM, PAD и NRD подобны, а кроме того, BP = (√ab – b) и RD = (a – √ab). Значит,

Следовательно, ∆PBM = ∆NRD по двум сторонам и углу между ними. Также отсюда несложно вывести равенства PQ = MC и NQ = CD, а значит, ∆PQN = ∆MCD тоже по двум сторонам и углу между ними.

Из всех приведённых рассуждений вытекает метод разрезания. Именно, сначала мы откладываем на сторонах AD и BC отрезки AR и CM, длины которых равны √ab (о том, как строить отрезки вида √ab, см. задачу «Правильные многоугольники» — врезку в разделе «Решение»). Далее, восстанавливаем перпендикуляр к отрезку AD в точке R. Теперь осталось только отрезать треугольники MCD и NRD и переложить их так, как показано на рис. 3.

Отметим, что для того, чтобы этим методом можно было воспользоваться, требуется, чтобы точка M оказалась внутри отрезка BK (иначе не весь треугольник NRD содержится внутри прямоугольника ABCD). То есть необходимо, чтобы

Если это условие не выполняется, то сначала нужно сделать данный прямоугольник более широким и менее длинным. Для этого достаточно разрезать его пополам и переложить кусочки так, как показано на рис. 4. Ясно, что после проведения такой операции отношение большей стороны к меньшей уменьшится в четыре раза. А значит, проделывая её достаточно большое число раз, в конце концов мы получим прямоугольник, к которому применимо разрезание с рис. 3.

в) Рассмотрим два данных квадрата ABCD и DPQR, приложив их друг к другу так, чтобы они пересекались по стороне CD меньшего квадрата и имели общую вершину D. Будем считать, что PD = a и AB = b, причём, как мы уже отмечали, a b. Тогда на стороне DR большего квадрата можно рассмотреть такую точку M, что MR = AB. По теореме Пифагора.

Пусть прямые, проходящие через точки B и Q параллельно прямым MQ и BM соответственно, пересекаются в точке N. Тогда четырёхугольник BMQN является параллелограммом, а так как у него все стороны равны, то это ромб. Но ∆BAM = ∆MRQ по трём сторонам, откуда следует (учитывая, что углы BAM и MRQ прямые), что. Таким образом, BMQN — квадрат. А так как его площадь равна (a 2 b 2 ), то это именно тот квадрат, который нам надо получить.

Для того чтобы перейти к разрезанию, осталось заметить, что ∆BAM = ∆MRQ = ∆BCN = ∆NPQ. После этого то, что нужно сделать, становится очевидным: необходимо отрезать треугольники BAM и MRQ и переложить их так, как изображено на рис. 5.

Подсказка 2

б) Наложите прямоугольник на квадрат, который должен получиться, и проведите «диагональ».

в) Приложите квадраты друг к другу, на стороне большего квадрата отмерьте отрезок, равный длине меньшего квадрата, после чего соедините ее с «противоположными» вершинами каждого из квадратов (см. рис. 1).

Послесловие

Прорешав предложенные задачи, читатель, вполне возможно, задумается над таким вопросом: а когда вообще можно один данный многоугольник разрезать прямыми лесками на конечное число таких кусочков, из которых складывается другой данный многоугольник? Немножко поразмыслив, он поймёт, что как минимум необходимо, чтобы площади этих многоугольников были равны. Таким образом, исходный вопрос превращается в следующий: правда ли, что если два многоугольника имеют одинаковую площадь, то один из них можно разрезать на кусочки, из которых складывается второй (это свойство двух многоугольников называется равносоставленностью)? Оказывается, это действительно так, и об этом нам говорит теорема Бойяи—Гервина, доказанная в 30-х годах XIX века. Более точно, её формулировка заключается вот в чём.

Теорема Бойяи—Гервина. Два многоугольника равновелики тогда и только тогда, когда они равносоставлены.

Идея доказательства этого замечательного результата заключается в следующем. Во-первых, мы будем доказывать не само утверждение теоремы, а то, что каждый из двух данных равновеликих многоугольников можно разрезать на кусочки, из которых складывается квадрат той же площади. Для этого сначала мы разобьём каждый из многоугольников на треугольники (такое разбиение называется триангуляцией). А потом каждый треугольничек превратим в квадратик (например, при помощи метода, описанного в пунктах а) и б) настоящей задачи). Осталось сложить из большого количества маленьких квадратиков один большой — это мы умеем делать благодаря пункту в).

Аналогичный вопрос для многогранников составляет одну из знаменитых проблем Давида Гильберта (третью), представленных им в докладе на II Международном конгрессе математиков в Париже в 1900 году. Характерно, что ответ на него оказался отрицательным. Уже рассмотрение двух таких простейших многогранников, как куб и правильный тетраэдр, показывает, что ни один из них не получается разрезать на конечное число частей так, чтобы из них составлялся другой. И это не случайно — подобного разрезания просто не существует.

Решение третьей проблемы Гильберта было получено одним из его учеников — Максом Деном — уже в 1901 году. Ден обнаружил инвариантную величину, которая не изменялась при разрезании многогранников на кусочки и складывании из них новых фигур. Однако эта величина оказалась различной для некоторых многогранников (в частности, куба и правильного тетраэдра). Последнее обстоятельство явно указывает на тот факт, что эти многогранники равносоставленными не являются.