Rioplatense 2015 - N3 P5

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

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

Rioplatense 2015 - N3 P5

Mensaje sin leer por Prillo » Dom 13 Dic, 2015 11:16 am

Para un número entero positivo [math] denotamos [math] al máximo común divisor de los coeficientes binomiales [math].
Hallar todos los valores posibles de [math].

Avatar de Usuario
3,14

OFO - Medalla de Plata-OFO 2015 OFO - Medalla de Plata-OFO 2016 FOFO 6 años - Medalla Especial-FOFO 6 años OFO - Medalla de Oro-OFO 2017 OFO - Medalla de Plata-OFO 2018
Mensajes: 449
Registrado: Jue 11 Oct, 2012 5:20 pm
Medallas: 5
Nivel: Exolímpico

Re: Rioplatense 2015 - N3 P5

Mensaje sin leer por 3,14 » Lun 14 Dic, 2015 9:37 am

Spoiler: mostrar
Afirmo que [math] es igual a [math] o a un número primo.
Dividamos el problema en tres casos:

A) [math]
En ese caso, los valores de cada coeficiente binomial son:
[math]
[math]
[math]
[math]
Observemos que el primer término vale [math], por lo que [math] es a lo sumo [math]. Por otro lado, veamos que [math] divide a todos los términos. Esto ocurre porque aparece en todos los numeradores, pero en ninguna de las fracciones se simplifica porque los términos de los denominadores son siempre a lo sumo [math], por lo que ninguno divide a [math]. Entonces [math] para todo primo [math].

B)[math] Con [math]
Vamos a demostrar que en este caso, [math]. Tomemos uno de los primos de la factorización de [math], digamos [math]. Demostraremos entonces que existe un término tal que [math] no lo divide. De esta forma, aplicando el mismo razonamiento para todos los primos de la factorización, se puede concluir que ninguno de ellos puede aparecer en [math], pero como [math] (porque el primer término vale [math]) entonces [math], entonces [math]. Veamos que el término que estamos buscando es:
[math]
Observemos que tanto en el numerador como en el denominador, todos los números son consecutivos, y hay [math] números, que por lo tanto forman un sistema completo de restos módulo [math].
Veamos que los restos son:
Numerador: [math]
Denominador: [math]
Observemos que podemos emparejar los restos (el último número de la derecha en el numerador con el primero del denominador; el anteúltimo con el último, y así sucesivamente). También observemos que ninguno de los números es divisible por [math], porque el único que es múltiplo de [math] es [math], pero claramente, por la factorización original de [math], [math].
Entonces, al poder emparejar todos los restos del numerador y el denominador, significa que la candidad de factores [math] en el numerador y en el denominador es la misma, y por lo tanto, se simplifican, y finalmente queda que [math] no divide al término.
Por ello, [math].

C) [math]
No voy a poner la demostración, pero se puede ver que [math] (en realidad no es necesario: basta con demostrar que existe un término no divisible por [math], por lo que o bien [math] o [math], pero en ninguno de los dos casos [math] es compuesto). El término es [math].
Es interesante observar que en este caso el argumento de B) no es aplicable porque [math], por lo que el término que usamos en [math], en [math] no aparece en la sucesión.
Última edición por 3,14 el Lun 14 Dic, 2015 2:53 pm, editado 1 vez en total.
[math]

Avatar de Usuario
3,14

OFO - Medalla de Plata-OFO 2015 OFO - Medalla de Plata-OFO 2016 FOFO 6 años - Medalla Especial-FOFO 6 años OFO - Medalla de Oro-OFO 2017 OFO - Medalla de Plata-OFO 2018
Mensajes: 449
Registrado: Jue 11 Oct, 2012 5:20 pm
Medallas: 5
Nivel: Exolímpico

Re: Rioplatense 2015 - N3 P5

Mensaje sin leer por 3,14 » Lun 14 Dic, 2015 9:41 am

Ahora que me fijo bien, [math] es un caso particular de [math] ...
[math]

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Oro-OFO 2019 COFFEE - Jurado-COFFEE Matías Saucedo OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020
COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber
Mensajes: 1303
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 7
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Rioplatense 2015 - N3 P5

Mensaje sin leer por Gianni De Rico » Dom 08 Dic, 2019 7:39 pm

