sábado, 26 de mayo de 2012

Problema del día Sábado 26 de Mayo (Diego)

Problema 1. 
Sean $b,n\geq 2$ numero naturales tal que para cada $k\geq 2$ natural exista un entero $a_k$ que cumpla que $b-a_k^n$ es multiplo de $k$. Demuestra que $b=A^n$ para algún $A$ natural. 

Problema 2. 
Sea $n$ un numero natural. Demuestra que 
\[ \binom{2^{n}-1}{0},\;\binom{2^{n}-1}{1},\;\binom{2^{n}-1}{2},\;\ldots,\;\binom{2^{n}-1}{2^{n-1}-1} \]
Son congruentes modulo $2^n$ a $1,3,\ldots, 2^n-1$ en algún orden.

7 comentarios:

Adán dijo...

Para el primero tengo algo, pero está muy fácil, no se si la regué :S Ahí va de todos modos.

Sea $p$ un primo que divide a $b$ y sea $v_{p}\left(b\right)=P$. Ahora, tomamos $k=p^{P+1}$ y sea $x$ el entero que satisface que $p^{P+1}$ divide a $b-x^{n}$.

Claramente, $p$ divide a $x$, por lo que $x=p^{a}\cdot X$ con $\left(p, X\right)=1$. Entonces, tenemos que $x^{n}=p^{an}\cdot X^{n}$, de donde vemos que:

Si $an$ es menor a $P$, entonces la máxima potencia de $p$ que divide a $b-x^{n}$ será $an$, que es menor a $P$, y menor a $P+1$ lo cual es una contradicción.

Si $an$ es mayor a $P$ entonces la máxima potencia de $p$ que divide a $b-x^{n}$ será $P$ que es menor a $P+1$ y eso es una contradicción.

Entonces $P=an$, lo que nos dice que $n$ divide a $P$. Esto lo hacemos para cada exponente de cada primo de $b$ y vemos que $n$ divide a cualquier exponente, de donde $b=A^{n}$, como queríamos.

Chuck dijo...

El primero está sencillo, tomas un primo tal que $p_{i}^{\alpha_{i}}||b$ ahora tomamos a $k=p_{i}^{\alpha_{i}+1}$ y entonces $\frac{k}{p}||a_{k}^{n}$. Ahora, sea $\beta_{i}$ un natural tal que $p^{\beta_{i}}||a_{k}$ por lo tanto $\beta_{i}\cdot n=\alpha_{i}$ de modo que $\beta_{i}=\frac{\alpha_{i}}{n}$ de modo que si $b=\prod_{i=1}^{x}{p_{i}^{\alpha_{i}}}$ entonces
$b^{\frac{1}{n}}=\prod_{i=1}^{x}{p_{i}^{\beta_{i}}}=A\in\mathbb{N}$ por lo tanto $b=A^{n}

Chuck dijo...

El segundo está mal escrito, ¿ no? supongo que más bien te refieres a que son todos los residuos módulo $2^{n-1}$... porque de lo contrario no hay suficientes coeficientes binomiales para tener todos esos residuos...

jorge garza vargas dijo...

No es que esté mal el exponente, es que piden que sean congruentes a los impares.
En realidad devería de decir:
Demuestra que esos coeficientes binomiales son congruentes modulo $2^n$ a $1,3,5...2^n-1$ en algún orden.
http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1555932&sid=91cd28187194d14ad2fb9bf125981b73#p1555932

jorge garza vargas dijo...

El 1 vino en el selectivo de méxico del 2009 y es el N2 de la SL de IMO del 2007.

jorge garza vargas dijo...

Lo reduje a inentar probar la siguiente proposición:

Si $1\leq a\leq b\leq 2^{n-1}-1$ entonces $\prod_{k=a}^b \frac{2^n-k}{k}$ no puede ser $\equiv 1\pmod{2^n}$.

De ahí ya no vi que hacer, ¿algún hint?

Unknown dijo...

Ya tengo la demostración. Se divide en varias partes. Primero chequeamos que los primeros casos cumplan, fácil.
Notemos que $\binom{n}{m}\frac{n-m}{m+1}=\binom{n}{m+1}$. En particular, $\binom{2^n-1}{m}=\binom{2^n-1}{m-1}\frac{2^n-m}{m}=\binom{2^n-1}{m}(\frac{2^n}{m}-1)$.

