Документ взят из кэша поисковой машины. Адрес оригинального документа : http://kvant.mccme.ru/pdf/2011/02/tabachnikov.pdf Дата изменения: Tue Oct 30 14:54:26 2012 Дата индексирования: Sun Feb 3 06:49:36 2013 Кодировка: Windows-1251 Поисковые слова: uv

Невозможные замощения
С.ТАБАЧНИКОВ, Д.ФУКС
Введение Эта статья посвящена замощениям плоских многоугольников при помощи других плоских многоугольников. Вот пример такой задачи, который, вероятно, известен читателю. Из шахматной доски вырезаны две угловые диагонально противоположные клетки (a1 и h8). Можно ли замостить полученную 'усеченРис.1. Можно ли замостить доми- ную' шахматную досношками шахматную доску без ку доминошками разугловых клеток? мера 2 Ч 1 ? Типичный фрагмент замощения доминошками показан на рисунке 2. Фигурки, составляющие замощение, не перекрываются (они касаются друг друга только по границе), и при этом каждая точка доски принадлежит какой-либо фигурке. Отметим два момента: во-первых, доминошки разрешается класть как вертикально, так и горизонтально; во-вторых, у соприкасающихся доминошек не обязательно должна быть цеРис.2. Фрагмент замолая общая сторона. Общая щения постановка задачи о замощении звучит так: если дан многоугольник P и набор многоугольников Q1, Q2,... , возможно ли замостить P копиями многоугольников Qi ? Читатель, которому не удалось решить задачу о шахматной доске без угловых клеток, сможет прочесть ее (отрицательное) решение в следующем разделе. Далее мы увидим множество других примеров невозможных замощений, но доказательства этой невозможности будут все более и более сложными. Раскраски Чтобы решить задачу о шахматной доске с вырезанными углами, вспомним, что поля шахматной доски окрашены в черный и белый цвета. Оба вырезанных диагонально противоположных угла черные, т.е. доска состоит из тридцати черных и тридцати двух белых полей (рис.3). С другой стороны, каждая доминошка размера 2 Ч 1 накрывает одно белое и одно черное поле.
Из книги: С.Табачников, Д.Фукс. Математический дивертисмент. М.: МЦНМО, 2011.

Значит, такое замощение невозможно. Вот другой способ изложить то же доказательство. Запишем на каждом белом поле нуль, а на каждом черном единицу. Общая сумма всех чисел на доске с вырезанными Рис.3. Рассуждение с испольуглами составляет 30. зованием раскраски Но на каждой доминошке написаны как 0, так и 1, и тридцать одна доминошка дает сумму 31, а не 30. Значит, такого замощения не существует. Вот вариация на ту же тему. Можно ли замостить квадрат 10 Ч 10 Г-образными фигурками, изображенными на рисунке 4. Заметим, что у каждой фигурки может быть восемь различных ориентаций! Ответ снова отрицательный. Запишем в клетках квадрата числа 1 и 5, как показано на рисунке 4. Рис.4. Раскраска по модулю 8 Каждая фигурка накрывает либо три единицы и одну пятерку, либо три пятерки и одну единицу. В любом из этих случаев сумма чисел на фигурке кратна 8. С другой стороны, общая сумма чисел на доске равна 300, что на 8 не делится. Значит, такого замощения не существует. Когда раскраски не помогают Предположим, что у нас есть два типа фигурок: обычные, положительные, фигурки и отрицательные фигурки, сделанные из 'антивещества'. Нам разрешается накладывать фигурки друг на друга, и при этом общие части положительных и Рис.5. Фигурки и антифигурки отрицательных фигурок взаимно уничтожаются (рис.5). Это можно представить себе по-другому: напишем на каждой положительной фигурке число 1, а на каждой отрицательной число -1 . Кратностью в точке называется сумма этих +1 по всем фигуркам, взятая в этой точке.


