Nacional 2012 P5 N3

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Vladislao

Colaborador OFO - Jurado FOFO 6 años - Jurado FOFO Pascua 2017 - Jurado
Mensajes: 788
Registrado: Mar 28 Dic, 2010 3:26 pm
Medallas: 6
Nivel: Exolímpico
Ubicación: Córdoba

Nacional 2012 P5 N3

Mensaje sin leer por Vladislao » Sab 10 Nov, 2012 3:39 pm

Dada una secuencia finita con términos en el conjunto [math], está permitido reemplazar cada término por un número del conjunto [math] 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 [math]. 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] Para todo entero positivo [math] se cumple que [math] es un número primo.

Avatar de Usuario
Vladislao

Colaborador OFO - Jurado FOFO 6 años - Jurado FOFO Pascua 2017 - Jurado
Mensajes: 788
Registrado: Mar 28 Dic, 2010 3:26 pm
Medallas: 6
Nivel: Exolímpico
Ubicación: Córdoba

Re: Nacional 2012 P5 N3

Mensaje sin leer por Vladislao » Sab 10 Nov, 2012 4:33 pm

Vamos a reformular el enunciado de modo que se pueda entender lo que hacemos:
Spoiler: mostrar
Sea [math]. Consideremos dos subconjuntos arbitrarios de [math], definidos como sigue: [math] y [math] (ambos con la misma cantidad de elementos). Consideremos una función biyectiva [math] de [math] en [math], tal que [math]. Demostrar que, dada una secuencia [math] de números del conjunto [math] (no necesariamente distintos), se puede realizar una elección conveniente de los conjuntos [math] e [math] de tal manera que la secuencia [math] es tal que la suma de sus términos es múltiplo de [math]. Nota: [math] si [math] no está en el conjunto [math] elegido.
Solución:
Spoiler: mostrar
Consideremos nuestra secuencia [math]. Para cada [math] sea [math] la cantidad de veces que está el número [math] en la secuencia. Consideremos el número: [math]. Es claro que [math] es la suma de los términos de la secuencia inicial. Supongamos que: [math] donde [math].

Separemos el problema en dos casos:

Caso 1) Existe algún [math] coprimo con 11.

Sea [math] coprimo con 11. Entonces [math] es coprimo con [math], y por lo tanto existe [math] tal que [math].

Supongamos que [math], entonces, como [math] es invertible existe algún [math] tal que [math].

Si cambiamos todos los números [math] de nuestra secuencia inicial, por los números [math], obtenemos una nueva suma:

[math].

Es claro que [math].

Por lo tanto, la nueva suma es divisible por 121.

Caso 2) Todos los [math] son múltiplos de 11.

Sea [math] para todo [math].

La suma [math] se puede escribir [math].

Si todos los [math] fueran múltiplos de [math] no hay nada que hacer, puedes cada [math] sería múltiplo de [math], y por ende, la suma [math] sería múltiplo de [math]. Vamos a suponer, entonces, que hay algún [math] coprimo con [math]. Entonces, consideramos [math], entonces, [math], donde [math] (aquí, vendría a ser [math]). Como [math] es coprimo con 11, es invertible, y por ende, se puede cambiar [math] por [math] de tal manera que: [math]. Lo que equivale a: [math], es decir: [math].

Si cambiamos [math] por [math], la suma [math] cambia por [math].

Luego, la nueva suma es múltiplo de 121 como queríamos.
Sea [math] Para todo entero positivo [math] se cumple que [math] es un número primo.

Avatar de Usuario
Prillo

Colaborador OFO - Jurado
Mensajes: 396
Registrado: Sab 18 Dic, 2010 8:52 pm
Medallas: 2

Re: Nacional 2012 P5 N3

Mensaje sin leer por Prillo » Sab 10 Nov, 2012 6:47 pm

Spoiler: mostrar
Sea [math] la cantidad de veces que aparece el término [math] en la sucesión. La suma inicial es [math]. Bastará hallar una permutación [math] de [math] tal que [math] divida a [math].

