Олимпиада Туймаада по математике. Младшая лига. 2022 год

В городе Невозвращенск $N$ автобусных остановок, пронумерованных числами от 1 до $N$. Каждый автобусный маршрут имеет ровно две остановки: начальную и конечную, автобус едет только в одну сторону, а вся автобусная сеть устроена так, что с какой бы остановки вы ни уехали, вернуться на нее, пользуясь автобусами, не удастся. Когда мэр замечает маршрут, ведущий от остановки с большим номером к остановке с меньшим, он приказывает поменять местами таблички с номерами начальной и конечной остановок маршрута. Могут ли перестановки табличек продолжаться бесконечно? ( К. Иванов )

Комментарий/решение

При перестановке табличек можно считать, что табличка с б\льшим номером доставляется на конечную остановку автобуса. Тогда табличка с номером $N$ будет перемещена лишь конечное число раз. Действительно, если бы табличка с номером $N$ совершала бесконечное количество перемещений, то, поскольку число остановок конечно, она рано или поздно посетила бы уже пройденную остановку, что противоречит условию.

После последнего перемещения таблички с номером $N$ можно провести аналогичное рассуждение для таблички с номером $N-1$, затем для таблички с номером $N-2$ и так далее, вплоть до таблички с номером $1$.

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