Мартин Гарднер - Математические головоломки и развлечения

• Название: Математические головоломки и развлечения
• Автор: Мартин Гарднер
• Издательство: "Мир"
• Жанр: Развлечения
• Год: 1999
• ISBN: 5-03-003340-8

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

---

Во всех головоломках элементы пентамино можно класть на плоскость любой стороной.

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

Рис. 235

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

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

Рис. 236

3. Разбейте двенадцать пентамино на три группы по четыре элемента. К каждой группе добавьте мономино (один квадратик) и постройте прямоугольник размером 3x7. Как это сделать, показано на рис. 237.

Рис. 237

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

Доказать единственность решения можно следующим образом.

Прежде всего заметим, что на рис. 238 элемент X должен обязательно использоваться в паре с элементом U. Ни элемент F, ни элемент W не годятся для того, чтобы завершить построение прямоугольника.

Рис. 238

Если элемент X дополнить элементом U, то в том же самом прямоугольнике 3x7 уже нельзя будет использовать элементы F и W. Следовательно, из трех прямоугольников размером 3 х 7 в одном будут использованы элементы X и U, второй будет содержать элемент W (но не U), а третий — элемент F (но не U). Если теперь перебрать все возможные варианты прямоугольников и сравнить их (это отнимет у вас достаточно много времени), то окажется, что предполагаемое решение (см. рис. 237) единственно.

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

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

5. Найдите на шахматной доске область минимального размера, на которой умещается любой из двенадцати элементов пентамино.

Минимальная площадь такой области равна девяти квадратам, и известно всего две ее формы (рис. 239).

Рис. 239

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

Если бы годилась фигура, содержащая меньше девяти квадратов, то элементами I, X и V можно было бы закрыть не более восьми квадратов. При этом у элементов I и X было бы три общих квадрата. (В противном случае либо потребовалось бы девять квадратов, либо, что было бы излишней роскошью, самая длинная прямая состояла бы из шести квадратов.) Этого можно достичь всего лишь двумя разными способами (рис. 240), но в том и в другом случае нужен еще и девятый квадрат, чтобы уместить элемент U.

Рис. 240

Таким образом, восьми квадратов не хватает, в то время как из приведенных примеров видно, что девяти квадратов достаточно.

С появлением компьютеров задачи с пентамино начали исследовать на них. В главе 12 уже упоминалось о том, как Дана Скотт с помощью компьютера нашла все способы составления из двенадцати элементов пентамино шахматной доски размером 8х8 с квадратным отверстием в четыре клетки в центре. Было найдено 65 принципиально различных решений (два решения, получающиеся одно из другого поворотом или отражением, считаются одинаковыми). К. Б. Хейселгроув, математик из Манчестерского университета, перечислил с помощью компьютера все возможные варианты прямоугольника размером 6х10, сложенного из двенадцати пентамино. Он нашел 2389 различных решений, не считая тех, которые получаются друг из друга поворотами и отражениями! Кроме того, он проверил программу, составленную Даной Скотт для шахматной доски 8x8.

Из пентамино получаются прекрасные головоломки. На рис. 241,а изображена пирамида из 64 клеток, которую можно сложить из двенадцати элементов пентамино и квадратного тетрамино 2x2.

Необыкновенно сложно собрать из двенадцати пентамино крест, показанный на рис. 241,б. Для фигуры, изображенной на рис. 241,в, решения до сих пор не найдено (никто ее не сложил, но и невозможность построения тоже не доказана). Даже для случая, когда отверстие в форме мономино вырезано в другом месте, решения тоже не найдено. Рис. 241,г представляет собой фигуру, наиболее близкую по форме к предыдущей. По-видимому, также неразрешима головоломка Герберта Тейлора, показанная на рис. 241,д; правда, до сих пор никому не удалось доказать, что решения не существует.

К счастью, не все нерешенные задачи окутаны мраком неизвестности. Так, Т. М. Робинсон доказал, что, например, фигуру, которая изображена на рис. 241, е, нельзя сложить из двенадцати пентамино.

Рис. 241

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

Полимино, занимающие четыре квадрата шахматной доски, называются тетрамино. В отличие от пентамино из пяти его различных элементов нельзя сложить прямоугольник. Для доказательства раскрасим в шахматном порядке прямоугольники площадью в 20 квадратов — их всего два: 4х5 и 2х10 (рис. 242).

Рис. 242

Четырьмя из пяти элементов тетрамино можно накрыть два черных и два белых квадрата (рис. 243), а пятый, Т-образный элемент, всегда покрывает три квадрата одного цвета и один — другого.

Рис. 243

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

С другой стороны, если взять несколько разных элементов пентамино, то любой из них вместе с пятью тетрамино образует набор, из которого можно построить квадрат размером 5x5. Два примера таких построений показаны на рис. 244.

Рис. 244

Возникает интересный вопрос: сколько разных пентамино можно использовать для этой цели?

Аспирант-математик Орегонского университета Р. Джуэтт предложил задачу о домино (полимино из двух квадратов), совершенно непохожую на те задачи, которыми мы занимались до сих пор. Существует ли такой прямоугольник, сложенный из костей домино, в котором нельзя провести ни вертикальную, ни горизонтальную прямую, соединяющую противоположные стороны? В прямоугольнике, изображенном на рис. 245, для примера такая линия проведена между верхним и нижним основаниями. Если представить себе, что вместо домино взяты кирпичи, то существование такой линии («шва») будет свидетельствовать о непрочной кладке.

Рис. 245

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

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

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

С тех пор как эта глава появилась в Scientific American, в изучении полимино и «прочных» прямоугольников произошли большие изменения. В 1965 году вышла книга Голомба «Полимино», в которой проводится тщательное исследование предмета.[77]