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

Невозвращенск қаласында $N$ автобус аялдамасы бар, олар 1-ден $N$-ге дейін нөмірленген. Әр маршруттың екі аялдамасы бар: бастапқы және соңғы, автобус тек бір бағытта жүреді. Қаланың автобус желісі келесідей: кез келген аялдамадан шығып, автобуспен қайта оралу мүмкін емес. Мэр егер қандай да бір маршрут үлкен нөмірлі аялдамадан кіші нөмірлі аялдамаға барса, сол маршруттағы аялдамалардың нөмірлері жазылған тақтайшаларды ауыстыруды бұйырады. Мұндай тақтайшаларды ауыстырулар шексіз жалғасуы мүмкін бе? ( К. Иванов )

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

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

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

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