415. Путешествие миссис Симпер. На рисунке изображена упрощенная схема маршрута, по которому моя приятельница миссис Симпер собирается путешествовать следующей осенью. Можно заметить, что на схеме представлено 20 городов, соединенных между собой железнодорожными линиями. Миссис Симпер живет в городе \(H\) и хочет посетить все остальные города только по одному разу, возвратившись в конце домой.

Читателю, наверное, будет небезынтересно узнать, что миссис Симпер может выбрать любой из 60 маршрутов, если считать разными маршруты, отличающиеся лишь направлением. Между \(N\) и \(O\), а также между \(R\) и \(S\) дорога проходит через тоннель, но, как истая леди, миссис Симпер категорически против езды по тоннелям. Ей хотелось бы также отложить свой визит в \(D\) на возможно более поздний срок, чтобы иметь удовольствие встретиться со своей старой приятельницей, живущей в этом городе.

Головоломка состоит в том, чтобы при данных обстоятельствах указать миссис Симпер наилучший маршрут.

![](https://cdn.mathpix.com/cropped/2024_05_21_56f37ca27ac3d928838dg-142.jpg?height=617&width=625&top_left_y=331&top_left_x=721)
415. Существует 60 маршрутов, следуя по которым миссис Симпер могла бы посетить каждый город по одному и только по одному разу, закончив путь в \(H\), если считать различными маршруты, отличающиеся только направлением. Однако если леди должна избежать тоннелей между \(N\) и \(O\), а также между \(S\) и \(R\), то можно обнаружить, что число различных маршрутов сокращается до 8 .

Если это заинтересует читателя, то он может попытаться самостоятельно определить все 8 маршрутов. Поступив таким образом, он обнаружит, что маршрутом, удовлетворяющим всем условиям, то есть не включающим в себя два тоннеля и задерживающим визит в \(D\) как можно дольше, окажется маршрут HISTLKBCMNUQRGFPODEAH. Он, несомненно, и будет наилучшим маршрутом.