Читать онлайн «Есть идея!». Страница 8

В рассмотренной нами задаче площадку перед домом можно рассматривать как прямоугольник размером 6×7 единиц с двумя недостающими клетками одного цвета. Если из прямоугольника вырезать 2 клетки одного цвета, то ясно, что покрыть 20 костями домино 40 остальных клеток невозможно. С исходной задачей тесно связан следующий ее интересный вариант: всегда ли 20 костями домино можно покрыть прямоугольник размером 6×7 единиц, из которого вырезаны 2 клетки разного цвета? Проверка на четность не позволяет доказать неразрешимость новой задачи, но это отнюдь не означает, будто бренные останки прямоугольника всегда можно покрыть 20 костями домино. От перебора всех фигур, возникающих при удалении из прямоугольника размером 6×7 единиц двух клеток разного цвета, следует заранее отказаться, так как их слишком много, что затрудняет анализ задачи. Не существует ли простое доказательство разрешимости задачи, позволяющее разом охватить все прямоугольники размером 6×7 с двумя недостающими клетками разного цвета?

Такое доказательство, простое и изящное, действительно существует. Идею его предложил Ральф Гомори. Оно также использует проверку на четность. Предположим, что прямоугольник размером 6×7 целиком заполнен замкнутой дорожкой шириной в 1 клетку (рис. 4). Если удалить 2 клетки разного цвета, то, где бы они ни были расположены в прямоугольнике, замкнутая дорожка распадется на две части, каждая из которых состоит из четного числа клеток, цвета которых чередуются. Ясно, что каждый такой отрезок дорожки можно выложить костями домино. Следовательно, задача всегда допускает решение. Может быть вам захочется испытать свои силы и, применить остроумную идею Гомори к доказательству разрешимости аналогичных задач для прямоугольников других размеров и форм, из которых вырезано более двух клеток.

Теория «покрытия» — обширный раздел комбинаторной геометрии, интерес к которому все возрастает. Области, которые требуется покрыть, могут быть любой формы, конечными или бесконечными. Форма фигур, которыми требуется покрыть заданную фигуру, варьируется от задачи к задаче. Иногда требуется покрытие не конгруэнтными фигурами, а фигурами нескольких различных форм. Доказательство несуществования решения таких задач нередко удается получить, раскрасив клетки покрываемой фигуры специальным образом в несколько цветов.

Трехмерным аналогом домино служит кирпич размером 1×2×4 единиц. Такими кирпичами нетрудно заполнить ящик размером 4×4×4 единиц (заполнение пространственных тел принято называть упаковкой). Можно ли заполнить кирпичами ящик размером 6×6×6 единиц? Решение этой задачи аналогично решению задачи о покрытии площадки перед домом мистера Брауна. Представим себе, что ящик разделен на 27 кубиков размером 2×2×2 единиц. Раскрасим кубики в шахматном порядке в черный и белый цвет («шахматная доска» при этом получится не обычная, а трехмерная). Подсчитав, сколько черных и белых кубиков вмещает ящик, мы обнаружим, что кубиков одного цвета на 8 больше, чем кубиков другого.

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

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

Четность играет важную роль и в физике элементарных частиц. В 1957 г. два американских физика китайского происхождения, Ли Цзундао и Янг Чжэньнин, получили Нобелевскую премию за теоретическое предсказание несохранения четности. Их знаменитая работа носит слишком специальный характер, чтобы мы могли разобрать ее здесь, но сохранение четности можно продемонстрировать на примере одного замечательного фокуса с монетами.

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

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

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

Перед вами снова проф. Квиббл.

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

Ну как, решили?

У проф. Квиббла всего 3 домашних животных: собака, кошка и попугай. Все они, кроме двух, собаки, все они, кроме двух, кошки, и все они, кроме двух, попугаи.

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

Пусть x — число собак, y — число кошек, z — число попугаев, а n — общее число животных. Тогда условия задачи позволяют записать следующую систему из 4 уравнений:

n = x + 2

n = y + 2

n = z + 2

n = x + y + z

Решить ее можно многими стандартными способами. Из первых трех уравнений видно, что x = y = z. Так как n = x + 2 и n = Зx (из последнего уравнения), то x + 2 = 3x, откуда x = 1, и мы получаем полный ответ задачи: x = y = z = 1.

Поскольку x, y и z в таких задачах принимают, как правило, целые положительные значения (кто станет держать у себя треть кошки или четверть попугая?), то задачу о домашних животных проф. Квиббла можно отнести к так называемым диофантовым задачам. Так принято называть задачи, сводящиеся к решению алгебраических уравнений в целых числах. Иногда диофантовы уравнения не имеют решений или допускают только одно решение. Существуют также диофантовы уравнения, имеющие более одного решения и даже бесконечно много решений. Вот, например, еще одна несколько более трудная диофантова задача о трех видах домашних животных, также сводящаяся к решению системы линейных уравнений.

Корова стоит 10 долларов, свинья — 3 доллара, а овца — 50 центов. Фермер купил по крайней мере 1 корову, 1 свинью и 1 овцу, израсходовав на покупку всего 100 долларов. Сколько и каких животных он купил?

Пусть x — число коров, y — число свиней и z — число овец. Тогда условия задачи можно записать в виде двух уравнений:

10x + 3y + z/2 = 100,

x + y + z = 100.

Умножив правую и левую часть первого уравнения на 2, избавимся от двойки в знаменателе, после чего вычтем из первого уравнения второе. Тем самым мы исключим z и получим «укороченное» уравнение