Мы будем говорить, что многоугольник допускает замощение со знаком, если положительные и отрицательные фигурки можно положить так, чтобы кратность в каждой точке внутри P равнялась 1. Ясно, что если рассуждение с использованием раскрасок наподобие того, что обсуждалось в предыдущем разделе, доказывает, что многоугольник нельзя замостить некоторым набором фигурок, то из этого же доказательства следует, что замощения со знаком также не существует. Однако бывают задачи, которые имеют решение только для замощений со знаком и неразрешимы для обычных замощений. Рассмотрим набор точек, расположенных в виде треугольника, как показано на рисунке 6. Мы хотим замостить этот треугольник прямыми плашками, каж-

плашкой, будет тогда кратна трем. Общая сумма зависит от n периодическим образом с периодом 9; ее значения по модулю три равны 0, 2, 2, 2, 1, 1, 1, 0, 0. Поэтому n mod 9 должно равняться 1, 8 или 0. Мы уже знаем, что n 0 или 2 (mod 3 ) , поэтому остаются только последние два случая. Покажем, что если n 8 или 0 (mod 9 ), то треугольник из точек можно замостить со знаком при помощи трехточечных плашек. На рисунке 8 такое замощение показано при n = 8, а на рисунке 9 изображено, как строить треугольники большего размера из треугольников со стороной 8 и рядов трехточечных плашек. Из этого получается, что следующую удивительную теорему невозможно доказать каким угодно рассуждением, использующим раскраски. Теорема 1. Ни для какого числа n треугольную таблицу точек со стороной n нельзя замостить трехточечными плашками. Группа Конвея замощения Для доказательства теоремы 1 нам понадобится некоторая предварительная подготовка. Для начала предположим, что все наши многоугольники: и область, которую мы собираемся замостить, и элементы замощения нарисованы на клетчатой бумаге и составлены из единичных квадратиков. Также условимся, что ни в каком из этих многоугольников не будет дырок: граница каждого из них будет состоять из единой замкнутой кривой.

Рис.6. Можно ли замостить этот треугольник плашками из трех точек?

Рис.7. Раскраска по модулю 3

дая из которых содержит три точки; каждая такая плашка может быть ориентирована одним из трех возможных способов. Для каких значений n существует такое замощение? Для начала, чтобы такое замощение было возможным, число точек должно делиться на три. Их общее число равно n (n + 1) 2 , и поэтому n 0 или 2 (mod 3 ) . Теперь 'раскрасим' точки так, как показано на рисунке 7. Сумма чисел, покрытых одной

Джон Конвей, р.1942

Рис.8. Замощение со знаком при n = 8

Рис.9. Построение больших замощений со знаком из меньших


НЕВОЗМОЖНЫЕ

ЗАМОЩЕНИЯ

Путь на клетчатой бумаге будет описываться словом, составленным из букв четырехбуквенного алфавита x, y, x -1 и y -1 : шаг вправо обозначается через x, шаг влево через x -1 , шаг вверх через y, и шаг -1 Рис.10. Путь и соответству- вниз через y . Пример изображен на рисунке 10. Мы бующее ему слово дем записывать k символов x или x -1 , идущих подряд, как x + k ; то же самое для y. Тривиальный путь будет обозначаться через e. Также условимся, что идущие подряд символы x и x -1 (или y и y -1 ) сокращаются: например, xyy -1x -1 = e . Композиция двух слов a и b будет определяться так: запишем сначала слово a, а потом слово b и сократим в полученном слове все идущие подряд пары, состоящие из x и x -1 и из y и y -1 . Полученное слово условимся обозначать через ab. Композиция удовлетворяет закону ассоциативности: (ab ) c = a (bc ) , где через a, b и c обозначены произвольные слова. Слово w-1 , обратное к данному слову w, получается так: надо прочитать слово w справа налево и заменить все показатели степеней на противоположные. Например, xy -1 = yx -1 . Ясно, что ww-1 = e . Пусть T ,..., Tn полный набор фигурок, разложен1 ных на клетчатой бумаге во всех возможных ориентациях (например, у доминошки различных ориентаций две, а у Г-образной фигурки восемь). Выберем на границе фигурки Ti начальную точку и пройдем вдоль границы против часовой стрелки. Полученный замкнутый путь будет соответствовать слову Wi , состоящему из букв x, x -1 , y и y -1 . Разумеется, это слово будет зависеть от выбора начальной точки. Пока что единственным имевшимся у нас правилом работы со словами был набор равенств
xx
-1

