Эйлер атындағы олимпиада, 2021-2022 оқу жылы, аймақтық кезеңнің 2 туры

1, 2, ..., 100 сандары (нөмірлері) жазылған 100 фишканы осы ретпен сағат тілінің бағыты бойынша 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, так как сумма в скобках нечетна. Противоречие.