¿Por qué hay que dar un número par de vueltas para volver a la lista original?

Question

Considere la lista de números $[1, \cdots, n]$ para algún número entero positivo $n$ . Dos elementos distintos $i$ y $j$ de la lista se puede cambiar en un flip . Por ejemplo, dejemos que $f$ ser un tirón que cambie $2$ y $4$ . Entonces $f([1,2,3,4]) = [1,4,3,2]$ . Consideremos ahora una secuencia de $k$ flips $f_1, \cdots, f_k$ de la lista $[1, \cdots, n]$ tal que $f_1(f_2(\cdots f_k([1,\cdots,n])\cdots)) = [1,\cdots, n]$ es decir, realizando todas las vueltas se obtiene la lista original. Entonces $k$ debe ser uniforme.

Me gustaría encontrar una prueba de esta proposición lo más elemental posible. Ya se me ocurrió una justificación usando grupos de permutación que va como sigue:

Cada vuelta $f_i$ corresponde a una transposición de la lista $[1, \cdots, n]$ . Dado que la composición $f_1f_2\cdots f_k$ resulta en la identidad, debe ser una permutación par. Por lo tanto, cualquier representación de $f_1f_2\cdots f_k$ como producto de transposiciones debe contener un número par de transposiciones. En particular, dado que cada $f_i$ es una transposición, se deduce que $k$ debe ser uniforme.

Esta "prueba" trivializa el enunciado del problema tal y como es, utilizando hechos relativamente potentes sobre los grupos de permutación. ¿Existe una prueba de menor nivel que evite el uso de estos resultados? (Lo ideal sería que dicha prueba evitara por completo los grupos de permutación y fuera comprensible para los profanos).

Edito: para aclarar (ya que esta pregunta no ha recibido tanta atención como esperaba), cualquier prueba que evite volver a derivar estos potentes resultados sobre las permutaciones sería suficiente. Básicamente querría una prueba que no demuestre mucho más de lo que requiere la pregunta, es decir, que no tenga una parte donde diga "en particular".

Answer 1

Aquí hay una prueba combinatoria (que no estoy seguro si es del grupo de permutación).

Cuenta el número de "pares invertidos" en la lista. Lo que quiero decir con par invertido es un par de números en el que el de mayor valor va antes que el de menor. Por ejemplo, en $[2,1,3,4]$ , $(2,1)$ es un par invertido pero $(1,3)$ no lo es.

Ahora observa el cambio del número de pares invertidos cuando se realiza un volteo. Digamos que la lista es $[\cdots,a,\cdots,b,\cdots]$ y damos la vuelta $a,b$ convirtiéndola en $[\cdots,b,\cdots,a,\cdots]$ . Debería ser obvio que los que están delante o detrás no aportan ningún cambio. Además, para los que están en medio, vamos a llamar a uno de ellos $c$ sólo contribuirá si $a<c<b$ o $a>c>b$ . $+2$ para los primeros y $-2$ para este último. Y por último, el $a,b$ par. $+1$ si $a<b$ y $-1$ si $a>b$ . De todos modos, el número total cambia por un número impar. Ya que tiene el número total de $0$ al principio y quieres $0$ al final, tienes que voltear un número par de veces.

Espero que esto te ayude.

Answer 2

Sus vueltas de $[1,\ldots,n]$ son precisamente transposiciones de $\{1,\ldots,n\}$ Así que demostrar tu afirmación sobre los volteos es inmediatamente equivalente a demostrar la poderosa afirmación sobre los grupos de permutación de que la identidad no es el producto de ningún número impar de transposiciones. Por lo tanto, es inevitable apoyarse en estos poderosos resultados o rederivarlos. Trataré de rederivarlos de forma elemental.

---

Dejemos que $f_1,\ldots,f_k$ vueltas de $[1,\ldots,n]$ tal que $f_1\circ\cdots\circ f_k$ es la identidad. Queremos mostrar $k$ está en paz. Esto es evidentemente cierto para $k=2$ y a partir de aquí procedemos por inducción, de modo que $k>2$ y supongamos que lo anterior es válido para todos los $k'<k$ . Utilizaré la notación de ciclo aquí y allá para ser más breve.