(

)

-1

= x -1x = e = yy

-1

= y -1y .

Добавим к этому правилу новые равенства: W1 = W2 = ... = e . Эти правила значат, что если одно из слов Wi встречается в более длинном слове, то мы можем заменить его на e, и, наоборот, мы можем вставлять в любом месте любого слова какое-либо из слов Wi . Если слово V может быть получено из слова 1 V2 последовательным применением этих правил, мы будем называть такие слова эквивалентными и записывать это как V = V2 . 1 Нам нужно еще разобраться с неоднозначностью выбора слова Wi , а именно, с его зависимостью от начальной точки. Пусть p другая начальная точка на границе фигурки Ti , и пусть Wi слово, полученное в результате прохождения вдоль границы начиная с точки p . Лемма. Имеется равенство Wi = e . Доказательство. Пусть слово u кодирует путь из p в p , а слово v путь из p в p (рис.11). Тогда Wi = uv и Wi = vu . Поскольку Wi = e , то и uv = e. Тогда
vu = u -1u (vu ) = u -1u = e , что и требовалось.

Пусть P многоугольник. Пройдем вдоль его границы и получим слово U (снова зависящее от начальной точки). Следующее предложение дает необхо- Рис.11. К доказательству лемдимое условие для суще- мы ствования замощения. Предложение. Если многоугольник P замощен фигурками T ,..., Tn , то U = e. 1 Доказательство. Индукция по количеству фигурок. Сначала предположим, что P замощен одной фигуркой, скажем, Ti . Тогда слово U равно какомуто из описанных выше Wi , и утверждение следует из леммы. Теперь предположим, что фигурок несколько. Тогда многоугольник P можно разрезать на два многоугольника P и P2 при помощи пути, проходящего внутри 1 P из одной точки границы до другой точки границы (назовем эти точки p и p ), причем идти этот путь должен лишь по границам фигурок (рис.12). Пусть w слово, соответствующее этому пути pp внутри P, и пусть v1 и v2 слова, соответствующие путям по границе многоугольника P из p в p и из p в p соответственно. Рис.12. Шаг индукции в доЗамкнутый путь по гра- казательстве предложения нице P против часовой стрелки, начинающийся в точке p, соответствует слову vv2 . При этом vv2 = v1w-1 (wv2 ) . Слова в скобках 1 1 соответствуют обходам по границам многоугольников P и P2 . В силу нашего выбора пути pp эти два 1 многоугольника замощены меньшим количеством фигурок. По предположению индукции, vw-1 = e и 1 wv2 = e . Поэтому и vv2 = e . 1 Наконец, слово U, соответствующее обходу вдоль границы, может отличаться от vv2 выбором начальной 1 точки. Но мы уже знаем из леммы, что если одно из этих слов эквивалентно e, то и другое тоже эквивалентно. Тем самым доказательство завершено.1 Из доказательства предложения видно, что равенство U = e можно получить из равенств W1 = W2 = ... = e чисто алгебраически, используя правила xx -1 = x -1x = e = yy -1 = y -1y и ассоциативность. Как может помочь это наблюдение? Если мы хотим доказать, что многоугольник P нельзя замостить фигурками T ,..., Tn , можно пытаться доказать, что равенство 1 U = e из равенств W1 = W2 = ... = e не следует. При этом уже не обязательно помнить, что x обозначает шаг

(

)

(

)

