Карточки

[wpoms.]

Имеется файл с 1000 карточек, пронумерованных числами от 1 до 1000, расположенных в порядке возрастания номеров. К карточкам применяют такую операцию: первую карточку ставят между последней и предпоследней, далее первую карточку (ее номер 2) ставят на последнее место, тем самым первой становится карточка с номером 3. Покажите, что после выполнения 1000 подобных операций все карточки снова будут расположены в порядке возрастания номеров. Проверьте возможность достижения подобного результата (n операций для n карточек), если в файле находится нечетное количество карточек.

@темы: Комбинаторика

Comments

[Adjirranirr]

Рассмотрим два оператора, действующие на вектор `V` размерности `2n` — оператор циклического сдвига влево `L` и оператор, меняющий местами два последних элемента `S`. Тогда `S^{2} = S^{2n} = \text{id}`, `L^{2n} = \text{id}`, где `\text{id}` — тождественное отображение.
Тогда группа `G = (: S,\ L\ |\ S^{2}, L^{2n} ` имеет конечный порядок; при этом, очевидно, группа ассоциативна, так как умножение группы соответствует ассоциативной композиции операторов (или произведению матриц).
Пусть `X` — операция, применяемая к карточкам. Тогда `X = L S L`, и `X^{2n} = (L S L)^{2n}`; тогда `S L X^{2n} L = SL (LSL) (LSL) ... (LSL) L = (SLL) (SLL) ... (SLL) = (SL^2)^{2n + 1}`.
Разобьем элементы вектора `V` на рядом стоящие пары с номерами `(2i,\ 2i + 1)` (нумерация начинается с нуля). Тогда оператор `S` меняет местами два элемента пары, а оператор `L^2` циклически сдвигает вектор, изменяя номер пары, но не ее элементы. Тогда после `n` применений оператора `SL^2` элементы каждой пары поменяются местами, и, соответственно, после `2n` применений — поменяются местами дважды. Таким образом, `(SL^2)^{2n} = \text {id}`. Тогда `SL X^{2n} L = SL^2 <=> SL X^{2n} = SL <=> X^{2n} = \text {id}`.

Пусть теперь размерность вектора `V` равна `2n + 1`. В матричном представлении оператор `L` имеет вид `L = ((0,1,0,,0,0,0),(0,0,1,dots,0,0,0),(0,0,0,,0,0,0),(,vdots,,ddots,,vdots,),(0,0,0,,0,1,0),(0,0,0,dots,0,0,1),(1,0,0,,0,0,0))`, оператор `S` имеет вид `S = ((1,0,0,,0,0,0),(0,1,0,dots,0,0,0),(0,0,1,,0,0,0),(,vdots,,ddots,,vdots,),(0,0,0,,1,0,0),(0,0,0,dots,0,0,1),(0,0,0,,0,1,0)) `. Тогда `det (L) = 1`, `det(S) = -1`. Тогда `det (X^(2n + 1)) = det(X)^(2n + 1) = det(L S L)^(2n + 1) = (det(L)det(S)det(L))^(2n + 1) = -1 != 1`, и `X^{2n + 1} != \text {id}`, т.е. для нечетного количества карточек `n` за `n` операций расположить их снова в порядке возрастания невозможно.