Nacional 2014 N3 P5

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
JPablo
Mensajes: 351
Registrado: Lun 25 Mar, 2013 9:00 pm
Nivel: Exolímpico

Nacional 2014 N3 P5

Mensaje sin leer por JPablo » Dom 16 Nov, 2014 12:32 am

Diremos que un entero [math] es especial si no divide a [math]. Hallar todos los números especiales [math] tales que [math].

ACLARACIÓN: Para cada entero positivo de [math] se define el factorial de [math] como [math], es decir, la multiplicación de todos los enteros de [math] a [math].

Avatar de Usuario
JPablo
Mensajes: 351
Registrado: Lun 25 Mar, 2013 9:00 pm
Nivel: Exolímpico

Re: Nacional 2014 N3 P5

Mensaje sin leer por JPablo » Dom 16 Nov, 2014 12:44 am

Este fue el problema que más me gustó del Nivel 3 jeje. Lo pasé a explicar en la puesta en común :D, verdaderamente maravilloso.
Spoiler: mostrar
Reescribimos la expresión del enunciado como
[math]
Notemos que cada término de la sumatoria es natural, pues cada uno de los denominadores es un natural menor o igual al factorial del numerador, por lo que se simplificará.

Empezaremos por demostrar que si [math] es un número primo, entonces [math] no es especial. Sea pues [math] con [math] primo, y demostremos primeramente que los [math] términos de [math] son una permutación de los enteros [math] si miramos módulo [math]. Para eso, veámoslo por absurdo: sean [math] y [math] dos enteros positivos entre [math] y [math] tales que
[math]
[math]
Por el Teorema de Wilson nosotros sabemos que [math], por lo tanto la congruencia anterior es
[math]
[math]
Por lo tanto [math] y esto implica que [math] o bien [math], pero siendo [math] y [math] naturales menores que [math], esto último no puede ocurrir, por lo que la única posibilidad es [math]. Esto demuestra que no hay dos términos congruentes módulo [math]. Como hay [math] posibles restos módulo [math] y tenemos [math] términos, evidentemente hay exactamente un resto módulo [math] que no figura en la permutación, que es claramente el [math].

Habiendo demostrado la permutación, tenemos que
[math]
[math]
Siendo [math] por enunciado, se sigue que [math] y por lo tanto [math], luego
[math]
[math]
Lo que demuestra que [math] no es especial, y por lo tanto [math] debe ser compuesto. Sean [math] los divisores de [math]. Es claro que
[math]
Si vemos casos chicos, notamos que los primeros que funcionan son [math] y [math], que son casualmente [math] y [math], y el [math] y el [math] son primos consecutivos. Esto nos permite conjeturar que todo [math] con [math] primo es especial.

Sea [math] con [math] primo. Entonces
[math]
[math]
Puesto que todos los términos, salvo tal vez el que divide por [math], son múltiplos de [math]. El múltiplo positivo de [math] más próximo a [math] es [math], pero como [math], éste no aparecerá en el factorial y por lo tanto
[math]
[math]
Por lo tanto todo [math] es especial. Esto puede generalizarse: Supongamos que [math] es el producto de varios primos que aparecen con exponente unitario en la factorización. La suma del enunciado no puede ser divisible por todos ellos pues de lo contrario sería divisible por [math]. Sea pues [math] un primo que no divida a la suma. Si [math] aparece con exponente unitario en la factorización en primos de [math], entonces existe un entero [math] coprimo con [math] tal que [math]. Si tuviéramos que [math] entonces [math] dividiría a la suma, por lo tanto debe ser
[math]
Como [math] es natural mayor que [math], entonces solamente puede ser [math], luego [math].

Supongamos ahora el caso más general: [math] es el producto de potencias de primos. La suma no puede ser divisible por todas las potencias. Sea pues [math] una potencia que no divida a la suma. Existe entonces un natural [math] coprimo con [math] tal que [math].

Si tuviésemos que [math] entonces, como en módulo [math] la relación es
[math]
es claro que [math] no será especial, pues hay [math] o más múltiplos de [math], el denominador [math] sacará a lo sumo [math] de ellos y nos quedarán al menos [math], lo cual nos daría congruencia cero. Por lo tanto debe ser
[math]

[math]

[math]
Luego
[math]
Pero [math] por lo tanto [math], luego
[math]
Para [math] no hay solución, pues [math] y [math].

Entonces [math].

Si [math] entonces [math] de donde [math]. Tanto para [math] como para [math] ya hemos visto las soluciones.

Si [math] tenemos [math] de donde [math]. Si [math] entonces [math] puede valer [math] ó [math], en cualquier caso obtenemos un [math]. Si [math] entonces [math] y [math].