Solución:
Spoiler: mostrar
Sean $m\in \mathbb{N}_n$ y $k\in \mathbb{N}$. Para cada primo $p$, tenemos que $$\nu _p\left (\binom{m+n}{n}\right )=\nu _p\left ((m+n)!\right )-\nu _p\left (m!\right )-\nu _p\left (n!\right )$$
Sea $n\neq q^k-1$, con $q$ primo. Veamos que para cada primo $p$, existe $m$ tal que $\nu _p\left (\binom{m+n}{n}\right )=0$, es decir, tal que $$\nu _p\left (n!\right )+\nu _p\left (m!\right )=\nu _p\left ((m+n)!\right )$$
Por la Fórmula de Legendre, tenemos que $\nu _p\left (a!\right )=\frac{a-s_p(a)}{p-1}$ para todo $a$ natural, donde $s_p(a)$ es la suma de los dígitos de $a$ en base $p$, luego, queremos ver
$$\begin{align*}
\nu _p\left (n!\right )+\nu _p\left (m!\right )=\nu _p\left ((m+n)!\right ) & \iff \frac{n-s_p(n)}{p-1}+\frac{m-s_p(m)}{p-1}=\frac{n+m-s_p(n+m)}{p-1} \\
& \iff n+m-s_p(n)-s_p(m)=n+m-s_p(n+m) \\
& \iff s_p(n)+s_p(m)=s_p(n+m) \\
\end{align*}$$
Sea $n=\overline{b_rb_{r-1}\ldots b_1b_0}_p=\sum \limits _{i=0}^rb_ip^i$, con $b_r\neq 0$ y $0\leqslant b_i\leqslant p-1$ para todo $0\leqslant i\leqslant r$, la descomposición de $n$ en base $p$, veamos que existe $0\leqslant c\leqslant r$ tal que $b_c\neq p-1$.
En efecto, supongamos lo contrario, luego, $b_i=p-1$ para todo $i$, por lo que $$n=\sum \limits _{i=0}^rb_ip^i=\sum \limits _{i=0}^r(p-1)p^i=(p-1)\sum \limits _{i=0}^rp^i=(p-1)\frac{p^{r+1}-1}{p-1}=p^{r+1}-1$$ entonces tomando $q=p$ y $k=r+1$ tenemos que $n=q^k-1$, con $q$ primo. Absurdo pues $n\neq q^k-1$, con $q$ primo. Luego, dicho $c$ existe, y tomando $m=p^c\leqslant p^r\leqslant n$, tenemos que $n+m=\overline{b_rb_{r-1}\ldots b_{c+1}(b_c+1)b_{c-1}\ldots b_1b_0}_p$, por lo que
$$\begin{align*}
s_p(n)+s_p(m) & =b_r+b_{r-1}+\cdots +b_{c+1}+b_c+b_{c-1}+\cdots +b_1+b_0+1 \\
& =b_r+b_{r-1}+\cdots +b_{c+1}+(b_c+1)+b_{c-1}+\cdots +b_1+b_0 \\
& =s_p(n+m) \\
\end{align*}$$
Luego, $$\nu _p\left (d(n)\right)=\text{min}\left \{\nu _p\left (\binom{n+m}{n}\right ):m\in \mathbb{N}_n\right \}\leqslant 0$$ y como $\binom{n+m}{n}\in \mathbb{N}$ para todo $m\in \mathbb{N}$, tenemos que $$\nu _p\left (d(n)\right )\geqslant 0$$ por lo tanto, $\nu _p\left (d(n)\right )=0$, de donde $d(n)=1$.

Sea ahora $n=q^k-1$, con $q$ primo, con el mismo razonamiento de antes, vemos que $\nu _p\left (\binom{n+m}{n}\right )=0$ si $p\neq q$ (en este caso el absurdo ocurre pues si $p^{r+1}-1=n=q^k-1$ entonces $p^{r+1}=q^k$, de donde $q\mid p$, por lo que $p=q$ al ser ambos primos), y que $\nu _q\left (\binom{n+m}{n}\right )\geqslant 1$ para todo $m$ (de donde $\nu _q\left (d(n)\right )\geqslant 1$).
Por otro lado, tomando $m=q^{k-1}$ se tiene que
$$\begin{align*}
s_q(n)+s_q(m) & =s_q\left (q^k-1\right )+s_q\left (q^{k-1}\right ) \\
& =k(q-1)+1 \\
& =(k-1)(q-1)+1+(q-1) \\
& =s_q\left (q^k+q^{k-1}-1\right )+(q-1) \\
& =s_q(n+m)+(q-1) \\
\end{align*}$$
Entonces
$$\begin{align*}
(q-1)=-s_q(n+m)+s_q(n)+s_q(m) & \iff (q-1)=n+m-s_q(n+m)-n-m+s_q(n)+s_q(m) \\
& \iff 1=\frac{n+m-s_q(n+m)}{q-1}-\frac{n-s_q(n)}{q-1}-\frac{m-s_q(m)}{q-1} \\
& \iff 1=\nu _q\left ((n+m)!\right )-\nu _q\left (n!\right )-\nu _q\left (m!\right ) \\
& \iff 1=\nu _q\left (\binom{n+m}{n}\right ) \\
\end{align*}$$
por lo que $$\nu _q\left (d(n)\right)=\text{min}\left \{\nu _q\left (\binom{n+m}{n}\right ):m\in \mathbb{N}_n\right \}\leqslant 1$$
Entonces $\nu _q\left (d(n)\right )=1$.
Luego, $\nu _p\left (d(n)\right )=0$ si $p\neq q$ y $\nu _q\left (d(n)\right )=1$, por lo tanto, $d(n)=q$.

Resulta entonces que $d(n)=p$ si $n=p^k-1$ y $d(n)=1$ en otro caso.
Queda Elegantemente Demostrado

Responder