Республиканская олимпиада по математике, 2002 год, 11 класс

В ряд выстроены $n$ кузнечиков. В любой момент разрешается одному кузнечику перепрыгнуть ровно через двух кузнечиков стоящих справа или слева от него. При каких $n$ кузнечики могут перестроиться в обратном порядке? ( А. Кунгожин )

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

Пронумеруем кузнечиков как $1,2,3,4,5,6...n$ тогда движения сказанные в условий на числах будут выглядит как $123 \rightarrow 312 \rightarrow 231$.

Покажем что для чисел вида $n=4k$ такое перестроение возможно. Пусть $123456...n$ разобьем последовательность на группы по $4$ элемента $1234, \ 5678, \ ... \ ,(n-3)(n-2)(n-1)n$ следуя операциям ниже

Для четных два вида причем выполняются последовательно с начало то что сверху, затем что ниже ( в системе слева направо, номер числа который надо перенести, количество шагов которой надо совершить, направление движение)

$\left\{ \begin{gathered} n-4x, \ \ \dfrac{n-(4x+2)}{2} , \ \leftarrow \\ 1, \ 1, \ \rightarrow \\ 0 \leq x \leq \dfrac{n-4}{4} \\ \end{gathered} \right.$ , $\left\{ \begin{gathered} n-4x-2, \ \ \dfrac{n-(4x+4)}{2} , \ \leftarrow \\ 2, \ 1, \ \rightarrow \\ 0 \leq x \leq \dfrac{n-8}{4} \\ \end{gathered} \right.$

Для нечетных

$\left\{ \begin{gathered} n-(2y+1), \ \ \dfrac{n-(2y+2)}{2} , \ \leftarrow \\ \\ 0 \leq y \leq \dfrac{n-4}{2} \\ \end{gathered} \right.$

Таким образом из последовательности $123...n$ можно получить $n...321$, для $4k+1$ так же выполняется , так как достаточно перенести $n$ на первое место. а так как $n=4k+1$ нечетное, нужно совершить $n, \dfrac{n-1}{2}, \leftarrow$ и кузнечики выстроиться в ряд $n|4k|$ и применить тот же алгоритм что описан для $4k$ для $|4k|$ кузнечиков. Выведем некоторое свойство чисел при перемещений, из условия следует что если в каких то четверках $abcd$ поменялись местами два числа $ba$ то меняются автоматический и вторые два, то есть $badc$ используя это свойство, для чисел вида $4k+2$ следует что два последних числа при выполнении операции определяются однозначно, значит если "прогонять" по выше описанному алгоритму, то придем к случаю $n(n-1)(n-2)...|12$ которое противоречить условию, аналогично и в случае $4k+3$.

Ответ только для чисел $4k,4k+1$.