|
|
 |
Условие
В стране Мара расположено несколько замков. Из каждого замка ведут три дороги. Из какого-то замка выехал рыцарь. Странствуя по дорогам, он из каждого замка, стоящего на его пути, поворачивает либо направо, либо налево по отношению к дороге, по которой приехал. Рыцарь никогда не сворачивает в ту сторону, в которую он свернул перед этим. Доказать, что когда-нибудь он вернётся в исходный замок.
Решение
Все замки страны Мара связаны каким-то конечным числом дорог. Если рыцарь странствует по стране достаточно долго, то он проедет достаточно много дорог, поэтому хотя бы по одной дороге AB (A и B – замки) он проедет не менее пяти раз. При этом не менее трёх раз он проедет по этой дороге в одном и том же направлении (скажем, от A к B); поэтому, если из замка B, кроме BA, ведут еще две дороги BC и BD то рыцарь минимум дважды, – скажем, после i-го и после j-го посещения замка B, где j > i, – сворачивал, выезжая из B (куда он оба раза приезжал из A) в одну и ту же сторону, скажем, в сторону замка C. Но из условия тогда следует, что не только в i-е и в j-е посещение B рыцарь приехал в B из одного замка – из A, – но и в A он оба раза приезжал из одного и того же замка P (ведь если рыцарь после B свернул на дорогу BC, например, налево, то в A он должен был свернуть направо после посещения P). Аналогично этому устанавливается, что полностью совпадают пути рыцаря, предшествующие двум рассматриваемым посещениям замка B: в замок P он оба раза попал из одного и того же замка, и т. д. Но тогда, если рыцарь до i-го посещения B миновал, начиная с выезда из своего замка X, какое-то число k замков, то и за k замков до j-го посещения B он снова был в X, что и доказывает утверждение задачи.
