Задача на инвариантность Круг поделен на n секторов, в каждом с которых стоит фишка. За один ход разрешается любые две фишки переставить в соседние с ними сектора. Как найти все значения n, для которых за определенное количество ходов собрать все фишки в одном секторе?

Предыдущий
вопрос Следующий
вопрос

Для решения этой задачи можно воспользоваться методом инвариантности.

Предположим, что в начальный момент времени существует инвариантная величина - сумма расстояний всех фишек до центральной фишки (расстояние считается по кратчайшему пути по кругу). После каждого хода сумма этой величины будет оставаться постоянной.

Таким образом, чтобы собрать все фишки в одном секторе, необходимо, чтобы в начальный момент времени сумма расстояний всех фишек до центральной фишки была равна 0 (то есть все фишки уже стояли в одном секторе). После каждого хода сумма этой величины не может увеличиваться, так как расстояние между любыми двумя фишками по кругу не увеличивается.

Таким образом, все значения n, для которых можно собрать все фишки в одном секторе, будут такими, что их наименьшее общее кратное с числом фишек равно количеству фишек. То есть надо найти такие n, что НОК(n, n) = n. Подходящими значениями будут простые числа.

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