Головоломок вишенка в коктейле

Вид материала

Документы

Содержание В. Набоков, «Защита Лужина» На рис. 87 показан открытый маршрут из журнала The London, Edinburgh and Dublin Philosophical Magazine Если пронумеровать клетки в обратном порядке, получится ква­драт с абсолютно такими же свойствами, как и исходный. American Mathematical Monthly) Сторона число фигур число решений

Подобный материал:

• Психологическое сопровождение замещающих семей, 219.46kb.
• Психологическая коррекция агрессивного поведения детей, 219.57kb.
• С. В. Левина Н. А. Задворочнова публичный доклад, 193.66kb.
• Проектный метод в деятельности доу, 187.91kb.
• Проектный метод в деятельности доу, 214.46kb.
• Альтергот Оксана Петровна. Детский сад является юридическим лицом, имеет полный пакет, 211.9kb.

ГЛАВА 14


Рыцари квадратного стола


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

^ В. Набоков, «Защита Лужина»


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

Из всех шахматных фигур конь, пожалуй, единственная фигура, ход которой представляет собой несимметричную фигуру. Наверняка у писателя вызывала тревогу именно эта «кособокость», «неправиль­ность» движений этой фигуры. По-немецки эта фигура называется der Springer — «прыгун». Он действительно как будто прыгает на две клет­ки вперед, а потом, как кэрроловский Белый рыцарь из Зазеркалья, валится в одну или в другую сторону. По-другому эти несимметрич­ные скачки можно описать так: конь проходит одну клетку прямо, как ладья, а затем поворачивает на 45° влево или вправо и идет на одну клетку по диагонали, как слон. Именно так следует описывать ход фи­гуры «ма» в китайских или корейских шахматах, так как по правилам, действующим в этих странах, «ма» не может сделать ход, если сосед­няя по диагонали клетка занята другой фигурой. «Кейма» — конь в японских шахматах — ходит так же, как и в западных. Однако отличие в том, что двигаться по доске он может лишь вперед.

Британский специалист по головоломкам Генри Эрнест Дьюде-ни называет шахматного кондр«безответственным мелким комеди­антом». Ни одна другая шахматная фигура не дала пищи для такого количества необычных и увлекательных комбинаторных задач. В этой главе мы рассмотрим ряд классических примеров таких задач, а также познакомимся с кое-какими новинками, изобретенными Соломоном В. Голомбом.

Самая старинная из задачек с конем, которой посвящено множе­ство литературы, — это «путешествие коня». В задаче требуется най­ти единственный возможный маршрут движения коня (на досках различного размера и формы), при котором он по одному и только по одному разу окажется на каждой из клеток. Маршрут считается замкнутым, если конь возвращается на клетку, с которой начинал путешествие, и открытым, если его концы не связаны друг с другом ходом коня. Если доска расчерчена на стандартные чёрные и белые клетки, то по маршруту следования коня он будет попеременно ока­зываться на клетках разных цветов. Таким образом, на замкнутом маршруте белых и чёрных клеток должно быть поровну. На доске со стороной, равной нечетному числу клеток, нечетным будет и их об­щее число, так что на таких досках невозможно совершить путеше­ствие с замкнутым маршрутом. На квадратной доске со стороной в 2 или 4 клетки вообще невозможно совершить путешествие, однако на всех квадратных досках большего размера возможны путешест­вия обоих типов. Прямоугольная доска размером 3x4 — это самая маленькая из прямоугольных досок, на которой возможен откры­тый маршрут, а5х6иЗх10 — самые маленькие прямоугольные до­ски для замкнутого маршрута. Задача не имеет решения для любой доски, хотя бы одна из сторон которой меньше 3 клеток, а если хо­тя бы одна сторона равна 4, то на такой доске невозможен замкну­тый маршрут.