1 Удобно переформулировать конструкции, описанные в этом пункте, на языке групп. Набор фигурок T1,... , Tn определяет группу с двумя образующими x и y и с соотношениями W1,... ,Wn . Эта группа называется группой Конвея замощения. Граничное слово многоугольника P является элементом группы Конвея замощения, и если P может быть замощен фигурками T1,... , Tn , то этот элемент единичный.


влево, и т.д. Более того, можно придать буквам x, y, x -1 и y -1 новый смысл лишь бы оставались верными равенства W1 = W2 = ... = e и работали вышеуказанные правила. Например, в качестве x, y, возможно, подойдут числа, повороты плоскости, перестановки ... Если мы сумеем придать смысл буквам так, что нужные равенства и правила сохранятся, но при этом окажется U e , мы докажем, что замощение невозможно! Пример. Вернемся к задаче о шахматной доске с вырезанными углами, с которой мы начали эту статью. Двум положениям доминошек размера 2 Ч 1 соответствуют граничные слова W1 = x 2 yx2 y -1 и

должно быть сравнимо с 0 или 8 по модулю 9. Если замощение существует при n 8 (mod 9 ) , то, как показано на рисунке 9, оно также существует и для n 0 (mod 9 ) . Итак, достаточно доказать, что замощение невозможно при n, кратном 9. Изобразим треугольник из точек иначе: как 'лесенку' на клетчатой бумаге, первая строчка которой состоит из одной клетки, вторая из двух, и так далее. Тогда наши плашки длины три будут изображаться в виде фигур с рисунка 14. На том же рисунке указаны и граничные слова для этих многоугольников. Мы хотим доказать, что для всякого n из равенств W1 = W2 = W3 = e не следует равенство Un = e . Рас-

Рис.13. Снова о шахматной доске с вырезанными углами

Рис.14. Фигурки и соответствующие им слова

W2 = xy2 x -1y -2 , а граничное слово шахматной доски с вырезанными углами это U = x 7 y7 x -1yx -7 y -7 xy -1 (рис.13). Мы хотим доказать, что из равенств W1 = e и W2 = e не следует, что U = e; согласно предложению, из этого будет следовать, что искомого замощения доски не существует. Заменим x перестановкой (12) (перестановка элементов 1, 2 и 3, меняющая местами 1 и 2), а y перестановкой (23). Напомним, что перестановки можно перемножать: произведение перестановок и означает перестановку, получающуюся в результате последовательного применения перестановки и перестановки . Тогда и x 2 , и y2 становятся равными тривиальной перестановке, и поэтому оба слова W1 и W2 становятся тривиальными. Следовательно, если U = e, то после замены x и y на перестановки (12) и (23) мы должны получить тривиальную перестановку. Но это не так! Читатель без труда проверит, что U = = (xy)4 = (312) (перестановка, сдвигающая элементы 1, 2, 3 по циклу: 1 на место 2, 2 на место 3 и 3 на место 1), т.е. U соответствует нетривиальной перестановке.2

смотрим теперь три семейства ориентированных параллельных прямых, изображенные на рисунке 15. Эти прямые отстоят друг от друга на равные расстояния и пересекаются под углом 60њ ; они образуют замощение плоскости равносторонними треугольниками и правильными шестиугольниками. Обозначим тре-

Рис.15. Шестиугольная решетка: дублеры границ трех плашек

Доказательство теоремы 1 Неудивительно, что теорема 1 потребует большей работы, нежели наш пример: в конце концов, у задачи о шахматной доске с вырезанными углами есть простое решение, использующее раскраски. Во-первых, раньше мы выяснили, что существует необходимое условие для существования замощения: n
2 В теоретико-групповых терминах можно сказать, что мы построили гомоморфизм из группы Конвея замощения в группу перестановок трех элементов; этот гомоморфизм переводит граничное слово шахматной доски с вырезанными углами в нетривиальную перестановку.