Una observación clave que puede ilustrarse claramente al profano con un ejemplo, son las identidades $$(cd)(ab)=(ab)(cd)\qquad\text{ and }\qquad(bc)(ab)=(ac)(bc),$$ lo que significa que un giro que hace mover $a$ seguido de un giro que no lo hace mover $a$ tiene el mismo resultado que alguna vuelta que no lo hace mover $a$ seguido de un giro que hace mover $a$ . Una imagen lo ilustra: $$\texttt{These aren't the most illustrative pictures.}$$ En las identidades anteriores es importante observar que el número de vueltas se mantiene igual, y el número de vueltas que se mueven $a$ también se mantiene igual, mientras que empujando el flip que se mueve $a$ a la izquierda.

Dejemos que $a$ sea un número conmutado por $f_1$ . Debido a que la secuencia de volteos resulta en la identidad debe haber otro volteo que cambie $a$ . Sea $f_i$ sea el siguiente, es decir, el que tenga la menor $i$ . Usando las identidades anteriores podemos empujar esta vuelta a la izquierda para obtener una secuencia que comienza con $f_1$ seguido de otro giro que mueve $a$ que sigue dando como resultado la identidad. Todo ello manteniendo el mismo número total de vueltas, y el mismo número de vueltas cambiando $a$ . Si ahora las dos primeras vueltas son distintas entonces la identidad $$(a\ b)(a\ c)=(a\ c)(b\ c),$$ que se mantiene para distintos $a$ , $b$ , $c$ se obtiene una secuencia de la misma longitud con una conmutación menos. $a$ y aún así empezar con una conmutación de volteo $a$ . Podemos repetir este proceso para la siguiente vuelta $f_j$ Conmutación $a$ y seguir repitiendo hasta que las dos primeras vueltas sean no distinto. Cada vez que repetimos este proceso el número de vueltas que se mueven $a$ disminuye en $1$ y este número no puede ser $1$ Así que sera obtener una secuencia que comience con dos volteos que sean no distinto. Esto significa que las dos primeras vueltas se cancelan, y por lo tanto que la secuencia restante de $k-2$ también da como resultado la identidad. Entonces por hipótesis de inducción $k-2$ es par, y por lo tanto $k$ está en paz.

Answer 3

Dejemos que $\ell=(x_1,x_2,\ldots, x_n)$ sea una lista de los números de $[n]$ . Para cada $k\in[n]$ denotar por $p_k$ el número de $x_i\ (1\leq i<k)$ con $x_i>x_k\,$ y llame a $\beta(\ell):=\sum_{k=1}^n p_k$ el maldad de $\ell$ . Es fácil convencerse de que una transposición ("flip") $\tau:\>\ell\mapsto\ell'$ cambia la maldad por $\pm1$ . De ello se desprende que un número impar de vueltas no puede restaurar un $\ell$ a su versión original.

Answer 4

El gráfico de transposición completo $X_n$ se define como el gráfico cuyo conjunto de vértices es el grupo simétrico $S_n$ y dos vértices son adyacentes siempre que se diferencien por una transposición. Es fácil ver que este grafo es bipartito, siendo la bipartición el conjunto de permutaciones pares y el conjunto de permutaciones Impares. Se quiere demostrar que cualquier recorrido en este grafo que empiece en el vértice identidad y vuelva al vértice identidad tiene longitud par (esto es cierto para cualquier vértice inicial, no sólo para la permutación identidad). Esto está claro porque un grafo bipartito no contiene ciclos Impares, pero la prueba de que el grafo de transposición completo es bipartito utiliza la noción de permutaciones pares e Impares.

Tal vez se pueda dibujar (para los profanos) un grafo de transposición completo de este tipo en forma de grafo bipartito (para valores pequeños de $n$ ), y luego explicar que en un grafo bipartito si se parte de un vértice del conjunto de vértices de la izquierda y se vuelve a un vértice del conjunto de vértices de la izquierda (puede ser incluso un vértice diferente al inicial), entonces hay que haber atravesado un número par de aristas.

En lugar de utilizar el concepto de permutaciones pares, tal vez puedas utilizar el concepto de número de inversiones de una permutación. Puedes limitarte a hacer permutaciones sólo de elementos adyacentes. Cada intercambio adyacente cambia el número de inversiones en 1. Y así volver a la misma permutación debe haber utilizado un número par de intercambios adyacentes. El gráfico correspondiente en el conjunto de vértices $S_n$ se llama el grafo de la burbuja y es bipartito (de hecho, es un subgrafo del grafo de transposición completo), siendo la bipartición el conjunto de permutaciones que tienen un número par de inversiones y las que tienen un número impar de inversiones. Ahora puedes demostrar que cualquier permutación arbitraria (es decir, incluyendo las no adyacentes) cambia el número de inversiones en un número impar y, por lo tanto, corresponde a pasar de una parte de la bipartición a la otra en este gráfico de ordenación de burbujas. (Esencialmente estás utilizando el hecho de que una permutación es par si tiene un número par de inversiones).

Answer 5

El valor de k será positivo ya que para devolver dos números a su posición tenemos que hacer dos volteos.

Por ejemplo, para [1,2,3,4,5] primero hemos volteado una vez, es decir, 2 y 5, y ahora para recuperar el conjunto original tenemos que volver a voltear 2 y 5. Ahora bien, si utilizamos k volteos, entonces debe ser par, ya que hay que invertir lo que se invierte por k-1 volteos.