Tomemos [math] números arbitrarios de entre nuestros [math]-es para que empiecen siendo [math], y nos olvidamos del último [math], que es [math]. Sea [math] la suma de los [math] elegidos; [math]. Notemos que sumar [math] a la expresión [math] módulo [math] mueve los [math]-es un lugar a la derecha (en su defecto [math] que está en la última posición de la derecha se va al extremo izquierdo a ser multiplicado por el [math]). Así, sumar [math] permuta los [math]-es en la expresión que nos interesa, y si hacemos esto [math] veces la suma habrá variado en [math]. Supongamos que [math] no es divisible por [math]. Entonces [math] es coprima con [math] y tras sumas una cantidad conveniente de veces [math] obtenemos una permutación de los [math]-es para la cual la expresión que nos interesa es múltiplo de [math], y hemos terminado. Entonces queda el caso en que [math] sea múltiplo de [math]. Pero recordemos que nuestros [math] [math]-es los elegimos en forma arbitraria. Entonces, lo peor que nos puede pasar es que no importa cuáles [math] números elijamos (ó lo que es lo mismo, cuál de los [math] dejemos afuera), su suma sea múltiplo de [math]. Esto es obviamente posible sólo si todos los [math]-es tienen igual resto en la división por [math]. En tal caso escribamos [math], donde [math] es el resto común. Tras desarrollar y simplificar la condición que queremos que cumplan los [math]-es transladada a los [math]-es es que [math] divida a [math]. Pero estamos en una situación casi análoga a la anterior. Elegimos [math] de ellos y hacemos la misma operación de suma que permuta estos [math] [math]-es entre las primeras [math] posiciones y que cambia la suma de la expresión en [math] módulo [math]. De vuelta, si no terminamos es porque todos los [math]-es tienen el mismo resto en la división por [math]. Pero esto implicaría que todos los [math]-es son congruentes módulo [math], pues [math] para todos [math]. Si este es el caso obtenemos que [math] y cualquier permutación sirve. Esto cubre todos los casos, y hemos terminado.
1  

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial
Mensajes: 829
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 1
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Nacional 2012 P5 N3

Mensaje sin leer por Gianni De Rico » Vie 03 Nov, 2017 8:25 pm

Spoiler: mostrar
Sea [math] para un entero [math] tal que [math], sea [math] la cantidad de veces que aparece el número [math].

Notemos que al cambiar un número [math] por un número [math], la suma de la lista cambia en [math]. Entonces, al cambiar los [math] números [math] por [math], la suma de la lista cambiará en [math].

Sea [math] la suma de la lista, entonces [math]. Si [math], entonces la suma es divisible por [math] y no hay nada que hacer (como mucho cambiar un número cualquiera por [math], para hacer alguna operación).


Dividimos el problema en casos:

Caso [math]: Existe algún [math] coprimo con [math]
Entonces [math] es coprimo con [math] y por lo tanto es inversible [math].
Al cambiar los [math] números [math] por [math], queremos que [math], ya que de esta forma [math]
Entonces [math] ya que [math] es inversible. Nos queda que [math], como conocemos [math], [math] y [math], podemos averiguar el valor de [math]. Como [math] puede ser cualquier número de la lista, y la lista contiene todos los restos posibles módulo [math], siempre podemos encontrar una solución para esta ecuación.

Caso [math]: [math]
Entonces [math], [math] y [math]. Por lo tanto, podemos dividir toda la ecuación por [math] y queda [math]. Si todos los [math] son múltiplos de [math], entonces [math]. Supongamos entonces que existe algún [math] coprimo con [math]. Entonces lo que queremos es que [math], ya que de esta forma [math], y por lo tanto la suma será múltiplo de [math], al multiplicarla nuevamente por [math], la suma será múltiplo de [math].
Como [math] es coprimo con [math], entonces es inversible [math].
Nos queda [math], ya que [math] es inversible. Entonces [math], como conocemos [math], [math] y [math], podemos averiguar el valor de [math]. Como [math] puede ser cualquier número de la lista, y la lista contiene todos los restos posibles módulo [math], siempre podemos encontrar una solución para esta ecuación.


Queda demostrado que siempre es posible lograr lo pedido.
[math]

Responder