Nacional 2014 N3 P5

Problemas que aparecen en el Archivo de Enunciados.

Nacional 2014 N3 P5

UNREAD_POSTpor JPablo » Dom 16 Nov, 2014 12:32 am

Diremos que un entero $n\geq 3$ es especial si no divide a $\left ( n-1 \right )!\left ( 1+\frac{1}{2}+\cdot \cdot \cdot +\frac{1}{n-1} \right )$. Hallar todos los números especiales $n$ tales que $10\leq n\leq 100$.

ACLARACIÓN: Para cada entero positivo de $x$ se define el factorial de $x$ como $x!=1\cdot 2\cdot 3\cdot ...\cdot x$, es decir, la multiplicación de todos los enteros de $1$ a $x$.
Avatar de Usuario
JPablo
 
Mensajes: 347
Registrado: Lun 25 Mar, 2013 9:00 pm
Nivel: Exolímpico

Re: Nacional 2014 N3 P5

UNREAD_POSTpor 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

$\left ( n-1 \right )!\sum_{k=1}^{n-1}\frac{1}{k}=\sum_{k=1}^{n-1}\frac{\left ( n-1 \right )!}{k}$


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 $n$ es un número primo, entonces $n$ no es especial. Sea pues $n=p$ con $p$ primo, y demostremos primeramente que los $p-1$ términos de $\sum_{k=1}^{p-1}\frac{\left ( p-1 \right )!}{k}$ son una permutación de los enteros $1,2,3,\cdot \cdot \cdot ,p-1$ si miramos módulo $p$. Para eso, veámoslo por absurdo: sean $m$ y $u$ dos enteros positivos entre $1$ y $p-1$ tales que

$\frac{\left ( p-1 \right )!}{m}\equiv {\frac{\left ( p-1 \right )!}{u}}\pmod {p}$


$u\left ( p-1 \right )!\equiv {m\left ( p-1 \right )!}\pmod {p}$


Por el Teorema de Wilson nosotros sabemos que $p\mid {\left ( p-1 \right )!+1}$, por lo tanto la congruencia anterior es

$u\left ( -1 \right )\equiv {m\left ( -1 \right )}\pmod {p}$


$u\equiv {m}\pmod {p}$


Por lo tanto $p\mid {m-u}$ y esto implica que $m-u=0$ o bien $p\leq \left | m-u \right |$, pero siendo $m$ y $u$ naturales menores que $p$, esto último no puede ocurrir, por lo que la única posibilidad es $m-u=0\Longleftrightarrow m=u$. Esto demuestra que no hay dos términos congruentes módulo $p$. Como hay $p$ posibles restos módulo $p$ y tenemos $p-1$ términos, evidentemente hay exactamente un resto módulo $p$ que no figura en la permutación, que es claramente el $0$.

Habiendo demostrado la permutación, tenemos que

$\sum_{k=1}^{p-1}\frac{\left ( p-1 \right )!}{k}\equiv {\sum_{k=1}^{p-1}k}\pmod {p}$


$\sum_{k=1}^{p-1}\frac{\left ( p-1 \right )!}{k}\equiv {\frac{p\left ( p-1 \right )}{2}}\pmod {p}$


Siendo $p\geq 10$ por enunciado, se sigue que $p\equiv {1}\pmod {2}$ y por lo tanto $\frac{p-1}{2}\in {\mathbb{N}}$, luego

$\sum_{k=1}^{p-1}\frac{\left ( p-1 \right )!}{k}\equiv {p\frac{p-1}{2}}\pmod {p}$


$\sum_{k=1}^{p-1}\frac{\left ( p-1 \right )!}{k}\equiv {0}\pmod {p}$


Lo que demuestra que $p$ no es especial, y por lo tanto $n$ debe ser compuesto. Sean $d_1<d_2<\cdot \cdot \cdot <d_{\sigma \left ( n \right )}$ los divisores de $n$. Es claro que

$\sum_{k=1}^{n-1}\frac{\left ( n-1 \right )!}{k}\equiv {\sum_{k=2}^{\sigma \left ( n \right )-1}\frac{\left ( n-1 \right )!}{d_k}}\pmod {n}$


Si vemos casos chicos, notamos que los primeros que funcionan son $n=10$ y $n=14$, que son casualmente $2\times 5$ y $2\times 7$, y el $5$ y el $7$ son primos consecutivos. Esto nos permite conjeturar que todo $n=2p$ con $p$ primo es especial.

Sea $n=2p$ con $p$ primo. Entonces