Голомб продемонстрировал, как с помощью клеток двух цветов доказать невозможность прохождения маршрута, на примере дока­зательства невозможности замкнутого маршрута на доске с одной из сторон, равной 4. Доска размера 4 х п нумеруется четырьмя буквами (рис. 85). Как видно, перед и после каждой клетки под буквой А на маршруте должна находиться клетка под буквой С. Клеток с такими буквами поровну, и все они должны находиться на одном замкнутом маршруте.

Однако в таком случае клетки В и D вообще не будут входить в маршрут, так как если совершить ход с клетки С на клетку D, то по­пасть с неё на клетку А можно, только предварительно вновь ока­завшись на клетке С. Однако если маршрут замкнутый, то клеток С


на нём будет больше, чем А, а это противоречит условию. Следова­тельно, путешествие по такому маршруту на данной доске невоз­можно. (Подобное доказательство приводится и Аренсом в 1-м то­ме книги Mathematische Unterhaltungen und Spiele на с. 389.)

Неизвестно, сколько возможных маршрутов путешествия коня существует на доске 8 х 8 — их число измеряется миллионами. Вни­мание уделяется обычно тем из них, которые отличаются необыч­ной симметрией или представляют собой матрицу с интересными арифметическими свойствами (при последовательной нумерации клеток на маршруте). На рис. 86 продемонстрирован пример замк­нутого маршрута, предложенный в 1759 году Леонардом Эйлером. В этом путешествии конь вначале проходит всю нижнюю часть до­ски, а затем — верхнюю, и все симметричные относительно разделя­ющей половины линии числа имеют разницу в 32.

На доске 8x8 невозможен замкнутый маршрут с четырёхсторон­ней симметрией (не меняющий конфигурации при повороте в лю­бую сторону на 90°). То же самое верно и для любых других досок со стороной, кратной 4. В то же время на доске размером 6x6 сущест­вует 5 таких маршрутов. Если вас интересует эта задача, вы можете обратиться к книге Мориса Крайчика Mathematical Recreations («Ма­тематика на досуге») 1953 года.


^ На рис. 87 показан открытый маршрут из журнала The London, Edinburgh and Dublin Philosophical Magazine за август 1848 года, пред­ложенный Уильямом Беверли. Я так и не смог выяснить, тот ли это Уильям Беверли, что и знаменитый в то время пейзажист и теат­ральный декоратор. Маршрут Беверли является первым из найден­ных «полумагических» маршрутов, в которых сумма чисел в каждом ряду и каждом столбце равна 260. (Он не может называться полно­стью «магическим», так как суммы чисел по обеим диагоналям от­личаются от константы.) Если разделить доску с маршрутом Бевер­ли на четыре части, как показано на рисунке, то каждый из малень­ких квадратов 4x4 будет магическим по рядам и столбцам, а если поделить на четыре и каждый из них, то сумма чисел в каждом ква­дратике 2x2 будет составлять 130. j:


^ Если пронумеровать клетки в обратном порядке, получится ква­драт с абсолютно такими же свойствами, как и исходный.

Существует ли маршрут, составляющий полностью магический квадрат, на обычной шахматной доске? Это самый животрепещу­щий вопрос из данной области задач. Найдено множество вариан­тов полумагических маршрутов, как открытых, так и замкнутых, но ни в одном из них сумма чисел хотя бы на одной диагонали не соот­ветствует необходимому числу. Можно доказать, что полностью ма­гические маршруты существуют только для квадратных досок со стороной, кратной 4. Так как на доске 4x4 вообще невозможно пройти все клетки ходом коня, то шахматная доска остается самой маленькой из возможных, для которых доказательство существова­ния или несуществования такого маршрута ещё может быть найдено.

Неизвестны примеры магических маршрутов и для доски 12 х 12. Однако найдены такие маршруты для досок со стороной в 16, 20, 24, 32, 40, 48 и 64 клетки. Пример замкнутого маршрута с магическим порядком ходов для доски 16x16 приведен в книге Джозефа С. Ма-дахи Mathematics on Vacation («Математика на досуге») 1966 года из­дания.