угольники буквами x и y, как показано на рисунке 15. Получившийся рисунок будем называть шестиугольной решеткой. Шестиугольная решетка весьма симметрична. Для любых двух ее вершин существует движение плоскости, переводящее одну из них в другую и сохраняющее решетку. Например, параллельный перенос переводит вершину B на рисунке 16 в вершину D, а поворот на 120њ вокруг точки A, являющейся центром треугольника, отмеченного буквой x, переводит вершину B в C. Всякий путь на квадратной решетке можно следующим образом продублировать на шестиугольной решетке. Путь на квадратной решетке записывается в виде слова из букв x, y, x -1 и y -1 . Во всякой вершине шестиугольной решетки пересекаются две ориентиро-


НЕВОЗМОЖНЫЕ

ЗАМОЩЕНИЯ

ванные прямые, и два из четырех полученных углов отмечены буквами x и y (рис.15). Мы будем интерпретировать символы x, y, x -1 и y -1 как инструкции по построению путидублера: x +1 будет означать 'сделать один шаг по границе угла, отмеченного буквой x, по направлению ориентации или против него соответственно'; то же самое для y +1 . Рис.16. Симметрии шестиуголь- Итак, как только мы ной решетки выберем начальную точку, путь на квадратной решетке определит нам путь-дублер на шестиугольной решетке. На рисунке 15 показаны пути на шестиугольной решетке, построенные по граничным путям трех фигурок с рисунка 14. Заметьте, что все три пути-дублера замкнуты; этот факт остается верным при любом выборе начальной точки пути-дублера из-за симметрий шестиугольной решетки. Напротив, дублер пути xyx -1y -1 , т.е. границы единичного квадратика, будет незамкнутым. Будем рассматривать только такие пути на квадратной решетке, дублеры которых на шестиугольной решетке будут замкнутыми. Этим свойством обладают граничные пути трех плашек, а также граница изображенной на рисунке 14 'лесенки'; ее дублер показан на рисунке 17 (здесь мы пользуемся тем, что n делится на три). Ориентированная замкнутая кривая делит плоскость на некоторое количеРис.17. Дублер к границе 'ле- ство компонент. Каждой сенки' компоненте отвечает число вращения этой кривой вокруг любой точки данной компоненты. Ориентированная площадь, ограниченная замкнутой кривой, равна сумме площадей компонент, умноженных на соответствующие числа вращения. Например, единичный круг с ориентированной против часовой стрелки границей имеет ориентированную площадь , а если его граница ориентирована по часовой стрелке, то - .3 Сопоставим пути на квадратной решетке ориентированную площадь, ограниченную его дублером на шестиугольной решетке. Для граничных путей трех фигурок эта площадь равна
3 В математическом анализе ориентированная площадь определяется как интеграл вдоль кривой от дифференциальной формы xdy.

нулю (см. рис.15), тогда как для 'лесенки' соответствующая ориентированная площадь всегда отрицательна (см. рис. 17). Из этого следует, что Un e . Действительно, если заменить одно из слов W1 , W2 или W3 словом e или наоборот, то ориентиро- Рис.18. Можно ли замостить больванная площадь, огра- шой треугольник маленькими? ниченная путем-дублером, не изменится. Эта площадь равна нулю для тривиального слова и отлична от нуля для Un . Тем самым доказательство теоремы 1 закончено. В завершение этого раздела приведем еще одну теорему, которую можно доказать аналогично теореме 1. На этот раз мы попытаемся замостить такой же треугольник, составленный из точек, маленькими треугольниками из трех точек (рис.18). Теорема 2. Такое замощение существует тогда и только тогда, когда n 0, 2, 9 или 11 (mod 12 ) . Теорема Макса Дена После решения третьей проблемы Гильберта Макс Ден доказал в 1903 году следующую теорему. Теорема 3. Если прямоугольник замощен квадратами, то отношение длин его сторон есть рациональное число. Обратное с очевидностью верно (рис.19). Доказательство. Будем рассуждать от противного. Можно масштабировать прямоугольник так, чтобы его ширина была Макс Ден, 18781952 равной 1; пусть его высота x иррациональное число. Предположим, что замощение при помощи квадратов существует. Продлим стороны квадратов на всю длину или ширину прямоугольника (рис. 20). Теперь у нас есть замощение нашего прямоугольника размера x ? 1 и всех квадратов при помощи некоторого количества меньших прямоугольников; Рис.19. Если отношение длин пусть длины их сторон (в сторон прямоугольника рационально, его можно замостить произвольном порядке) квадратами равны a1 , , aN . Рассмотрим последовательность 1, x, a1 , , aN ; (1) удалим из нее те числа, которые являются линейными комбинациями предыдущих с рациональными коэф-