Si [math] entonces [math] de donde [math] y [math] son los únicos que satisfacen, pero entonces [math].

Si [math] entonces [math] de donde [math] y [math], obtenemos entonces [math].

Por lo tanto las únicas posibilidades son [math] con [math] primo y [math]. La primera opción ya fue corroborada, solamente nos queda corroborar el [math].

Si miramos la expresión en módulo [math], usando lo deducido con los divisores de [math] tenemos
[math]
Del [math] al [math] hay siete números pares. Cada una de las sumas quita solamente uno, por lo tanto nos quedarán seis y de esta forma el [math] no es especial.

Entonces, un número [math] es especial si y sólo si es el doble de un primo. Así, las soluciones son:

[math]
PD: A ver quién se copa y postea la solución del chico que tuvo podio y lo explicó frente a todos, que fue una solución espectacular :lol:
Última edición por JPablo el Sab 28 Feb, 2015 9:02 pm, editado 1 vez en total.

Avatar de Usuario
AgustinChenna.
Mensajes: 186
Registrado: Mié 03 Ago, 2011 9:23 pm
Nivel: Ñandú

Re: Nacional 2014 N3 P5

Mensaje sin leer por AgustinChenna. » Dom 16 Nov, 2014 3:31 am

Spoiler: mostrar
Arrancamos trabajando un poco la ecuación inicial. Tengo que:

[math]

Lo cual finalmente expresaremos como:

[math]

Bueno, ahora basta encontrar cuales son los posibles [math] para los cuales [math] no sea múltiplo de [math] y estamos.

Caso 1: Si [math] es primo, entonces [math] no es multiplo de [math]. Pero al dividir ese factorial por todos los números desde [math] hasta [math] voy obteniendo todos los restos posibles de la división por [math]. Luego, al sumar todos esos sumandos con restos distintos en la división por [math], los restos sumaran [math] por Gauss. Como [math] es un primo distinto de [math], entonces esto mismo lo puedo expresar como [math] lo cual claramente es multiplo de [math]. [math] primo no sirve.

Caso 2: Si [math] es una potencia (voy a ejemplificar con que [math] pero en realidad se ve facil que sirve para toda potencia), en este caso un cuadrado perfecto, entonces tiene un solo divisor ademas de [math] y [math]. Pero como [math] es al menos [math], entonces en la sucesión de numeros [math] habrá por lo menos [math] números de la forma [math]. Por lo tanto, todos los sumandos serán multiplos de [math], ya que cuando tenga [math], dentro de ese numero habra otros dos numeros de la forma [math] multiplicando y por tanto sera multiplo de [math] y lo mismo para todos los casos en los que se divida al factorial por un multiplo de [math]. Por lo tanto, [math] no es una potencia.

Caso 3: Supongamos que [math] tiene dos divisores solamente distintos de [math] y [math] (sean [math] y [math] con [math]). Si [math], entonces en la sucesion [math] habrá por lo menos dos números de la forma [math] y dos de la forma [math] (en realidad habría mas de [math], pero no importa). Por lo tanto, [math] no solo es multiplo de [math], como ocurriría con todos los compuestos, si no que ademas todos los sumandos de [math] también seran multiplos de [math]. Si vemos con detenimiento, en el momento que haga [math] seguirá habiendo otro numero de la forma [math] multiplicando dentro del factorial y habrá otro numero de la forma [math]. Lo mismo con [math]; tendré dentro del factorial un numero [math] y otro [math]. Por lo tanto, si todos los sumandos de [math] son multiplos de [math], entonces [math] divide a [math] y por lo tanto todos los numeros [math] con mas de dos divisores no sirven, como tampoco sirven los que tienen dos divisores mayor a [math]. Por lo tanto, solo funcionan los [math] de la forma [math] con [math] primo.

Los números son los mismos que puso JPablo arriba

LuchoLP

OFO - Medalla de Bronce OFO - Medalla de Plata
Mensajes: 182
Registrado: Mié 17 Abr, 2013 7:27 pm
Medallas: 3
Nivel: Exolímpico

Re: Nacional 2014 N3 P5

Mensaje sin leer por LuchoLP » Dom 16 Nov, 2014 1:43 pm

Forma rápida de ver que los primos no funcionan
Spoiler: mostrar
Wolstenholme http://omaforos.com.ar/viewtopic.php?f=11&t=345
1  

Avatar de Usuario
Fran5

OFO - Medalla de Oro OFO - Jurado FOFO Pascua 2017 - Jurado
Mensajes: 797
Registrado: Mié 21 Mar, 2012 1:57 pm
Medallas: 4
Nivel: Exolímpico
Ubicación: Santa Fe

Re: Nacional 2014 N3 P5

Mensaje sin leer por Fran5 » Lun 17 Nov, 2014 1:19 am

