Есть идея! - [19]
Задачу Лонгфелло нетрудно решить, если начертить схему, изображенную на рис. 4. По существу эта схема ничем не отличается от проекта бассейна, представленного архитектором Ронгом. Требуется определить длину отрезка x. Как и задачу о длине стороны бассейна, задачу о лилии можно решить разными способами. Но если воспользоваться теоремой о пересекающихся хордах, то ответ получается особенно легко и быстро.
А вот еще одна замечательная задача о бассейне, трудная с виду, но легко решаемая, если сообщить, в чем ее изюминка. Дельфин находится у западного края круглого бассейна в точке A, проплывает по прямой 12 м и упирается «носом» в край бассейна в точке B. Повернувшись, он проплывает по прямой в другом направлении 5 м и снова касается края бассейна в точке C, диаметрально противоположной точке A. Какое расстояние пришлось бы преодолеть дельфину, если бы он из точки A поплыл прямо в точку C?
Задача о дельфине решается легко и просто, если воспользоваться теоремой о том, что любой вписанный угол, опирающийся на диаметр окружности, — прямой, и заметить, что угол ABC именно такой угол. Катеты прямоугольного треугольника ABC равны 5 м и 12 м. Следовательно, гипотенуза равна 13 м. Мораль всех этих задач ясна: во многих случаях геометрическую задачу можно решить до смешного просто, если вовремя вспомнить соответствующую теорему евклидовой геометрии.
Пасутся кони на другом поле
На заседании шахматного клуба мистер Бишоп предложил следующую задачу.
Мистер Бишоп. Как поменять позиции черных и белых коней за наименьшее число ходов?
Один из членов клуба сделал 2 первых хода так, как показано на диаграмме. Переставить белых коней в верхние углы доски, а черных — в нижние он сумел за 24 хода.
Другому члену клуба удалось решить задачу мистера Бишопа за 20 ходов.
Но никому не удавалось решить задачу менее чем за 18 ходов, пока не появилась Фанни Фиш.
Мисс Фиш. Есть идея! Я знаю, как решить задачу за 16 ходов, и могу доказать, что ее нельзя решить за меньшее число ходов.
Прежде чем приступить к объяснению, Фанни начертила диаграмму, на которой отрезками прямых изображены возможные ходы каждого коня.
Мисс Фиш. Представьте себе, что отрезки прямых — это нити, а восемь клеток нанизаны на них, как бусины, и их можно расположить по окружности.
Мисс Фиш. Каждый ход на доске соответствует вполне определенному ходу на окружности. Чтобы поменять позиции коней, их необходимо переместить по окружности, двигая в одном направлении.
Мистер Бишоп. Вы совершенно правы, Фанни. Чтобы перейти на новую позицию, каждый из 4 коней должен совершить по 4 хода. Таким образом, задачу можно решить за 16 ходов, а более экономного решения не существует.
Фанни заменила одного из белых коней красным и задала членам шахматного клуба новую задачку: как поменять местами белого и красного коня за наименьшее число ходов?
Как, по-вашему, почему Фанни улыбалась, предлагая эту задачку?
Фанни решила шахматную задачу, сведя ее к изоморфной задаче, допускавшей простое (хотя и далеко не тривиальное!) решение. Поставленную Фанни задачу можно решить тем же методом. Соединив нитями клетки, занятые конями, и развернув получившееся «ожерелье» в окружность, мы увидим, что кони нанизаны на нити в следующем порядке: черный, черный, красный, белый. Фанни улыбалась, так как понимала, что переставить красного и белого коней невозможно: они следуют друг за другом в неизменном порядке, потому что ни один конь не может перепрыгнуть через другого коня, если они оба движутся по кругу (в любом направлении) и обгон запрещен. Понятно ли вам почему?
При движении по окружности по часовой стрелке белый конь всегда следует непосредственно за красным. Если бы белый и красный кони могли поменяться полями, которые они занимали на доске с самого начала, то порядок следования был бы изменен на обратный и красный конь двигался бы по кругу непосредственно за белым. Ясно, что такое перестроение невозможно. Действительно, оно означало бы, что один из коней (либо белый, либо красный) перепрыгнул через двух черных коней. Сведя мини-шахматную задачу к топологической задаче о расположении четырех точек на простой замкнутой кривой, мы получили возможность весьма просто доказать, что решения исходной задачи не существует. Получить доказательство «несуществования» другим способом было бы чрезвычайно трудно. Попробуйте, и вы убедитесь в этом сами.
Вам понравилась задача о перестановке шахматных коней? Вот еще одна такая задача, по трудности даже превосходящая обе предыдущие. Рассмотрим позицию на шахматной доске 3×4, изображенную на рис. 5. Как и прежде, трех черных и трех белых коней требуется поменять местами так, чтобы белые кони оказались на верхней горизонтали, а черные заняли нижнюю горизонталь, причем выполнить перестановку за наименьшее число ходов.
В этом случае, как видно на рис. 6, изоморфный граф более сложен. Этот граф представляет собой диаграмму, на которой показаны все возможные ходы коней, Предположив, что вершины нашего графа — пуговицы или бусины, а ребра — нити, мы обнаружим, что развернуть его в окружность, как в предыдущей задаче, невозможно, но наш граф из нитей и пуговиц нам удастся уложить так, как показано на рис.