$\sum_{k=1}^{2p-1}\frac{\left ( 2p-1 \right )!}{k}\equiv {\frac{\left ( 2p-1 \right )!}{p}}\pmod {2p}$


$\sum_{k=1}^{2p-1}\frac{\left ( 2p-1 \right )!}{k}\equiv {\frac{\left ( 2p-1 \right )!}{p}}\pmod {p}$


Puesto que todos los términos, salvo tal vez el que divide por $p$, son múltiplos de $2p$. El múltiplo positivo de $p$ más próximo a $p$ es $2p$, pero como $2p>2p-1$, éste no aparecerá en el factorial y por lo tanto

$\sum_{k=1}^{2p-1}\frac{\left ( 2p-1 \right )!}{k}\not\equiv {0}\pmod {p}$


$\sum_{k=1}^{2p-1}\frac{\left ( 2p-1 \right )!}{k}\not\equiv {0}\pmod {2p}$


Por lo tanto todo $n=2p$ es especial. Esto puede generalizarse: Supongamos que $n$ 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 $n$. Sea pues $p$ un primo que no divida a la suma. Si $p$ aparece con exponente unitario en la factorización en primos de $n$, entonces existe un entero $k$ coprimo con $p$ tal que $n=pk$. Si tuviéramos que $2p\leq pk-1$ entonces $p$ dividiría a la suma, por lo tanto debe ser

$2p>pk-1\Longleftrightarrow p\left ( k-2 \right )<1$


Como $k$ es natural mayor que $1$, entonces solamente puede ser $k=2$, luego $n=2p$.

Supongamos ahora el caso más general: $n$ es el producto de potencias de primos. La suma no puede ser divisible por todas las potencias. Sea pues $p^m$ una potencia que no divida a la suma. Existe entonces un natural $k$ coprimo con $p$ tal que $n=p^mk$.

Si tuviésemos que $2mp\leq p^{m}k-1$ entonces, como en módulo $p^m$ la relación es

$\sum_{i=1}^{n-1}\frac{\left ( n-1 \right )!}{i}\equiv {\sum_{i=1}^{m}\frac{\left ( n-1 \right )!}{p^{i}}}\pmod {p^{m}}$


es claro que $n$ no será especial, pues hay $2m$ o más múltiplos de $p$, el denominador $p^i$ sacará a lo sumo $m$ de ellos y nos quedarán al menos $m$, lo cual nos daría congruencia cero. Por lo tanto debe ser

$2mp> p^{m}k-1$

$p^{m}k-2mp< 1$

$p\left (p^{m-1}k-2m  \right )< 1$


Luego

$p^{m-1}k\leq 2m$


Pero $2^7>100$ por lo tanto $m\leq 6$, luego

$p^{m-1}k\leq 12$


Para $m\geq 5$ no hay solución, pues $p\geq 2$ y $2^4>12$.

Entonces $m\in \left \{ 1,2,3,4 \right \}$.

Si $m=1$ entonces $p(k-2)<1$ de donde $k\leq 2$. Tanto para $k=1$ como para $k=2$ ya hemos visto las soluciones.

Si $m=2$ tenemos $pk\leq 4$ de donde $p\leq 3$. Si $p=2$ entonces $k$ puede valer $1$ ó $2$, en cualquier caso obtenemos un $n<10$. Si $p=3$ entonces $k=1$ y $n=9$.

Si $m=3$ entonces $p^2 k\leq 6$ de donde $p=2$ y $k=1$ son los únicos que satisfacen, pero entonces $n=8$.

Si $m=4$ entonces $p^3 k\leq 8$ de donde $p=2$ y $k=1$, obtenemos entonces $n=16$.

Por lo tanto las únicas posibilidades son $n=2p$ con $p$ primo y $n=16$. La primera opción ya fue corroborada, solamente nos queda corroborar el $16$.

Si miramos la expresión en módulo $16$, usando lo deducido con los divisores de $16$ tenemos

$\sum_{k=1}^{16-1}\frac{\left ( 16-1 \right )!}{k}\equiv {\frac{\left ( 16-1 \right )!}{2}+\frac{\left ( 16-1 \right )!}{4}+\frac{\left ( 16-1 \right )!}{8}}\pmod {16}$


Del $1$ al $15$ 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 $16$ no es especial.

Entonces, un número $10\leq n\leq 100$ es especial si y sólo si es el doble de un primo. Así, las soluciones son:

$10,14,22,26,34,38,46,58,62,74,82,86,94$


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
JPablo
 
Mensajes: 347
Registrado: Lun 25 Mar, 2013 9:00 pm
Nivel: Exolímpico