Spoiler: mostrar
La idea me la tiró Zylber y ahora la adapto

La idea es usar [math] que es "el mayor exponente con el cual [math] divide a [math]

Podemos reescribir la expresión del enunciado como [math]

Sea [math] la factorización en primos de [math]

Supongamos que tenemos bolitas de varios colores, y en cantidades suficientes.

A cada primo le asignamos un color, y luego le asociamos a cada entero [math] tantas bolitas de cada color como indiquen los exponentes de los primos que le dividen

Nuestro objetivo es ver que si [math] nos faltan bolitas, y en caso contrario, nos sobran

Entonces, en [math] tenemos que quitar, para cada término, bolitas de colores :D

Tomemos un primo impar cualquiera. Supongamos que tiene exponente [math]

Entonces, ese primo aparece dividiendo en [math] términos (desde [math] hasta [math]) y en cada término quitamos tantas bolitas como indique el exponente del divisor. (en particular, hay [math] bolitas de color [math] asociadas al número [math])

Originalmente, habría al menos [math] bolitas de ese color (una por cada múltiplo). Y en cada paso quitamos al menos una.

Si [math], usamos directamene teorema de wolstenholme

Si [math], observamos que teníamos inicialmente una sóla bolita, pero la quitamos en el término [math].

Si [math], tenemos al menos dos bolitas en cada término, y quitamos sólo de a una.
Si en algún término quitamos a lo sumo [math] bolitas, resulta que hay al menos [math] bolillas en cada término, por tanto, siempre nos van a quedar al menos [math] bolitas, que es el exponente con el cual [math] divide a [math]

Para [math], si [math] se tiene que [math].
De modo que 2 siempre divide

En conclusión, los numeros especiales son los de la forma [math]
"Al toque Roque // Al pique Quique // Tranca palanca // No pasa nada // Argentina Gana // La tenés adentro // Costa Rica te entro"

Avatar de Usuario
Gianni De Rico

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

Re: Nacional 2014 N3 P5

Mensaje sin leer por Gianni De Rico » Dom 16 Jul, 2017 6:52 pm

Spoiler: mostrar
Vemos que como todas las fracciones son de la forma [math], con [math] y [math], al hacer distributiva, todos los sumados serán naturales, y por lo tanto el resultado también lo será.

Dividimos el problema en casos (a partir de ahora, llamo [math] a los números primos):

Caso [math]: [math]
Spoiler: mostrar
Sean [math] y [math] naturales coprimos tales que [math], por el Teorema de Wolstenholme, [math] divide a [math] pero no a [math]. Reescribimos la ecuación original como [math], entonces, [math] es natural, como [math], se tiene que [math], por lo tanto, [math] no es especial.
Caso [math]: [math]
Spoiler: mostrar
Tenemos [math] por lo tanto [math] aparece sólo una vez en [math], entonces, [math] no será múltiplo de [math], mientras que el resto sí, ya que el [math] aparece al menos [math] veces en [math], por lo tanto, la suma de todas las fracciones excepto [math] será múltiplo de [math], pero al sumar un número múltiplo de [math] con un número no múltiplo de [math], obtenemos un número que no es múltiplo de [math], por lo tanto, si [math], entonces [math] es especial.
Caso [math]: [math]
Spoiler: mostrar
Entonces todas las fracciones son múltiplos de [math], ya que no importa por cuál potencia de [math] dividamos a [math], siempre sobran suficientes factores [math] entre el resto de las potencias para llegar a [math], dado que la cantidad de factores [math] que habrá entre todas las potencias será [math], ya que [math]. Entonces todas las fracciones son múltiplos de [math], por lo tanto, [math] no es especial.
Caso [math]: [math], con [math]
Spoiler: mostrar
Notemos que [math], ya que de no ser así, podemos intercambiar a [math] con el mayor factor primo de [math]. Entonces [math], como [math] (y todos sus divisores) aparecen al menos [math] veces en la factorización de [math], entonces no importa si cancelamos uno de los factores, siempre tendremos al menos [math] más en [math], por lo tanto, todas las fracciones serán múltiplos de [math] (1). De forma análoga, [math] aparece al menos [math] veces en la factorización de [math] (puede aparecer más si [math] es múltiplo de [math]), entonces no importa si cancelamos a [math], siempre tendremos al menos [math] factor [math] más en [math], por lo tanto, todas las fracciones serán múltiplos de [math] (2).

De (1) y (2) sale que todas las fracciones serán múltiplos de [math] y de [math], por lo tanto, todas las fracciones serán múltiplos de [math], de dónde [math] no es especial.
Por lo tanto [math] es especial si y sólo si [math], como [math], los únicos números especiales son:
[math]
[math]

Responder