Dada una secuencia finita con términos en el conjunto $A=\{0,1,\ldots ,121\}$, está permitido reemplazar cada término por un número del conjunto $A$ de modo que términos iguales se reemplacen por números iguales, y términos distintos por números distintos. (Pueden quedar términos sin reemplazar.) El objetivo es obtener, a partir de una sucesión dada, mediante varios de tales cambios, una nueva sucesión con suma divisible por $121$. Demostrar que es posible lograr el objetivo para toda sucesión inicial.
Última edición por Vladislao el Sab 10 Nov, 2012 4:55 pm, editado 1 vez en total.
Sea [math]\theta = 1,3063778838... Para todo entero positivo [math]k se cumple que [math]\left\lfloor \theta^{3^k}\right\rfloor es un número primo.
Sea [math]A=\{0,1,\ldots, 121\}. Consideremos dos subconjuntos arbitrarios de [math]A, definidos como sigue: [math]X=\{x_1,x_2,\ldots, x_k\} y [math]Y=\{y_1,y_2,\ldots, y_k\} (ambos con la misma cantidad de elementos). Consideremos una función biyectiva [math]f de [math]X en [math]Y, tal que [math]f(x_i)=y_i. Demostrar que, dada una secuencia [math]a_1, a_2, \ldots, a_n de números del conjunto [math]A (no necesariamente distintos), se puede realizar una elección conveniente de los conjuntos [math]X e [math]Y de tal manera que la secuencia [math]f(a_1), f(a_2), \ldots, f(a_n) es tal que la suma de sus términos es múltiplo de [math]121. Nota: [math]f(t)=t si [math]t no está en el conjunto [math]X elegido.
Consideremos nuestra secuencia [math]a_1, \ldots, a_n. Para cada [math]i=0,1,\ldots, 121 sea [math]k_i la cantidad de veces que está el número [math]i en la secuencia. Consideremos el número: [math]S=0\cdot k_0 + 1\cdot k_1 + \ldots + 121 \cdot k_{121}. Es claro que [math]S es la suma de los términos de la secuencia inicial. Supongamos que: [math]S\equiv r \pmod{121} donde [math]0 \leq r < 121.
Separemos el problema en dos casos:
Caso 1) Existe algún [math]k_i coprimo con 11.
Sea [math]k_i coprimo con 11. Entonces [math]k_i es coprimo con [math]121, y por lo tanto existe [math]k_i^{-1} \in \mathbb{Z}_{121} tal que [math]k_i\cdot k_i^{-1} \equiv 1 \pmod {121}.
Supongamos que [math]i\cdot k_i \equiv r_i \pmod {121}, entonces, como [math]k_i es invertible existe algún [math]j tal que [math]j \cdot k_i \equiv r_i-r \pmod{121}.
Si cambiamos todos los números [math]i de nuestra secuencia inicial, por los números [math]j\in \mathbb{Z}_{121}, obtenemos una nueva suma:
Es claro que [math]S'=S-i\cdot k_i + j\cdot k_i \equiv r - r_i + (r_i-r) \equiv 0 \pmod{121}.
Por lo tanto, la nueva suma es divisible por 121.
Caso 2) Todos los [math]k_i son múltiplos de 11.
Sea [math]k_i=11t_i para todo [math]i.
La suma [math]S se puede escribir [math]S=11\cdot (0\cdot t_0 + 1\cdot t_1+\ldos+121\cdot t_{121})=11\cdot S_1\equiv r \pmod{121}.
Si todos los [math]t_i fueran múltiplos de [math]11 no hay nada que hacer, puedes cada [math]k_i sería múltiplo de [math]121, y por ende, la suma [math]S sería múltiplo de [math]121. Vamos a suponer, entonces, que hay algún [math]t_j coprimo con [math]11. Entonces, consideramos [math]j \cdot k_j \equiv r_j \pmod{121}, entonces, [math]j\cdot t_j \equiv s_j \pmod{11}, donde [math]0\leq s_j < 11 (aquí, vendría a ser [math]11s_j=r_j). Como [math]t_j es coprimo con 11, es invertible, y por ende, se puede cambiar [math]j por [math]m de tal manera que: [math]m\cdot t_j \equiv s_j-\frac{r}{11} \pmod{11}. Lo que equivale a: [math]m\cdot (11t_j) \equiv 11\left(s_j-\frac{r}{11}\right) \pmod{121}, es decir: [math]m\cdot k_j \equiv r_j-r \pmod{121}.
Si cambiamos [math]j por [math]m, la suma [math]S cambia por [math]S'= S-j\cdot k_j + m\cdot k_j \equiv r-r_j+(r_j-r) \equiv 0 \pmod{121}.
Luego, la nueva suma es múltiplo de 121 como queríamos.
Sea [math]c_k la cantidad de veces que aparece el término [math]k en la sucesión. La suma inicial es [math]c_1+2c_2+3c_3+\dots+120c_{120}. Bastará hallar una permutación [math](a_0,a_1,a_2,\dots,a_{121}) de [math](c_0,c_1,c_2,\dots,c_{121}) tal que [math]121 divida a [math]a_1+2a_2+3a_3+\dots+120a_{120}.
Tomemos [math]121 números arbitrarios de entre nuestros [math]c_i-es para que empiecen siendo [math]a_0,a_1,a_2,\dots,a_{120}, y nos olvidamos del último [math]c_i, que es [math]a_{121}. Sea [math]S la suma de los [math]121 elegidos; [math]S=a_0+a_1+a_2+\dots+a_{120}. Notemos que sumar [math]S a la expresión [math]0\cdot a_0+1a_1+2a_2+3a_3+\dots+120a_{120} módulo [math]121 mueve los [math]a_i-es un lugar a la derecha (en su defecto [math]a_{120} que está en la última posición de la derecha se va al extremo izquierdo a ser multiplicado por el [math]0). Así, sumar [math]S permuta los [math]a_i-es en la expresión que nos interesa, y si hacemos esto [math]k veces la suma habrá variado en [math]kS. Supongamos que [math]S no es divisible por [math]11. Entonces [math]S es coprima con [math]121 y tras sumas una cantidad conveniente de veces [math]S obtenemos una permutación de los [math]a_i-es para la cual la expresión que nos interesa es múltiplo de [math]121, y hemos terminado. Entonces queda el caso en que [math]S sea múltiplo de [math]11. Pero recordemos que nuestros [math]121[math]a_i-es los elegimos en forma arbitraria. Entonces, lo peor que nos puede pasar es que no importa cuáles [math]121 números elijamos (ó lo que es lo mismo, cuál de los [math]122 dejemos afuera), su suma sea múltiplo de [math]11. Esto es obviamente posible sólo si todos los [math]a_i-es tienen igual resto en la división por [math]11. En tal caso escribamos [math]a_i=11b_i+r, donde [math]r es el resto común. Tras desarrollar y simplificar la condición que queremos que cumplan los [math]a_i-es transladada a los [math]b_i-es es que [math]11 divida a [math]0\cdot b_0+b_1+2b_2+3b_3+\dots+120b_{120}. Pero estamos en una situación casi análoga a la anterior. Elegimos [math]11 de ellos y hacemos la misma operación de suma que permuta estos [math]11[math]b_i-es entre las primeras [math]11 posiciones y que cambia la suma de la expresión en [math]S módulo [math]11. De vuelta, si no terminamos es porque todos los [math]b_i-es tienen el mismo resto en la división por [math]11. Pero esto implicaría que todos los [math]a_i-es son congruentes módulo [math]121, pues [math]b_i\equiv b_j\pmod{11}\Rightarrow 11b_i\equiv 11b_j\pmod{121}\Rightarrow 11b_i+r\equiv 11b_j+r \pmod{121}\Rightarrow a_i\equiv a_j\pmod{121} para todos [math]i,j. Si este es el caso obtenemos que [math]a_1+2a_2+3a_3+\dots+120a_{120}\equiv a_1(1+2+3+\dots+120)=a_1\cdot 60\cdot 121\equiv 0\pmod{121} y cualquier permutación sirve. Esto cubre todos los casos, y hemos terminado.
Sea [math]x_i=i para un entero [math]i tal que [math]0\leq i\leq 121, sea [math]k_i la cantidad de veces que aparece el número [math]x_i.
Notemos que al cambiar un número [math]x_i por un número [math]x_i', la suma de la lista cambia en [math]x_i'-x_i. Entonces, al cambiar los [math]k_i números [math]x_i por [math]x_i', la suma de la lista cambiará en [math]k_i(x_i'-x_i).
Sea [math]S la suma de la lista, entonces [math]S\equiv n(121). Si [math]n\equiv 0(121), entonces la suma es divisible por [math]121 y no hay nada que hacer (como mucho cambiar un número cualquiera por [math]121, para hacer alguna operación).
Dividimos el problema en casos:
Caso [math]1: Existe algún [math]k_i coprimo con [math]11
Entonces [math]k_i es coprimo con [math]121 y por lo tanto es inversible [math]\pmod{121}.
Al cambiar los [math]k_i números [math]x_i por [math]x_i', queremos que [math]k_i(x_i'-x_i)\equiv -n(121), ya que de esta forma [math]S+k_i(x_i'-x_i)\equiv n-n\equiv 0(121)
Entonces [math]k_i(x_i'-x_i)\equiv -n(121)\Rightarrow x_i'-x_i\equiv -n\frac{1}{k_i}(121) ya que [math]k_i es inversible. Nos queda que [math]x_i'\equiv x_i-n\frac{1}{k_i}(121), como conocemos [math]x_i, [math]n y [math]k_i, podemos averiguar el valor de [math]x_i'. Como [math]x_i' puede ser cualquier número de la lista, y la lista contiene todos los restos posibles módulo [math]121, siempre podemos encontrar una solución para esta ecuación.
Caso [math]2:[math]k_i\equiv 0(11)\forall i
Entonces [math]S=11S', [math]k_i=11k_i' y [math]n=11n'. Por lo tanto, podemos dividir toda la ecuación por [math]11 y queda [math]S'\equiv n'(11). Si todos los [math]k_i' son múltiplos de [math]11, entonces [math]S'=11S''\Rightarrow S=121S''\Rightarrow S\equiv 0(121). Supongamos entonces que existe algún [math]k_i' coprimo con [math]11. Entonces lo que queremos es que [math]k_i'(x_i'-x_i)\equiv -n'(11), ya que de esta forma [math]S'+k_i'(x_i'-x_i)\equiv n'-n'\equiv 0(11), y por lo tanto la suma será múltiplo de [math]11, al multiplicarla nuevamente por [math]11, la suma será múltiplo de [math]121.
Como [math]k_i' es coprimo con [math]11, entonces es inversible [math]\pmod{11}.
Nos queda [math]k_i'(x_i'-x_i)\equiv -n'(11)\Rightarrow x_i'-x_i\equiv -n'\frac{1}{k_i'}(11), ya que [math]k_i' es inversible. Entonces [math]x_i'\equiv x_i-n'\frac{1}{k_i'}(11), como conocemos [math]x_i, [math]n' y [math]k_i', podemos averiguar el valor de [math]x_i'. Como [math]x_i' puede ser cualquier número de la lista, y la lista contiene todos los restos posibles módulo [math]11, siempre podemos encontrar una solución para esta ecuación.
Queda demostrado que siempre es posible lograr lo pedido.