Por lo tanto,
$\binom{2^n-1}{2r+1}\equiv \binom{2^n-1}{2r}(\frac{2^n-(2r+1))}{2r+1})\equiv \binom{2^n-1}{2r} (\frac{2^n}{2r+1}-1)\equiv -\binom{2^n-1}{2r}$
Mirando modulo $2^n$ (y obviamente $2^{n-1}$ también)

Después, demostramos que $\binom{2^n-1}{4k}\equiv \binom{2^{n-1}-1}{2k}$ modulo $2^{n-1}$.
Para eso fijémonos que
\[ (\frac{2^n}{4i+1}-1)(\frac{2^n}{4i+2}-1)(\frac{2^n}{4i+3}-1)(\frac{2^n}{4i+4}-1)\equiv (-1)(\frac{2^{n-1}}{2i+1}-1)(-1)(\frac{2^{n-1}}{2i+2)-1)\equiv (\frac{2^{n-1}}{2i+1}-1)(\frac{2^{n-1}}{2i+2}-1) \]
Modulo $2^{n-1}$. Asi que llendo de 4 en 4 multiplicandos, podemos concluir que $\binom{2^n-1}{4k}\equiv \binom{2^{n-1}-1}{2k}$ dado que $\binom{2^n-1}{0}=1=\binom{2^{n-1}-1}{0}$.

Ahora veamos que $(\frac{2^{n}}{2i+1}-1)(\frac{2^{n-1}}{2i+1}-1)\equiv -1$ con modulo $2^{n-1}$ y $2^{n}$.
También $(\frac{2^{n}}{2i+1}-1)(\frac{2^{n}}{2i+2}-1)\equiv(\frac{2^{n}}{2i+1}-1)(\frac{2^{n-1}}{i+1}-1)\equiv 1$, modulo $2^{n-1}$. Más aún, tenemos que $(\frac{2^{n}}{4i+1}-1)(\frac{2^{n}}{4i+2}-1)\equiv (-1)(\frac{2^{n-1}}{2i+1}-1)\equiv (-1)(2^{n-1}-1} \equiv 2^{n-1}+1$.
Entonces
$$\binom{2^n-1}{4k}\equiv\binom{2^n-1}{4k+2}\equiv\binom{2^{n-1}-1}{2k}$$
y
$$\binom{2^n-1}{4k+1}\equiv\binom{2^n-1}{4k+3}\equiv\binom{2^{n-1}-1}{2k+1}\equiv -\binom{2^{n-1}-1}{2k}$$.
modulo $2^{n-1}$
Pero también, como $2^{n-1}+1\not\equiv 1$ tenemos que $\binom{2^n-1}{4k}\equiv\binom{2^n-1}{4k+2}+2^{n-1}$ y $\binom{2^n-1}{4k+1}\equiv\binom{2^n-1}{4k+3}+2^{n-1}$ modulo $2^n$.


Ahora supongamos que para $n=m-1$ se cumple. Asi que lo demostraremos para $n=m$. Queremos ver si el impar $1\leq T\leq 2^m-1$ esta en esa secuencia. Supongamos que es congruente a $t$ modulo $2^{m-1}$, con $1\leq t\leq 2^{m-1}-1$. Entonces existe exactamente un entero $0\leq q\leq 2^{m-2}-1$ tal que $\binom{2^{m-1}}-1}{q}\equiv t$ modulo $2^{n-1}$. Entonces sea $r=2q$ si $q$ es par y $2q-1$ si $q$ es impar. Tenemos que, por lo anterior demostrado, $\binom{2^n-1}{r}\equiv t$ modulo $2^{n-1}$. Pero $\binom{2^n-1}{r+2}\equiv \binom{2^n-1}{r}+2^{n-1}$ modulo $2^n$, asi que exactamente uno de esos dos coeficientes cumplen que es congruente a $T$ modulo $2^n$. Por lo tanto, existe un coeficiente binomial de la secuencia que es $T$, para todo $T$ impar entre esos.
Como hay tantos impares en $1,3,\ldots, 2^n-1$ como coeficientes binomiales, entonces cada uno esta exactamente una vez.

Publicar un comentario