Решение.
Заметим, что при каждом ходе мы узнаём, в какой полуплоскости от- носительно серединного перпендикуляра к шагу находится изотоп. Будем называть ход удачным, если он приближает нас к изотопу, и неудачным в противном случае.
Следующую лемму мы докажем в конце решения, а пока будем пользоваться без доказательства:
Лемма 1. Маршрут, состоящий только из удачных ходов, оптимальный.
Посмотрим на серый шестиугольник. Наша первая цель поставить робота в его вершину, ближайшую к изотопу. Для этого будем действовать так. Сначала ро- бот обходит шестиугольник в направлении, указанном стрелкой, до первого неудачного хода, и затем делает еще один ход назад, откатывающий неудачный. Потом робот делает аналогичную операцию, начиная с друго- го направления*. В результате робот придёт в нужную вершину, сделав не более 4 лишних ходов.
Теперь мы стоим в ѕугловойї точке сектора в 60◦,в котором находится изотоп. Сделаем один шаг по бис- сектрисе этого угла, а второй перпендикулярно одной из сторон угла. На первом шаге мы заведомо приблизи- лись к изотопу. Если на втором шаге мы тоже к нему приблизились, то эти два шага содержатся в одном из кратчайших путей к изотопу. Более того, мы снова ока- зались в ѕугловойї точке сектора в 60◦, в котором нахо- дится изотоп. Если же на втором шаге мы удалились от изотопа, то изотоп находится в полоске, ограниченной серединным перпендикуляром ко второму ходу и стороной угла. После этого достаточно вернуться на один ход назад и идти вдоль этой полоски.
При таком алгоритме общее число ѕлишнихї ходов не превосходит 4 + 2 = 6.
Доказательство леммы: заметим, что если выбросить все рёбра, параллельные од- ному направлению, решётка распадётся на ѕзмейкиї. Рассмотрим змейки, на которых лежат начальная точка и изотоп. Нам нужно перейти с одной из них на другую. Следо- вательно, в направлении, параллельном выброшенным ребрам, необходимо сделать хотя бы столько ходов (по выброшенным рёбрам), каково расстояние между соответствую- щими змейками. Осталось заметить, что любой удачный ход, параллельный некоторому направлению, уменьшает число, соответствующее этому направлению: серединный пер- пендикуляр как раз отделяет одни змейки от других.
* Идти только в одну сторону может оказаться недостаточно, если первый же ход неудачный.
