Мартин Гарднер - Есть идея!

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

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

Из длинного списка хлопотливых домашних дел мистеру и миссис Джонс осталось выполнить три пункта:

1) произвести уборку на первом этаже (у семейства Джонсов имеется 1 пылесос, на уборку первого этажа уходит 30 мин);

2) подстричь газон перед домом (у семейства Джонсов имеется 1 машинка для стрижки газона, на выполнение этого задания необходимо затратить 30 мин);

3) накормить и уложить спать ребенка (на это также требуется затратить 30 мин).

Как следует распределить обязанности супругам Джонс, чтобы завершить все работы по дому в кратчайший срок? Если предположить, что мистер и миссис Джонс работают одновременно, то трудно удержаться от искушения дать ответ: «На выполнение 3 пунктов программы у супругов Джонс уйдет 60 мин». Но если одну из работ, например уборку первого этажа, разделить на 2 равные части и выполнение второй половины отложить (как в задаче с поджариванием ромштексов) до завершения другой работы, то на выполнение намеченной программы у супругов Джонс уйдет лишь ¾ времени (по сравнению с первым вариантом), или 45 мин.

А вот более хитроумная задача на исследование операций: требуется как можно быстрее обжарить с двух сторон 3 ломтика хлеба и каждый из них с одной стороны намазать маслом. В нашем распоряжении имеется тостер устаревшей модели с дверцами на пружинках справа и слева. Тостер вмещает одновременно 2 ломтика хлеба и поджаривает их только с одной стороны. Чтобы поджарить тосты с двух сторон, необходимо открыть дверцы и перевернуть ломтики на другую сторону.

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

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

Нетрудно спланировать все операции так, чтобы 3 ломтика поджаренного хлеба с маслом были готовы за 2 мин. Но 9 с можно сэкономить, если вам удастся набрести на следующую счастливую идею: ломтик хлеба можно поджарить с одной стороны не до конца, затем вынуть из тостера и дожарить позже. При таком подходе время на приготовление 3 ломтиков поджаренного хлеба с маслом удается сократить до 114 с. Но даже для тех, кому удается подобрать ключ к решению, составление оптимального графика выполненных операций остается далеко не легкой задачей. Что же касается бесчисленных проблем на составление самых экономичных последовательностей операций в различных областях человеческой деятельности, то они требуют для своего решения сложных математических методов, обращения к ЭВМ и современной теории графов.

Упрямые плитки

Площадка перед домом мистера Брауна выложена 40 квадратными плитками. Со временем некоторые плитки треснули, и мистер Браун решил покрыть площадку заново.

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

Владелец магазина. Сколько вам нужно плиток, мистер Браун?

Мистер Браун. Мне нужно покрыть 40 квадратов. Думаю, что 20 плиток будет достаточно.

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

Бетси. Что случилось, папа? Чем ты так озабочен?

М-р Браун. Никак не могу уложить эти проклятые плитки! Как ни бьюсь, два квадрата остаются непокрытыми. С ума можно сойти!

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

Бетси. Есть идея! Я поняла, почему у тебя ничего не получается, папа! Все дело в том, что каждая новая плитка должна накрывать один белый и один черный квадрат.

Какое отношение это имеет к делу? Что Бетси имеет в виду?

На плане площадки 21 черный квадрат и 19 белых квадратов. Следовательно, после того, как уложено 19 новых плиток, 2 черных квадрата неизменно остаются непокрытыми, и покрыть их одной новой плиткой невозможно. Единственный способ выйти из затруднения — расколоть новую плитку на два квадрата.

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

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

Проверка на четность в самых различных вариантах лежит в основе доказательств многих теорем «несуществования» в математике. Кто не помнит, например, знаменитое доказательство иррациональности числа √2, предложенное Евклидом. Иррациональность √2 Евклид доказывает от противного, то есть сначала предполагает, что число √2 рациональное и его можно представить в виде несократимой дроби с целым числителем и знаменателем. Числитель и знаменатель этой дроби не могут быть оба четными, так как тогда дробь не была бы несократимой. Следовательно, либо они оба нечетны, либо один из них четен, а другой нечетен. Затем Евклид доказывает, что и в том, и в другом случае дробь, которая была бы равна √2, не существует. Иначе говоря, числитель и знаменатель дроби, которая была бы равна √2, не могли бы быть ни одинаковой, ни различной четности. Но все дроби подразделяются на два непересекающихся класса: к одному относятся дроби с числителем и знаменателем одинаковой четности, к другому принадлежат дроби с числителем и знаменателем различной четности. Следовательно, число √2 непредставимо в виде дроби с целым числителем и знаменателем, то есть иррационально.

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