Рис. 20. Продление сторон квадратов

фициентами. Так, мы не удаляем 1, мы также не удаляем x, поскольку оно иррационально; мы удаляем a1 , если и только если a1 = r1 + r2 x, где r1 и r2 рациональны, и т.д. Пусть b1 = 1, b2 = x, b3 , , bm оставшиеся числа. Важное замечание: всякое из чисел в последовательности (1) может быть представлено в виде рациональной линейной комбинации чисел b1 , ..., bm , причем единственным образом. (Это стандартная теорема из линейной алгебры, но ради полноты изложения приведем здесь ее доказательство. Очевидно, что 1 и x являются рациональными линейными комбинациями чисел b1 , , bm (просто 1 = b1 и x = b2 ). Предположим по индукции, что все числа в последовательности (1), предшествующие ak , суть рациональные линейные комбинации чисел b1 , ..., bm . Возможны два случая: либо ak не является рациональной линейной комбинацией предыдущих чисел тогда оно является одним из bj и тем самым является рациональной линейной комбинацией b1 , ..., bm ; либо ak является рациональной линейной комбинацией предыдущих чисел тогда оно является рациональной линейной комбинацией b1 , , bm , поскольку все предыдущие числа представимы как рациональные линейные комбинации b1 , , bm . Осталось доказать единственность. Если две различные линейные комбинации чисел b1 , , bm равны,

прямоугольников имеется общая горизонтальная или вертикальная сторона, их можно объединить в больший прямоугольник. В силу аддитивности функции f (равенство (2)) 'площадь' большего прямоугольника есть сумма 'площадей' двух меньших прямоугольников. Следовательно, 'площадь' прямоугольника размера x ? 1 равна сумме 'площадей' квадратов, из которых он составлен. Первая равна f(x)f(1) = 1, тогда как 2 'площадь' квадрата размера u ? v равна f (u ) , т.е. неотрицательна. Мы получили противоречие. Замощения квадратами и электрические цепи Рассмотрим замощение прямоугольника квадратами, изображенное на рисунке 21. Пусть x1 , , x9 длины сторон квадратов. Для каждого отрезка на этом рисун-

Рис. 21. Замощение квадратами


i =1

m

rbi =


j =1

m

rb j , j

а s максимальное число от 1 до m, для которого s -1 r - ri bi , откуда получается, что bs rs rs ,то bs = i i =1 r - r s s линейная комбинация предыдущих чисел bi , что противоречит нашему выбору b1 , , bm .) Пусть f следующая функция от чисел b1 , , bm : f(1) = 1, f(x) = - 1, f( b3 ) = = f( bm ) = 0. Продолжим f на все рациональные линейные комбинации чисел b1 , , bm по линейности: f( rb1 + + rmbm ) = r1 f( b1 )+ + rm f( bm ). 1 Значит, если u и v рациональные линейные комбинации чисел b1 , , bm , то f(u + v) = f(u) + f(v), (2)

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

x2 = x4 + x5 , x3 + x5 = x6 , x1 + x4 = x7 + x8 , x6 + x8 = x9
(горизонтальные отрезки) и
x1 = x2 + x4 , x7 = x8 + x9 , x4 + x8 = x5 + x6

(3) (4)

(вертикальные отрезки). Чтобы такое замощение существовало, эта система линейных уравнений должна быть разрешима в положительных числах. Замощение на рисунке 21 соответствует следующему решению:

