Путешествие по Солнечной системе

 

 

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

 

В конце концов, на восьми клетках окажутся монетки в 1 копейку. Оставаясь спиной к зрителям, Вы называете планету, на которой остановился «космический корабль». Здесь на минутку остановимся и убедимся, что у Вас есть монетка в 10 копеек и восемь по 1 копейке. Вместо монет можно использовать кнопки, шашки и прочие предметы, которые будут служить Вам фишками. Теперь я возьму на себя роль волшебника, в то время как Вы будете в роли зрителя. 

 

Выберите одну из девяти клеток и положите на нее монету в 10 копеек. Это полностью свободный выбор с вашей стороны, и, очевидно, у меня нет никакой возможности узнать, что за выбор Вы сделали. Перемещая монету согласно моим инструкциям, Вам следует перемещаться только на одну клетку за один ход, по горизонтали или вертикали. Диагональные ходы не допускаются! Делая каждый ход, Вы записываете букву из названия той клетки, в которую Вы изначально положили монетку. Например, если Вы начинаете путешествие с «Марса», то Вы пишете М-А-Р-С, перемещая гривенник на один квадрат на восток, на запад, на север или на юг в случайном порядке. Один шаг — одна буква. 

 

Когда Вы закончите записывать название стартовой клетки, положите 1 копейку на клетку «Венера». Я, конечно, могу поспорить, что, независимо от того, откуда Вы начали ходить, или как перемещали гривенник, он не остановится на «Венере». Отныне на каждой стадии Вашего «путешествия по Солнечной системе» Вы будете перемещать «космический корабль» только семь раз, независимо от количества букв в названии очередной клетки. Эти шаги Вы, как и раньше, делаете случайно, но теперь они ограничены свободными клетками. Этих свободных квадратов будет все меньше и меньше, поскольку все больше и больше копеек Вы будете класть на матрицу. 

 

 

Когда Вы будете показывать этот фокус кому-нибудь, обязательно повернитесь спиной, давая эти инструкции. Если хотите, можете добавить таинственности, позволив зрителю на нескольких этапах двигаться, записывая по буквам 3-Е-М-Л-Я вместо того, чтобы считать до семи. После того, как он положит копейку на «Луну», Вы можете смело сказать ему, что его гривенник прибыл на «Плутон», даже не оборачиваясь, чтобы своими глазами на это взглянуть. 

 

Почему трюк всегда срабатывает? Ответ познакомит Вас с понятием «четность». Это понятие имеет огромное значение, как в комбинаторной математике, так и в современной физике элементарных частиц. 

 

 

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

 

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

 

Отныне на каждом этапе гривенник будет двигаться нечетное количество раз. И не имеет никакого значения, переместится ли он семь раз (или любое другое нечетное число раз), или будет ходить в соответствии с пятью буквами слова 3-Е-М-Л-Я, или согласно любому другому слову с нечетным количеством букв. Если имя или фамилия кого-либо из зрителей имеет нечетное число букв, Вы смело можете использовать их для написания и ходов. Каждый раз, когда гривенник перемещается, его четность изменяется. Это позволяет Вам направлять копейки на свободные клетки с четностью, противоположной четности гривенника. После восьми этапов незанятой останется только клетка «Луна», а десять копеек будут отдыхать на «Плутон». 

 

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

 

 

А теперь — простая, но хитрая маленькая задачка, в которой использован еще один вид «турне» по той же самой матрице. 
 

Поместите гривенник на «Марс». Вы должны перемещать его последовательно по прямым линиям, каждая из которых может быть любой длины, в горизонтальном, вертикальном или диагональном направлении. Задача состоит в том, чтобы пройтись гривенником по всем оставшимся восьми клеткам и сделать это за наименьшее число ходов. Например, на рисунке вверху показано, как это можно сделать за пять ходов. 

 

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

 

На рисунке внизу показано, как гривенник может совершить турне по Солнечной системе всего за четыре перехода. А кто сказал, что монета не может выскальзывать за пределы квадрата?

 

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

 

 

Если диаметр гривенника меньше, чем сторона клетки, то легко заметить, что он может проходить через часть каждой клетки в два хода. Если же его диаметр больше стороны клетки, достаточно одного хода, как показано ниже: 

 

 

Исходная задача, очевидно, обобщается для ячеек любой прямоугольной решетки, а также для клеток треугольных матриц и других схем. Множество таких задач, обычно в виде «туров» шахматной королевы, можно найти в книге головоломок Сэма Лойда и Генри Э. Дьюдени. Новаторская статья, посвященная проблеме в общем: Соломон В. Голомб, Джон Л. Сэлфридж, «Уникурсальная ломаная линия и другие графы в узлах решеток» (Solomon W. Golomb, John L. Selfridge, «Unicursal Polygonal Paths and other graphs on lattice points» // «Pi Mu Epsilon Journal». Vol.6 (autumn, 1970). P. 101-117). Здесь рассматривается задача найти путь через узлы решеток, а не через клетки. 

 

Чтобы подогреть Ваш интерес к этой, еще мало изученной области рекреационной теории графов, рассмотрим массивы 3 х 4 и 4 х 4, показанные ниже: 

 

 

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

 

 

Для массива 3x4 есть единственная (за исключением симметрии) закрытая схема из 5 отрезков. Три закрытых схемы для массива 4x4 показаны ниже. Детальный анализ случая 4x4 можно найти здесь: Фред Шуг «Эталонная книга математических развлечений» (Fred Schuh, «The Master Book of Mathematical Recreations» (Dover, 1968)). 

 

 

 

M. С. Кламкин доказал, что открытые схемы для n х n массивов (n > 2) можно составить из всего лишь 2n-2 отрезков (American Mathematical Monthly. February 1955. Vol. 62. P. 124). Сэлфридж доказал, что 2n-2 отрезков всегда необходимы (Ibid. June 1955. Vol. 62. P. 443). Голомб и Сэлфридж в статье, которая цитировалась в предыдущем разделе ответов, показали, что то же самое утверждение справедливо и для замкнутых схем при n > 3, а также для схем, которые не превышают периметр квадрата при n > 5. О минимальных схемах для неквадратных моделей узловых решеток известно мало. 

 

Несколько превосходных новых головоломок, основанных на турах королевы для узловых решеток, Вы сможете найти в статье Соломона В. Голомба: Paths on arrays of dots // Journal of Recreational Mathematics. July 1968. Vol. 1. P. 154-156. (Ответы там же: October 1969. Vol.2. P. 220—230.) Также обратите внимание на статью: Scherer Karl. Dot Connection II // Ibid. 1981-82. Vol. 14. №3. P. 232.