Когда ты была рыбкой, головастиком - я...
Когда ты была рыбкой, головастиком - я... читать книгу онлайн
Имя Мартина Гарднера (р. 1914) хорошо известно в России. За свою долгую жизнь он написал более 70 книг, ставших популярными во всем мире, многие из них издавались и на русском языке. Гарднер — автор огромного количества статей, посвященных математике (на протяжении 25 лет он вел колонку математических игр и фокусов в журнале «Scientific America»), а также фантастических рассказов и эссе на самые разные темы.
В сборник «Когда ты была рыбкой, головастиком — я…» вошли статьи, посвященные вопросам, явлениям или событиям, особенно взволновавшим писателя в последние годы. И о чем бы ни говорил со своими читателями Мартин Гарднер — о науке или о религии, о Честертоне или Санта-Клаусе, о гибели «Титаника» или о политике, — он демонстрирует глубочайший интеллект, мудрость и добрый, тонкий юмор.
Copyright © Martin Gardner, 2009Published by arrangement with Hill and Wang,a division of Farrar, Straus and Giroux, LLC, New York.
Внимание! Книга может содержать контент только для совершеннолетних. Для несовершеннолетних чтение данного контента СТРОГО ЗАПРЕЩЕНО! Если в книге присутствует наличие пропаганды ЛГБТ и другого, запрещенного контента - просьба написать на почту [email protected] для удаления материала
Посмотрев на рис. 5, можно отметить, что для каждого приведенного разбиения количество свободных тримино (не входящих в элементы 2×3) оказывается четным. И это не совпадение. Мне удалось вывести следующий тривиальный закончик. Когда порядок доски — четный, количество свободных тримино при покрытии — нечетное, и наоборот: когда порядок доски — нечетный, число свободных тримино должно быть четным.
Доказать эти равенства просто. Если доска имеет четный порядок, то после удаления одной клетки количество тримино при любом способе покрытия составит величину, равную (n2–1)/3, т. е. нечетное число. В каждом элементе 2×3 содержится два тримино, а значит, общее количество тримино, входящих в состав элементов 2×3, неминуемо окажется четным. Если вычесть это четное число из общего числа тримино (а оно — нечетное), мы получим нечетное число тримино, не входящих ни в один элемент 2×3.
Пусть доска имеет нечетный порядок. После удаления одной клетки на доске останется четное число клеток. «Вычтем» из него четное число тримино, входящих в элементы 2×3, и получим четное число тримино, в такие элементы не входящих.
Выше 7-го порядка
Индуктивное доказательство Голомба применимо к бесконечному числу рядов, чьи элементы удваиваются. В частности, после того как мы успешно покрыли доску 7×7, можно понять, как покрываются доски размером n×n, где n = 2k·7. К примеру, возьмем доску 14-го порядка. Разобьем ее на области, расположив зачерненную доску 7-го порядка в левом верхнем углу и положив одно тримино у нижнего правого угла этой зачерненной доски, подобно тому, как мы проделывали раньше (см. рис. 3, справа). Поскольку доску 7-го порядка можно покрыть, из этого с очевидностью вытекает доказательство для доски 14-го порядка, а далее, по индукции, доказательства для порядков 28, 56, 112…
Подобное доказательство нельзя вывести для доски 10-го порядка, расположив в ее углу квадрат 5-го порядка, поскольку его не всегда удается покрыть (см. рис. 4). Однако с этой сложностью легко справиться, применив несколько иной подход. Разместим в левом верхнем углу квадрат 8-го порядка — его, как нам известно, можно покрыть. Остается угловая область, имеющая ширину 2 и занимающая низ и правую часть большого квадрата (см. рис. 7). Путем поворотов и отражений любую недостающую клетку в квадрате 8-го порядка удается расположить в любом месте этой доски. Таким же образом получаем доказательство для порядков 20, 40, 80 и т. д. Сходное доказательство существует для доски 11-го порядка: квадрат 7-го порядка располагаем в ее углу, и тогда угловая область, занимающая нижнюю и боковую часть большого квадрата, будет иметь ширину 4. Индукция позволяет вывести доказательства и для порядков 22, 44, 88… Понятно, что эта методика дает нам бесконечное количество покрываемых досок, длина сторон которых удваивается (это своего рода удваивающийся ряд). Просто располагайте в левом верхнем углу любой доски заведомо покрываемый квадрат со стороной, которая меньше стороны исходной доски либо равна ей. Если оставшуюся снизу и сбоку область большой доски вам удастся покрыть — значит, и большая доска покрываема.
Обычно труднее всего покрыть доски, у которых длина сторон — простое число. Проблему доски 17-го порядка удается решить, поместив в ее угол квадрат со стороной 13 и оставив внизу и сбоку область шириной 4. Проблему доски 19-го порядка — поместив в ее угол квадрат 14-го порядка (доказательство его покрываемости основано, в свою очередь, на таком же свойстве квадрата 7-го порядка) и получив угловую область шириной 5 (см. рис. 8).
ПОЛНЫЙ И УНИВЕРСАЛЬНЫЙ РЕЗУЛЬТАТ
Занимаясь разбиением этих фигур, я подобрался (но пока недостаточно близко) к тому, чтобы вывести индуктивное доказательство того, что все дефицитные квадраты покрываемы, за исключением квадрата 5-го порядка. Это доказательство в конце концов получили И. Пинг Чу и Ричард Джонсонбау [77]. Чу и Джонсонбау позаботились не только обо всех дефицитных квадратах, но и обо всех дефицитных прямоугольниках! Их индуктивное доказательство — слишком специальное, чтобы его здесь приводить. Коротко говоря, они продемонстрировали покрываемость для всех прямоугольников m×n (включая и квадраты — случай, когда m=n) с числом клеток, кратным 3 после удаления одного поля. Подобные доски покрываемы, если выполняются все четыре необходимых и достаточных условия:
1) m ≥ 2,
2) n ≥ m,
3) если m=2, n должно тоже равняться 2,
4) m ≠ 5.
Прямоугольник 4×7 — самый маленький дефицитный прямоугольник (не квадрат), который можно покрыть с помощью L-тримино. Вот еще одно упражнение: много ли у вас уйдет времени на то, чтобы покрыть такую фигуру с помощью тримино и двух элементов 2×3, если недостающая клетка у этой фигуры располагается в углу?
Кристофер Йенсен показал в своей неопубликованной статье, что если в углу любой доски убрать две клетки, как показано на рис. 9. получившуюся доску нельзя будет покрыть с помощью тримино. Однако, если исключить приведенные пять случаев, доску с длинами сторон 3m–1 и 3n+1 и с любыми двумя недостающими клетками окажется возможным покрыть при следующем необходимом и достаточном условии: либо если n=1, либо если m ≥ 3 и n ≥ 3.
Заключение
Кейт Джонс, основавшая и возглавляющая фирму «Kadon Enterprises», которая выпускает и продает разные симпатичные механические головоломки и другие забавные математические предметы, выпустила на рынок игру под названием «V-21» [78]. Буква V здесь — от «V-тримино», а 21 — число тримино в наборе, где кроме ярко раскрашенных фишек имеется также доска 8-го порядка, на которую их можно класть. Первое задание — положить мономино (квадрат 1-го порядка) в произвольное место доски, а затем покрыть оставшуюся площадь с помощью тримино (т. е. решить задачу для доски 8-го порядка). К игре прилагается сорокастраничное руководство. В нем напечатана короткая статья Нортона Старра «Дефицитная шахматная доска» и приводятся изображения прямоугольных досок и задачи к ним.
Завершим наш рассказ красивейшим симметричным покрытием стандартной шахматной доски (рис. 10).
А вот и ответ на задачу, которую я предложил вам на с. 197:
Глава 12
Ay, мистер Херш, вы «здесь»?
Рубен Херш принадлежит к небольшой группе математиков, убежденных, что математика реальна лишь в контексте человеческой цивилизации. А я — бесстыжий платоник и предпочитаю иной язык мышления, предполагающий, что если из Вселенной исчезнут все разумные существа, то математические объекты и теоремы в каком-то смысле никуда не денутся — даже если не останется никого, кто смог бы писать или говорить о них. Гигантские простые числа продолжают быть простыми, хоть никто и не доказывал, что они являются таковыми. Как выразился однажды Бертран Рассел, даже в центре Солнца дважды два — четыре.
