|
|
 |
Условие
Клетчатая полоска 1×1000000 разбита на 100 сегментов. В каждой клетке записано целое число, причём в клетках, лежащих в одном сегменте, числа совпадают. В каждую клетку поставили по фишке. Затем сделали такую операцию: все фишки одновременно передвинули, каждую – на то количество клеток вправо, которое указано в её клетке (если число отрицательно, то фишка двигается влево); при этом оказалось, что в каждую клетку снова попало по фишке. Эту операцию повторяют много раз. Для каждой фишки первого сегмента подсчитали, через сколько операций она впервые снова окажется в этом сегменте. Докажите, что среди полученных чисел не более 100 различных.
Решение
Для каждой клетки первого сегмента определим её маршрут – последовательность клеток, которые проходит стоящая на ней фишка до возвращения в первый сегмент. Клетка "возвращения" в маршрут уже не входит. Длиной маршрута назовём количество входящих в него клеток. Это и есть количество операций, которое подсчитывается. (Если после первой операции фишка остается в первом сегменте, то длина её маршрута равна 1.)
По условию операция осуществляет взаимно однозначное соответствие между клетками полоски и, поэтому, обратима. Следовательно, начав с любой клетки маршрута, можно однозначно вернуться к его началу – единственной клетке маршрута, принадлежащей первому сегменту. Значит, через каждую клетку полосы проходит не более одного маршрута. Отсюда же следует, что маршрут не содержит циклов и, поэтому, всегда заканчивается.
Левую клетку каждого сегмента назовём критической. Докажем, что если маршрут не содержит ни одной критической клетки, то сдвинув все его клетки на "единицу" влево, мы получим новый маршрут той же длины. Действительно, для фишки стоящей на клетке такого маршрута, все равно: сначала сдвинуться на одну клетку влево, а потом сделать ход-операцию, или сначала сделать ход, а потом сдвинуться влево. Поскольку, ход из конца старого маршрута ведёт в первый сегмент, то сдвиг влево из этого сегмента не выводит. Поэтому сдвиг переводит конец старого маршрута в конец нового, то есть длина маршрута не меняется.
Значит, достаточно рассмотреть только длины маршрутов, проходящих через критические клетки. Но таких клеток ровно сто, следовательно, и длин соответствующих маршрутов не больше ста.
Замечания
10 баллов