x1 = 15, x2 = 8, x3 = 9, x4 = 7, x5 = 1, x6 = 10, x7 = 18, x8 = 4, x9 = 14;
разумеется, весь этот набор чисел можно умножить на произвольный множитель. Уравнения (3) и (4) можно интерпретировать как правила Кирхгофа для электрических цепей. Пример такой цепи показан на рисунке 22. Предположим, что все резисторы имеют единичное сопротивление и что сила тока в i-м резисторе равняется xi . Есть два

т.е. функция f аддитивна. Рассмотрим прямоугольник, длины обеих сторон которого u и v суть рациональные линейные комбинации чисел b1 , , bm . Определим 'площадь' этого прямоугольника как f(u)f(v). Если у двух таких


НЕВОЗМОЖНЫЕ

ЗАМОЩЕНИЯ

правила Кирхгофа: первое правило, или закон токов, утверждает, что сумма токов, втекающих в каждый узел, равняется сумме токов, вытекающих из него; второе правило, или закон напряжений, гласит, что сумма падений напряжения по любому замкнутому контуру равна нулю.4 Поскольку сопротивление всех резисторов единичное, по закону Ома падение напряжения на i-м резисторе равно силе тока xi . Законы токов для цепи на рисунке 22 это в точности уравнения (3), а законы напряжений это уравнения (4). Контур на рисунке 22 получается из замощения на рисунке 21 следующим образом: всякому горизонтальному отрезку соответствует узел электрической цепи, а каждый квадрат соответствует резистору. Резистор соединяет два узла, если отвечающий ему квадрат примыкает к соответствующим двум отрезкам. Эта конструкция работает для любого замощения прямоугольника квадратаРис. 22. Электрическая цепь, соответ- ми и дает электрическую цепь. Падение напряжения между ствующая замощеверхней и нижней вершинами нию на рис. 21 (т.е. напряжение источника ЭДС) единственным образом определяет токи во всех резисторах, и мы получаем решение системы (3) (4). В частности, у этой системы имеется единственное решение, с точностью до общего множителя. То же самое верно и для любого замощения прямоугольника квадратами. Недостаток этого метода состоит в том, что у нас нет контроля над знаками силы тока: ток в некоторых резисторах может оказаться отрицательным, и тогда электрическая цепь не будет соответствовать никакому замощению прямоугольника квадратами. Замощение прямоугольниками с целочисленными сторонами Теорема 4. Пусть прямоугольник R замощен прямоугольниками, у каждого из которых есть целочисленная сторона. Тогда и у R есть целочисленная сторона. У этой теоремы о замощениях известно чрезвычайно много различных доказательств (в журнале 'American Mathematical Monthly', 7-й выпуск за 1987 год, опубликована статья, в которой приведено четырнадцать, а кроме них есть и другие). Мы выбрали одно из самых красивых (от редакции: для тех, кто незнаком с двойными интегралами, после этого доказательства мы приводим по сути вариант того же самого рассуждения, но на абсолютно элементарном языке!). Доказательство. Интеграл Ъ sin 2xdx по отрезку целой длины равен нулю. Следовательно, двойной
4 Разумеется, здесь рассматриваются только контуры, не включающие в себя источник ЭДС. Прим. перев.

интеграл

ЪЪ

sin 2x sin 2y dxdy

по каждому из прямоугольников, участвующих в замощении, равен нулю. Значит, этот двойной интеграл по всему прямоугольнику R также равен нулю. Предположим, что левый нижний угол прямоугольника R находится в начале координат, а длины его сторон равны a и b. Тогда
ab

ЪЪ
00

sin 2x sin 2y dxdy =

1

( 2 )

2

(1

- cos 2a ) (1 - cos 2b ) .

