Есть идея! (Гарднер) - страница 36
При движении по окружности по часовой стрелке белый конь всегда следует непосредственно за красным. Если бы белый и красный кони могли поменяться полями, которые они занимали на доске с самого начала, то порядок следования был бы изменен на обратный и красный конь двигался бы по кругу непосредственно за белым. Ясно, что такое перестроение невозможно. Действительно, оно означало бы, что один из коней (либо белый, либо красный) перепрыгнул через двух черных коней. Сведя мини-шахматную задачу к топологической задаче о расположении четырех точек на простой замкнутой кривой, мы получили возможность весьма просто доказать, что решения исходной задачи не существует. Получить доказательство «несуществования» другим способом было бы чрезвычайно трудно. Попробуйте, и вы убедитесь в этом сами.
Вам понравилась задача о перестановке шахматных коней? Вот еще одна такая задача, по трудности даже превосходящая обе предыдущие. Рассмотрим позицию на шахматной доске 3×4, изображенную на рис. 5. Как и прежде, трех черных и трех белых коней требуется поменять местами так, чтобы белые кони оказались на верхней горизонтали, а черные заняли нижнюю горизонталь, причем выполнить перестановку за наименьшее число ходов.
В этом случае, как видно на рис. 6, изоморфный граф более сложен. Этот граф представляет собой диаграмму, на которой показаны все возможные ходы коней, Предположив, что вершины нашего графа — пуговицы или бусины, а ребра — нити, мы обнаружим, что развернуть его в окружность, как в предыдущей задаче, невозможно, но наш граф из нитей и пуговиц нам удастся уложить так, как показано на рис. 7. Числа на этом рисунке соответствуют номерам клеток на рис. 4 и 5.
Ясно, что задача о перестановке шахматных коней на этом графе изоморфна исходной задаче, но решается несравненно легче. Удастся ли вам найти минимальное решение в 18 ходов?
Метод нитей и пуговиц позволяет проанализировать одну старинную игру. Для нее нам понадобится особая «доска» — звездчатый граф, изображенный на рис. 8, и семь монет или небольших фишек.
Игра состоит в следующем. Положив монету на любую вершину графа, вы можете сдвинуть ее вдоль черной ломаной линии (ребер графа) в любую другую вершину. После того как ход закончен, прикасаться к монете и перемещать ее в другую вершину запрещается.
Затем вы кладете вторую монету на любую незанятую вершину графа и передвигаете ее вдоль ребер в любую другую незанятую вершину. Так вы продолжаете действовать до тех пор, пока все семь монет не займут свое место на вершинах графа.