Сколько коней можно поставить на одну шахматную доску так, чтобы ни один из них не угрожал другому? Интуитивно кажется, что их должно быть 32, что получается, если выставить коней только на чёрные или только на белые клетки. Однако доказать это не так-то просто. Один из способов доказательства — поделить всю доску на прямоугольники размером 2 х 4. В каждом из них конь, стоящий на любой из клеток, может атаковать лишь одного коня-противника. Следовательно, в этом прямоугольнике может находиться не более 4 коней, не подвергающихся угрозе нападения. Таких прямоуголь­ников 8. Следовательно, на всей шахматной доске коней, не атакуе­мых другими, будет 32.

Голомб обратил внимание на то, что наиболее профессиональное
доказательство (предложенное в 1964 году Ральфом Гринбергом в
бюллетене ^ American Mathematical Monthly) основывается на возмож-
ности данного маршрута коня на шахматной доске. Как мы уже ви-
дели, по ходу этого маршрута чередуются клетки двух цветов. Оче-
видно, что мы не можем поставить на это поле больше 32 коней без
того, чтобы они не начали угрожать друг другу. Точно так же ясно,
что они должны стоять только на белых или только на чёрных клет-
ках. Иными словами, если бы могли поставить на шахматную доску
33-го коня, то в любом маршруте такой конь должен был бы пере-
прыгивать с одной клетки определённого цвета на другую такую же -
а это невозможно. Рассматривая возможность данного маршрута,
мы можем доказать не только то, что на доску можно поставить
только 32 коня, не атакующих друг друга, но и в придачу к этому то,
что два варианта решения такой расстановки не будут пересекаться.
Обобщив это доказательство, мы видим, что оно справедливо для
всех квадратов со стороной в четное число клеток, для которых воз-
можно проложить маршрут. В квадрате с нечетной величиной сто-
роны, естественно, маршрут должен начинаться и заканчиваться на
клетках одного и того же цвета. Таким образом, для таких досок ва-
риант расстановки 32 коней, не угрожающих друг другу, только
один: они будут стоять на клетках того же цвета, что и центральная
клетка доски. к

Теперь давайте обратимся от максимального числа к минималь­ному и попробуем выяснить, каким будет минимальное число ко­ней, расставленных на квадратной доске так, чтобы все незанятые клетки подвергались угрозе нападения со стороны хотя бы одного из них? В следующей таблице приведены значения для квадратов с размерами от 3 до 10, а также число возможных решений (не учиты­вая поворотов и зеркальных отображений).


^ СТОРОНА ЧИСЛО ФИГУР ЧИСЛО РЕШЕНИЙ

3	4	2
4	4	3
5	5	8
6	8	22
7	10	3
8	12	1
9	14	1(?)
10	16	2(?)

Примеры решений для квадратов со стороной от 3 до 8 показаны на рис. 88. В различных изданиях часто печатается единственный вариант решения для стандартной шахматной доски.

Возможные варианты для следующих по размеру досок — 9 х 9 и 10 х 10 клеток — изучены мало. Решение для доски 9x9 принято считать единственным, однако доказательства его единственности не существует, точно так же, как и доказательства того, что для дос­ки 10 х 10 таких решений два. Читатель может попробовать самосто­ятельно найти хотя бы эти три уже известных решения.

Обратите внимание, что в квадрате 7 х 7, где все незанятые клет­ки атакованы, могут быть атакованы и все занятые клетки, а в квад­рате 8x8 под угрозой оказываются только четыре такие клетки. Ес­ли добавить в условие задачи, что атакованы могут быть только не­занятые клетки, то для каждой доски потребуется большее число ко­ней. (Я признателен за предоставление решений для доски 8x8 Виктору Милли.)