Следовательно, либо cos 2a = 1 , либо cos 2b = 1 , т.е. либо a, либо b целое число. Замена в этом доказательстве функции sin 2x sin 2y на функцию ( -1) ( -1) дает простое доказательство без интегралов. Аналогичное элементарное доказательство. Разграфим плоскость на клетки со стороной 1/2 и раскрасим ее в два цвета черный и белый, в шахматном порядке. Верен такой замечательный факт: как бы мы ни расположили на этой плоскости прямоугольник, стороны которого параллельны линиям сетки и длина одной из сторон целая, в нем будет поровну черного и белого цвета. Это совсем очевидно, если его стороны с целой длиной (пусть они горизонтальны) упираются концами в линии сетки тогда прямоугольник делится вертикальными линиями сетки на четное число одинаковых по размеру столбиков (для этого мы взяли сторону клетки 1/2), причем в каждом столбике столько белого, сколько в соседнем черного, и наоборот (рис.23). Разбив столбики на пары соседних, видим, что белого и черного в прямоугольнике поровну. Общий слу- Рис. 23 чай сводится к только что рассмотренному проверьте, что, сдвигая прямоугольник параллельно его стороне с целой длиной, мы не меняем в нем количество черного и белого цвета. Теперь несложно вывести и саму теорему. Расположим наш большой прямоугольник так, чтобы он весь лежал в первом квадранте, а одна из его вершин совпадала с началом координат. В каждом маленьком прямоугольнике белого и черного будет поровну, а значит и в большом тоже. Пусть обе стороны большого прямоугольника нецелые. Рассмотрим самую высокую горизонтальную линию сетки с целой ординатой и самую правую вертикальную линию сетки с целой абсциссой, пересекающие наш прямоугольник (рис.24). Они делят его на четыре прямоугольные части, три из которых имеют сторону с целой длиной и, значит, содержат поровну белого и черного цвета. Тогда и четвертая часть (правая верхняя) содержит поровну
[2 x] [2 y]


(Paul Monsky) в 1970 году, и ее доказательство крайне неожиданно.5 Возможно, еще более неожиданно, что существуют четырехугольники, которые нельзя замостить никаким количеством треугольников равной площади.
Упражнения 1. Можно ли замостить доминошками фигуру, изображенную на рисунке 27?

Рис. 24

черного и белого цвета. Эта часть целиком лежит в квадрате 1Ч1 и имеет нецелые стороны a и b, где 0 <
Рис. 27. Еще одно доказательство с помощью раскраски 2. Вырежем из шахматной доски одну белую и одну черную клетку. Докажите, что полученную доску можно замостить доминошками. Указание. Рассмотрите замкнутый путь, покрывающий все клетки, и выложите доминошки вдоль него. 3. Докажите, что квадрат размера 10 Ч 10 нельзя замостить прямоугольниками размера 1 Ч 4 . Указание. Используйте раскраску в четыре цвета. 4.** Докажите теорему 2. 5. Покажите, что многоугольник на рисунке 28 невозможно замостить квадратами (это, конечно же, станет возможно, если мы разрешим использовать 'квадраты из антивещества'!). 6. Пусть x = 2 - 3 5 . Разрежьте квадрат на три прямоугольника, подобных прямоугольнику размера 1 ? x . Комментарий . Квадрат можно разрезать на прямоугольники, подобные прямоугольнику размера 1 ? x , если и только если x являетРис. 28. Этот многоугольник ся корнем многочлена с ценельзя замостить квадратами лыми коэффициентами и при этом для каждого корня a + bi многочлена наименьшей степени, корнем которого является x, выполнено неравенство a > 0. 7. Покажите, что теорема 4 останется верной, если разрешить использовать 'квадраты из антивещества'. Указание. Переопределите 'площадь' прямоугольника размера u ? v как uf(v) vf(u). Эта площадь снова будет аддитивной, а для всех квадратов она окажется равной нулю.

Рис. 26. Замощение треугольниками равной площади

5 См., например, статью Б.Беккер, С.Востоков, Ю. Ионин. '2-адические числа'. 'Квант' ?2 за 1979 г.