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$.
Suscribirse a:
Comentarios de la entrada (Atom)
9 comentarios:
No me acuerdo si ya les había puesto este problema... Si sí me avisan para poner otro.
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
Ya lo chequé de nuevo y si está bien.
Ya me salió. Está padre.
Jajaja, pues qué padre que te salió, pero al menos escribe algo de tu solución.
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.
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