На рис. 89 слева показано, как можно расположить на доске раз­мером 11x11 двадцать два (22!) коня так, чтобы все незанятые клет­ки могли бы быть атакованы и вместе с тем под угрозой не находил­ся бы ни один конь. Это решение было напечатано в парижском журнале Ulntermediare des Mathematiciens в выпуске 5 от 1898 года. Считалось, что данное число фигур, удовлетворяющее условиям за-





Рис. 88.

Решения для досок со стороной от 3 до 8


дачи, минимально, даже если разрешить им нападать на другие фи­гуры. Однако в 1973 году Бернар Лемэр, также парижанин, нашел замечательное решение для 21 коня, показанное на рис. 89 справа. Впервые оно появилось в Journal of Recreational Mathematics, вып. 6, осень 1973 г.

Все незанятые клетки на доске 12 х 12 можно атаковать при по­мощи 24 коней, как показано на рис. 90. Это лучшее известное ре­шение, если не допускается нападения на другие фигуры. В обоих случаях других решений неизвестно.

В труде Аренса (том 2, с. 359) приводятся самые известные реше­ния для досок размером 13 х 13, 14 х 14 и 15 х 15 клеток, где коням разрешается атаковать не только свободные, но и занятые клетки. Число минимально необходимых дда этого фигур составляет соот­


ветственно 28, 34 и 37. В 1967 году Гарри О. Дэвис понизил рекорд для доски со стороной 14 до 32 коней. Мы впервые публикуем его решение, обладающее двусторонней симметрией (см. рис. 91).


Если мы будем искать решение для количества коней, требую­щихся для нападения на все без исключения клетки доски, свобод­ные и занятые, то самый простой способ поиска — это изобразить на прозрачной бумаге два варианта расстановки - для минимального числа коней, требующихся для нападения на все чёрные и все белые клетки. Затем, при наложении друг на друга двух рисунков разными способами, можно найти окончательные решения. Дьюдени в своей книге Amusements in Mathematics («Занимательная математика») по­ясняет, что на шахматной доске расставить минимальное число ко­ней (7) для нападения на все клетки одного цвета можно лишь дву­мя способами. Накладывая найденные варианты, можно обнару­жить всего три решения для 14 коней, не считая поворотов и зер­кальных отражений. Работы, посвященные подобным задачам для больших по площади досок, мне неизвестны.


ШАШМАТЫ


Примерно в 1947 году Голомб придумал комбинированную игру, со­четающую в себе особенности шахмат и шашек, которую назвал «шашматы». Так же как в шашках, игра ведется на чёрных клетках 64-клеточной доски. Так как на такой доске конь не может ходить так, как принято в шахматах, не покидая при этом чёрных клеток, Голомб «модифицировал» коня, которого позднее окрестил «коком» (пова­ром). Эта фигура ходит не на две, а на три клетки по прямой, а затем на одну клетку в сторону. Кок, стоящий в центре доски (обозначен буквой С на рис. 92), может пойти восемью возможными способами.

Если углубиться в историю, то окажется, что кок, вроде бы изобре­тенный в XX веке, уже существовал в персидских шахматах XIV в. Тог­да эту фигуру называли верблюдом. Нам стало известно о правилах этой сложной древней игры благодаря сохранившемуся манускрипту, наиболее полный перевод которого приводится в книге Дункана Форбса History of Chess («История шахмат»). Эта игра называлась шах­матами Тамерлана, так как великий завоеватель якобы был большим её поклонником. Помимо двух верблюдов с каждой стороны в этих шахматах дополнительно присутствовали также по два змея (соответ­ствующих нашим коням) и две очень сильные фигуры, носящие на­звание «жирафов». Жираф мог ходить на одну клетку по диагонали, а затем прямо на любое число клеток. Леонард Эйлер занимался разра­боткой маршрутов на различных досках для такой фигуры.

