2019-04-29
В стране Оз имеется несколько замков, из каждого из которых ведут три пути. Странствующий рыцарь выедал из своего родового замка и пустился в путешествие по стране. Рыцарь любит разнообразие; поэтому, доезжая до очередного замка, он каждый раз поворачивает налево, если в предшествующий раз повернул направо, и поворачивает направо, если до этого он повернул налево. (Проезжая первый на своем пути замок, рыцарь может повернуть в любую сторону.) Докажите, что когда-нибудь рыцарь вернется в свой замок.
Решение:
Естественно называть «дорогой» отрезок пути между двумя замками; все замки страны Оз связаны каким-то конечным числом $n$ дорог. Если рыцарь странствует по стране достаточно долго; если это число $\geq 4n + 1$, то хоть по одной дороге $AB$ (где $A$ и $B$ - замки) он проедет не менее 5 раз. При этом не менее 3 раз он проедет по этой дороге в одном и том же направлении (скажем, от $A$ к $B$); поэтому, если из замка $B$, кроме $BA$, ведут еще две дороги $BC$ и $BD$, то рыцарь минимум дважды,- скажем, после $i$-го и после $j$-го посещения замка $B$, где $j > i$, - сворачивал, выезжая из $B$ (куда он оба раза приезжал из $A$) в одну и ту же сторону, скажем, в сторону замка $C$. Но из условий задачи тогда следует, что не только в $i$-e и в $j$-е посещение $B$ рыцарь приехал в $B$ из одного замка - из замка $A$,- но и в $A$ он оба раза приезжал из одного и того же замка (из замка $P$ в обозначениях рис. ведь если рыцарь после $B$ свернул на дорогу $BC$, т. е. налево, то в $A$он должен был свернуть направо, т. е. приехать в $A$ он должен был из $P$). Аналогично этому устанавливается, что полностью совпадают пути рыцаря, предшествующие двум рассматриваемым посещениям замка $B$; тац, в замок $P$ он оба раза попал из одного и того же замка (из замка $U$ рис.), и т.д. Но тогда, если рыцарь до $i$-го посещения $B$ миновал, начиная с выезда из своего замка $X$, какое-то число $k$ замков, то и за $k$ замков до $j$-го посещения $B$ он снова был в $X$, что и доказывает утверждение задачи.
Ответ: Если странствия рыцаря длятся достаточно долго, то найдется такой участок $AB$ пути (где $A$ и $B$ - замки), по которому (в направлении от $A$ к $B$) рыцарь проедет не менее трех раз.