lunes, 22 de agosto de 2011

Problema del día 22 de Agosto.

Sean $k, t\in \mathbb{N}$, $k,t,\ge 2$, primos relativos. Comenzamos con la permutación $(1,2,...,n)$ y podemos intercambiar de lugar dos enteros si su diferencia es $k$ o $t$. Demuestra que con es posible obtener cualquier permutación de $1,2,...,n$ aplicando cambios permitidos si y sólo si $n\geq k+t-1$.

9 comentarios:

IrvinG dijo...

No me acuerdo si ya les había puesto este problema... Si sí me avisan para poner otro.

José.Ra dijo...

Yo no lo había visto. Saguro que es n>=t+k-1 ? Creo que tengo una parte del si y sólo si, pero dudo por lo del mayor a t mas k menos uno

IrvinG dijo...

Ya lo chequé de nuevo y si está bien.

jorge garza vargas dijo...

Ya me salió. Está padre.

IrvinG dijo...

Jajaja, pues qué padre que te salió, pero al menos escribe algo de tu solución.

jorge garza vargas dijo...
Este comentario ha sido eliminado por el autor.
jorge garza vargas dijo...

Escribiré las ideas principales.
Decimos que dos enteros $a$ y $b$ son conexos si se puede "llegar" de $a$ a $b$ sumando o restando $k$ o $t$ sin "salirse" del intervalo $[1,n]$.
Es claro que la conectividad es conmutativa y transitiva.
S.P.G $k>t$.
Si $n\geq k+t-1$ demostraremos que cualquier pareja del conjunto es conexa. Es claro que si $x$ y $y$ pertenecen a la misma clase $(mod t)$ entonces $x$ y $y$ son conexos, sólo tenemos que demostrar que las clases son conexas entre sí. Sea $r$ el residuo de $k (mod t)$, entonces ${r,2r...(t-1)r}$ son todos residuos distintos $(mod t)$ y en ninguno está el $0$, después a los números ${1,2...t-1)$ se les puede sumar $k$ y y la suma será menor o igual a $n$, comenzando con el $r$ le sumaremos $k$ y pasaremos a la clase $2r$, de donde restando $t$ algunas veces se puede llegar al residuo de $2r$ $(mod t)$ el cual es menor o igual a $t-1$ por lo que le podemos sumar $k$, si continuamos así vemos que las clases $1,2...t-1$ son conexas entre sí, y la clase $t$ la obtenemos sumándole $k$ al menor elemento de la clase $-r$ por lo que todas las clases son conexas entre sí.
Sean $a_0$ y $a_n$ dos números conexos, sean $a_1, a_2...a_{n-1}$ los números por los cuales se pasa para "llegar" de $a_0$ a $a_n$, entonces la diferencia entre $a_j$ y $a_{j+1}$ es $t$ o $k$ por lo que dos números consecutivos de la sucesión se pueden intercambiar, de ahí se ve que se puede llegar aplicando los pasos permitidos a que $a_0$ ocupe el lugar de $a_n$ y viceversa, y que los otros $a_i$ se queden fijos. Con esto se demuestra que si dos números son conexos entonces se puede hacer una transposición entre ellos, y como toda permutación se puede expresar como producto de composiciones, entonces toda permutación se puede lograr aplicando cambios permitidos.

jorge garza vargas dijo...
Este comentario ha sido eliminado por el autor.
jorge garza vargas dijo...

Luego si, $n$ es menor a $k+t-1$ utilizamos un grafo en donde cada entero del conjunto es un vértice y hay una arista entre dos de ellos si tienen diferencia $k$ o $t$, luego usando ideas parecidas a la demostración anterior y utilizando que $(t-1)+k>n, t+k>n, (n-t)-k<1, (n-t+1)-k<1$ se ve que de ciertas clases no se puede llegar a otras, por lo tanto la gráfica no es conexa, luego suponiendo por contradicción que sí se puede llegar a cualquier permutación se llega a que la gráfica es conexa, contradicción.

Publicar un comentario