получилось. Как он ни старался, уложить плитки так, чтобы они покрыли всю площадку, это ему не удалось.
Дочь мистера Брауна начертила план площадки, раскрасила квадраты в шахматном порядке и в течение нескольких минут внимательно разглядывала свой рисунок.
Какое отношение это имеет к делу? Что Бетси имеет в виду?
На плане площадки 21 черный квадрат и 19 белых квадратов. Следовательно, после того, как уложено 19 новых плиток, 2 черных квадрата неизменно остаются непокрытыми, и покрыть их одной новой плиткой невозможно. Единственный способ выйти из затруднения — расколоть новую плитку на два квадрата.
Дочь мистера Брауна нашла способ покрыть площадку прямоугольными плитками, воспользовавшись рассуждением, известным под названием «проверка на четность». Мы говорим о двух числах, что их четность одинакова, если они либо оба четны, либо оба нечетны. Если одно число четно, а другое нечетно, то говорят, что их четность различна. С подобными ситуациями неоднократно приходится сталкиваться в комбинаторной геометрии.
В нашей задаче два квадрата одного цвета обладают одинаковой четностью, а четность двух квадратов различных цветов различна. Прямоугольная плитка покрывает только квадраты различной четности. Бетси доказала, что если 19 прямоугольных плиток уложить на площадке перед домом, то 2 оставшихся квадрата можно было бы покрыть последней прямоугольной плиткой, если бы их четность была одинаковой. А поскольку четность двух оставшихся квадратов всегда одинакова, то покрыть их последней плиткой невозможно. Следовательно, покрыть площадку перед домом новыми плитками также невозможно.
Проверка на четность в самых различных вариантах лежит в основе доказательств многих теорем «несуществования» в математике. Кто не помнит, например, знаменитое доказательство иррациональности числа v2, предложенное Евклидом. Иррациональность v2 Евклид доказывает от противного, то есть сначала предполагает, что число v2 рациональное и его можно представить в виде несократимой дроби с целым числителем и знаменателем. Числитель и знаменатель этой дроби не могут быть оба четными, так как тогда дробь не была бы несократимой. Следовательно, либо они оба нечетны, либо один из них четен, а другой нечетен. Затем Евклид доказывает, что и в том, и в другом случае дробь, которая была бы равна v2, не существует. Иначе говоря, числитель и знаменатель дроби, которая была бы равна v2, не могли бы быть ни одинаковой, ни различной четности. Но все дроби подразделяются на два непересекающихся класса: к одному относятся дроби с числителем и знаменателем одинаковой четности, к другому принадлежат дроби с числителем и знаменателем различной четности. Следовательно, число v2 непредставимо в виде дроби с целым числителем и знаменателем, то есть иррационально.
Теория покрытия одних плоских фигур другими изобилует задачами, в которых доказать несуществование решения было бы трудно, если бы не проверка на четность. Задача, с которой столкнулся мистер Браун, чрезвычайно проста, поскольку в ней речь идет о покрытии площадки плитками в форме костей домино — простейших нетривиальных полимино. (Каждая «кость» полимино составлена из квадратов, примыкающих друг к другу по целой стороне). Предложенное Бетси доказательство неразрешимости задачи применимо к любой фигуре из единичных квадратов, у которой после раскрашивания квадратов в шахматном порядке клеток одного цвета оказывается по крайней мере на одну больше, чем клеток другого цвета.
В рассмотренной нами задаче площадку перед домом можно рассматривать как прямоугольник размером 6?7 единиц с двумя недостающими клетками одного цвета. Если из прямоугольника вырезать 2 клетки одного цвета, то ясно, что покрыть 20 костями домино 40 остальных клеток невозможно. С исходной задачей тесно связан следующий ее интересный вариант: всегда ли 20 костями домино можно покрыть прямоугольник размером 6?7 единиц, из которого вырезаны 2 клетки разного цвета? Проверка на четность не позволяет доказать неразрешимость новой задачи, но это отнюдь не означает, будто бренные останки прямоугольника всегда можно покрыть 20 костями домино. От перебора всех фигур, возникающих при удалении из прямоугольника размером 6?7 единиц двух клеток разного цвета, следует заранее отказаться, так как их слишком много, что затрудняет анализ задачи. Не существует ли простое доказательство разрешимости задачи, позволяющее разом охватить все прямоугольники размером 6?7 с двумя недостающими клетками разного цвета?
Такое доказательство, простое и изящное, действительно существует. Идею его предложил Ральф Гомори. Оно также использует проверку на четность. Предположим, что прямоугольник размером 6?7 целиком заполнен замкнутой дорожкой шириной в 1 клетку (рис.
Теория «покрытия» — обширный раздел комбинаторной геометрии, интерес к которому все возрастает. Области, которые требуется покрыть, могут быть любой формы, конечными или бесконечными. Форма фигур, которыми требуется покрыть заданную фигуру, варьируется от задачи к задаче. Иногда требуется покрытие не конгруэнтными фигурами, а фигурами нескольких различных форм. Доказательство несуществования решения таких задач нередко удается получить, раскрасив клетки покрываемой фигуры специальным образом в несколько цветов.
Трехмерным аналогом домино служит кирпич размером 1?2?4 единиц. Такими кирпичами нетрудно заполнить ящик размером 4?4?4 единиц (заполнение пространственных тел принято называть упаковкой). Можно ли заполнить кирпичами ящик размером 6?6?6 единиц? Решение этой задачи аналогично решению задачи о покрытии площадки перед домом мистера Брауна. Представим себе, что ящик разделен на 27 кубиков размером 2?2?2 единиц. Раскрасим кубики в шахматном порядке в черный и белый цвет («шахматная доска» при этом получится не обычная, а трехмерная). Подсчитав, сколько черных и белых кубиков вмещает ящик, мы обнаружим, что кубиков одного цвета на 8 больше, чем кубиков другого.
Независимо от того, как расположен кирпич внутри ящика, он всегда покрывает столько же белых кубиков, сколько и черных. Но кубиков одного цвета в ящике на 8 больше, чем кубиков другого цвета. Независимо от того, как расположены в ящике первые 26 кирпичей, в нем всегда остается еще 8 кубиков одного цвета. Покрыть их двадцать седьмым кирпичом невозможно. Доказать то же утверждение, перебирая все возможные случаи упаковки ящика, было бы чрезвычайно трудно.
Теория упаковки кирпичей — лишь небольшой фрагмент теории упаковки в трехмерном пространстве. Проблемам этой теории, среди которых имеется немало нерешенных, посвящена обширная и все возрастающая литература. Многие из задач относятся к рациональному выбору стандартной упаковки промышленных товаров, хранению товаров на складе и т. д.
Четность играет важную роль и в физике элементарных частиц. В 1957 г. два американских физика китайского происхождения, Ли Цзундао и Янг Чжэньнин, получили Нобелевскую премию за теоретическое предсказание несохранения четности. Их знаменитая работа носит слишком специальный характер, чтобы мы могли разобрать ее здесь, но сохранение четности можно продемонстрировать на примере одного замечательного фокуса с монетами.
Наберите пригоршню монет и, бросив ее на стол, сосчитайте, сколько монет выпало вверх гербом. Если число гербов окажется четным, мы скажем, что гербы имеют «четную четность». Если число гербов на столе окажется нечетным, мы скажем, что гербы имеют «нечетную четность». Выбрав наугад две монеты,