Re: Nacional 2014 N3 P5

UNREAD_POSTpor AgustinChenna. » Dom 16 Nov, 2014 3:31 am

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

$(n-1)! \cdot (1 + \frac{1}{2} + ... + \frac{1}{n-1}) = (n-1)! \cdot [\frac {(n-1)! + \frac{(n-1)!}{2} + ... + \frac{(n-1)!}{n-1})}{(n-1)!} ]$

Lo cual finalmente expresaremos como:

$(n-1)! + \frac{(n-1)!}{2} + ... + \frac{(n-1)!}{n-1} = y$

Bueno, ahora basta encontrar cuales son los posibles $n$ para los cuales $y$ no sea múltiplo de $n$ y estamos.

Caso 1: Si $n$ es primo, entonces $(n-1)!$ no es multiplo de $n$. Pero al dividir ese factorial por todos los números desde $1$ hasta $(n-1)$ voy obteniendo todos los restos posibles de la división por $n$. Luego, al sumar todos esos sumandos con restos distintos en la división por $n$, los restos sumaran $\frac{(n-1) \cdot n}{2}$ por Gauss. Como $n$ es un primo distinto de $2$, entonces esto mismo lo puedo expresar como $\frac{n-1}{2} \cdot n$ lo cual claramente es multiplo de $n$. $n$ primo no sirve.

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

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

Los números son los mismos que puso JPablo arriba
Spoiler: Mostrar
Perdí

Spoiler: Mostrar


Spoiler: Mostrar
Imagen[/url]
Imagen
Imagen
Imagen
Avatar de Usuario
AgustinChenna.
 
Mensajes: 186
Registrado: Mié 03 Ago, 2011 9:23 pm
Nivel: Ñandú

Re: Nacional 2014 N3 P5

UNREAD_POSTpor LuchoLP » Dom 16 Nov, 2014 1:43 pm

Forma rápida de ver que los primos no funcionan
Spoiler: Mostrar

A Matigelp97 le gusta este mensaje.

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

Re: Nacional 2014 N3 P5

UNREAD_POSTpor Fran5 » Lun 17 Nov, 2014 1:19 am

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

La idea es usar $v_p(n)$ que es "el mayor exponente con el cual $p$ divide a $n$

Podemos reescribir la expresión del enunciado como $( n-1)!\sum_{k=1}^{n-1}\frac{1}{k}=\sum_{k=1}^{n-1}\frac{( n-1 )!}{k}$

Sea $N=p_1^{\alpha_1}p_2^{\alpha_2}...p_k^{\alpha_k}$ la factorización en primos de $N$

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 $N$ tantas bolitas de cada color como indiquen los exponentes de los primos que le dividen

Nuestro objetivo es ver que si $n=2p$ nos faltan bolitas, y en caso contrario, nos sobran

Entonces, en $\sum_{k=1}^{n-1}\frac{( n-1 )!}{k}$ tenemos que quitar, para cada término, bolitas de colores :D

Tomemos un primo impar cualquiera. Supongamos que tiene exponente $k \geq 1$

Entonces, ese primo aparece dividiendo en $\frac{n}{p}-1$ términos (desde $\frac{( n-1 )!}{p}$ hasta $\frac{( n-1 )!}{n-p}$) y en cada término quitamos tantas bolitas como indique el exponente del divisor. (en particular, hay $v_p(q)$ bolitas de color $p$ asociadas al número $q$)

Originalmente, habría al menos $\frac{n}{p}-1$ bolitas de ese color (una por cada múltiplo). Y en cada paso quitamos al menos una.

Si $\frac{n}{p}=1$, usamos directamene teorema de wolstenholme

Si $\frac{n}{p}=2$, observamos que teníamos inicialmente una sóla bolita, pero la quitamos en el término $\frac{(n-1)!}{p}$.

Si $\frac{n}{p}>2$, 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 $k>1$ bolitas, resulta que hay al menos $\sum_{i=1}^{n-1} v_p(i) \geq k+(k-1)+...+2+1=\frac{k(k+1)}{2} >2k$ bolillas en cada término, por tanto, siempre nos van a quedar al menos $k$ bolitas, que es el exponente con el cual $p$ divide a $n$

Para $p=2$, si $n \geq 10$ se tiene que $v_2((n-1)!) \geq v_2(n)+3+1+2+1>v_2(n)+v_2(64)$.
De modo que 2 siempre divide

