Юный техник 1994-09, страница 70

роге, мы должны сейчас же повернуть обратно, предварительно отметив этот путь двумя черточками (прибытие и обратное направление), как это показано на рис. 2. ф Правило III. Если мы приходим на известный нам перекресток таким путем, который уже раз прошли раньше, то, отметив этот путь второй черточкой, отправляемся дальше путем, которым мы еще не шли, если только такой путь существует. Этот случай изображен на рис. 3.

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

Придерживаясь точно указанных правил, мы обойдем два раза все линии сети и придем в точку отправления. Это можно доказать, сделав и уяснив себе предварительно такие замечания:

1. Выходя из точки отправления, скажем А, мы ставим начальный знак (поперечную черточку).

2. Прохождение через перекресток по одному из предыдущих трех правил каждый раз добавляет два знака (две поперечные черточки) на линиях, которые сходятся в этой точке.

3. В любой момент прохождения лабиринта, перед прибытием на ка-кой-либо перекресток или после отправления из него, начальный перекресток (пункт отправления) имеет нечетное число знаков (черточек), а всякий другой перекресток имеет их четное число.

4. В любой момент, до или после прохода через перекресток, начальный перекресток имеет только один путь, обозначенный только одной черточкой. Всякий же иной из посещенных уже перекрестков может иметь только два пути, обозначенных одной черточкой.

5. После полного обхода лабиринта у всех перекрестков все пути должны иметь по две черточки. Это,

впрочем, входит прямо в условие задания.

Приняв во внимание все вышеизложенное, мы легко убедимся, что если кто-либо отправляется из начального перекрестка, скажем А, и прибывает в какой-либо иной перекресток М, то он не может встретить таких трудностей задачи, которые могли бы остановить его дальнейшее путешествие. В самом деле, в это место он приходит или новым путем, или путем, который уже один раз пройден. В первом случае прилагается первое или второе из данных выше правил. Во втором случае вступление на перекресток М и остановка здесь дала бы нечетное число знаков около него, следовательно, за неимением нового пути надо пойти по уже пройденному один раз пути, и около перекрестка будет четное число знаков (если он не начальный) по замечанию 3.

Пусть наконец мы будем вынуждены закончить наш путь и возвратиться в начальный перекресток А. Назовем эту последнюю линию ZA, то есть она ведет из перекрестка Z в начальный А. Этот путь должен быть тем самым, которым мы отправились первый раз из А, иначе путь можно было бы продолжить. И если теперь мы принуждены этим же путем возвратиться в начальную точку, то это значит, что из перекрестка Z нет уже никакого другого пути, который бы не был уже 2 раза пройден. Иначе это значило бы, что забыли применить первую часть правила III, более того, это значило бы, что в Z есть какой-то путь YZ, пройденный только один раз по замечанию 4. Итак, при последнем возвращении в А все пути в Z должны быть отмечены двумя черточками. Точно так же это можно доказать для предшествующего перекрестка Y и для всех остальных. Другими словами, наше предложение доказано, и задача решена.

66