Олимпиада имени Леонарда Эйлера 2021-2022 учебный год, II тур регионального этапа

В вершины правильного 100-угольника поставили 100 фишек, на которых написаны номера 1, 2, \ldots, 100, именно в таком порядке по часовой стрелке. За ход разрешается обменять местами некоторые две фишки, стоящие в соседних вершинах, если номера этих фишек отличаются не более чем на k. При каком наименьшем k серией таких ходов можно добиться расположения, в котором каждая фишка сдвинута на одну позицию по часовой стрелке по отношению к своему начальному положению? ( С. Берлов )

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

Комментарии от администратора Комментарии от администратора №1.    
Решение. Пример. Фишку 50 последовательно 99 раз меняем со следующей против часовой стрелки.
   Оценка. Рассуждаем от противного. Пусть $k < 50.$ Будем считать сдвиги фишек относительно их начальных позиций, причем сдвиг по часовой стрелке считаем с плюсом, против часовой — с минусом. Тогда при обмене двух фишек к сдвигу одной из них прибавляется 1, а из сдвига другой вычитается 1. Пусть после нескольких ходов все фишки сместились на одну позицию по часовой стрелке. Тогда полный сдвиг фишки с номером $k$ равен $100t_k+1,$ где $t_k$ — число полных оборотов этой фишки (обороты по часовой стрелке считаются со знаком плюс, а против часовой — со знаком минус). Так как $k < 50,$ фишки с номерами 1 и 51 не могли меняться местами, и потому совершили одинаковое число полных оборотов, то есть $t_1 = t_{51}.$ Аналогично, $t_2 = t_{52},$ $\ldots,$ $t_{50} = t_{100}.$ Поэтому сумма всех сдвигов всех фишек равна $100(2t_1+\ldots+2t_{50}+1).$ Она должна быть равна 0, так как равна 0 сумма сдвигов при каждом ходе. Но она не равна 0, так как сумма в скобках нечетна. Противоречие.