«Изобретение кока, — пишет Голомб, - тут же породило две про­блемы: во-первых, можно ли найти для кока на шахматной доске та­кой же маршрут путешествия, как для коня, во-вторых, каково мак­симальное число коков, которых можно расставить на доске, не подвергая их нападению?»

Для ответа на первый вопрос Голомб использовал видоизменен­ную доску, предложенную его коллегой Ллойдом Э. Уэлчем (см. рис. 93). Доска с зигзагообразными сторонами с клетками, в два раза превосходящими по размеру клетки нормальной шахматной доски, накладывается на обычную доску так, чтобы каждая черная клетка на шахматной доске соответствовала одной клетке верхней доски. Теперь на новой доске можно играть в любую игру, для которой тре­буются только чёрные клетки шахматной доски. Нужно только со­ответствующим образом подогнать под конфигурацию доски ходы фигур. Так как на новой доске ряды и столбцы обычной доски пре­вращаются в диагонали, то для соответствия такому расположению слон должен ходить по такой доске, как ладья на обычной, и наобо­рот. Играть на такой доске в шашки можно, расставив белые шаш­ки на клетки с 1 по 12, чёрные - с 21 по 32 и двигаясь не по диаго­нали, а по прямой. (Кстати, вам никогда не приходило в голову, что из-за того, что для игры в шашки нужны клетки только одного цве­та, то на одной доске одновременно можно играть две абсолютно независимые партии в шашки, используя для каждой партии клетки разных цветов?)


Что еще занятнее, обращает внимание Голомб, ходы кока на шахматной доске превращаются на доске Уэлча в ходы коня. Таким образом, кок может совершить на шахматной доске путешествие, аналогичное путешествию коня на доске Уэлча. Один из маршрутов такого путешествия: 1 - 14 — 2 — 5 — 10 — 23 — 17 — 29 — 26 — 32 — 20 — 8 - 19 — 22 — 9 — 21 — 18 — 30 — 27 - 15 — 3 — 6 — 11 — 24 — 12 — 7 -4— 16 — 28 — 31 —25 — 13. Эти номера соответствуют путешествию кока по черным клеткам шахматной доски. (Два других замкнутых маршрута кока по черным клеткам шахматной доски описаны в книге Мориса Крайчика Mathematical Recreations («Математические развлечения»).)

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

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

Если вы хотите попробовать сыграть в голомбовы шашматы, вам нужно расставить фигуры так, как показано на рис. 94. Восемь пешек (М) ходят, как шашки. Два короля (К) ходят, как дамки в шашках. Слон (В) ходит так же, как в шахматах, а повар (С) — как описано выше. Так же как шахматный конь, кок не блокируется фигурами, стоящими на промежуточных клетках его хода. Пешки и короли «едят» фигуры так же, как в шашках, перепрыгивая через «жертву». Слон и кок «едят» по шахматным правилам — попадая на ту же клетку, где стоит «жертва». Если положение вашей фигуры позволяет «съесть» фигуру противника по шашечным правилам, вы обязаны бить, за исключением тех случаев, когда одновременно возможно «съесть» другую фигуру по-шахматному (в таком случае вы можете выбирать, каким способом «есть» фигуру противника). Фигуры, находящиеся под угрозой по шахматным правилам, брать не обязательно. Пешку, добравшуюся до последней линии, следует превратить в короля, слона или кока.

Ходят по очереди. Цель игры — «съесть» всех королей противни­ка. Таким образом, при соответствующих обстоятельствах решение о том, в какую фигуру превратить пешку, имеет большое значение, как указывает Голомб. Превращение её в короля дает плюс к защи­те, в слона или кока — к нападению. Так же как в шашках, заблоки­рованная фигура выходит из игры.

1.М22- 17

М23 - 19

С32 - 20

С20 х М8

С8 х К2

1.С1-13 2. С13-18 З.С18хК30

С30 - 18

С18хК31 (выигрыш)