En conclusión, los numeros especiales son los de la forma $n=2p$
"Al toque Roque // Al pique Quique // Tranca palanca // No pasa nada // Argentina Gana // La tenés adentro // Costa Rica te entro"
Avatar de Usuario
Fran5
 
Mensajes: 789
Registrado: Mié 21 Mar, 2012 1:57 pm
Ubicación: Santa Fe
Medals: 4
OFO - Medalla de Oro OFO - Jurado OFO - Jurado FOFO Pascua 2017 - Jurado
Nivel: Exolímpico

Re: Nacional 2014 N3 P5

UNREAD_POSTpor Gianni De Rico » Dom 16 Jul, 2017 6:52 pm

Spoiler: Mostrar
Vemos que como todas las fracciones son de la forma $\frac 1m$, con $m\leq n-1$ y $m\in \mathbb N$, 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 $p$ a los números primos):

Caso $1$: $n=p$
Spoiler: Mostrar
Sean $a$ y $b$ naturales coprimos tales que $\frac ab=1+\frac 12+\frac 13+\ldots +\frac{1}{p-1}$, por el Teorema de Wolstenholme, $p$ divide a $a$ pero no a $b$. Reescribimos la ecuación original como $(p-1)!\frac ab=(p-1)!(1+\frac 12+\frac 13+\ldots +\frac{1}{p-1})$, entonces, $(p-1)!\frac ab$ es natural, como $p|a$, se tiene que $p|(p-1)!\frac ab$, por lo tanto, $n=p$ no es especial.

Caso $2$: $n=2p$
Spoiler: Mostrar
Tenemos $p<n-1<2p$ por lo tanto $p$ aparece sólo una vez en $(n-1)!$, entonces, $\frac{(n-1)!}{p}$ no será múltiplo de $n$, mientras que el resto sí, ya que el $2$ aparece al menos $p$ veces en $(n-1)!$, por lo tanto, la suma de todas las fracciones excepto $\frac{(n-1)!}{p}$ será múltiplo de $n$, pero al sumar un número múltiplo de $n$ con un número no múltiplo de $n$, obtenemos un número que no es múltiplo de $n$, por lo tanto, si $n=2p$, entonces $n$ es especial.

Caso $3$: $n=2^x$
Spoiler: Mostrar
Entonces todas las fracciones son múltiplos de $n$, ya que no importa por cuál potencia de $2$ dividamos a $(n-1)!$, siempre sobran suficientes factores $2$ entre el resto de las potencias para llegar a $2^x$, dado que la cantidad de factores $2$ que habrá entre todas las potencias será $\frac{(x-1)x}{2}>x$, ya que $n\geq 10\Rightarrow x\geq 4\Rightarrow x-1\geq 3\Rightarrow x-1>2\Rightarrow (x-1)x>2x\Rightarrow \frac{(x-1)x}{2}>x$. Entonces todas las fracciones son múltiplos de $n$, por lo tanto, $n=2^x$ no es especial.

Caso $4$: $n=kp$, con $k>2$
Spoiler: Mostrar
Notemos que $p>2$, ya que de no ser así, podemos intercambiar a $p$ con el mayor factor primo de $k$. Entonces $p|(n-1)!$, como $k$ (y todos sus divisores) aparecen al menos $p-1$ veces en la factorización de $(n-1)!$, entonces no importa si cancelamos uno de los factores, siempre tendremos al menos $1$ más en $(n-1)!$, por lo tanto, todas las fracciones serán múltiplos de $k$ (1). De forma análoga, $p$ aparece al menos $k-1$ veces en la factorización de $(n-1)!$ (puede aparecer más si $k$ es múltiplo de $p$), entonces no importa si cancelamos a $p$, siempre tendremos al menos $1$ factor $p$ más en $(n-1)!$, por lo tanto, todas las fracciones serán múltiplos de $p$ (2).

De (1) y (2) sale que todas las fracciones serán múltiplos de $p$ y de $k$, por lo tanto, todas las fracciones serán múltiplos de $kp$, de dónde $n=kp$ no es especial.


Por lo tanto $n$ es especial si y sólo si $n=2p$, como $10\leq n\leq 100$, los únicos números especiales son:

$\{10;14;22;26;34;38;46;58;62;74;82;86;94\}$
$e^{i\pi}+1=0$
Avatar de Usuario
Gianni De Rico
 
Mensajes: 346
Registrado: Vie 16 Sep, 2016 6:58 pm
Ubicación: Rosario
Nivel: 3


Volver a Problemas Archivados

¿Quién está conectado?

Usuarios navegando por este Foro: No hay usuarios registrados visitando el Foro y 1 invitado