domingo, 26 de mayo de 2013
Problema del 26 de Mayo (Xavi)
Sea $p$un numero primo y $A$ un subconjunto infinito de los números naturales. Sea $f_A(n)$ el numero de soluciones distintas de la ecuación $x_1+x_2+\cdots+x_p=n$, con $x_1, x_2,..., x_p \in A$. ¿Existe algun numero natural $N$ tal que $f_A(n)$ sea constante para todo $n>N$?
Suscribirse a:
Comentarios de la entrada (Atom)
8 comentarios:
Si permuto $x_1$, ..., $x_p$, ¿cuenta como la misma solución?
No, cuenta como una diferente. También, toma en cuenta que algunas de las x's pueden ser iguales.
¿Debo responderlo para todo $A$, o basta con encontrar un $A$ tal que $f_A(n)$ no sea constante?
Debes responder la pregunta para todo $A$
Tomemos un $m$ enorme no divisible entre $p$. Ahora, si $a_1+...+a_p=m$, entonces $a_1=...=a_p$ es falso, y el conjunto $X= \{y_1,...,y_p\}$ genera algunas soluciones de $x_1+...+x_p=m$. Específicamente, genera $p$ en $z_1,...,z_k$ $= \frac{p!}{z_1!...z_k!}$, donde sin pérdida de generalidad $a_1=...=a_{z_1}$, $a_{z_1+1}=...=a_{z_1+z_2$, ..., $a_{z_1+...+z_{k-1}+1}=...=a_p$, donde $z_1+...+z_k=p$ y $k$ no es igual a $1$. Entonces $p$ divide al nùmero se soluciones generadas por $X$. Como toda solución es generada por algún conjunto de ese estilo, $p | f_A(m)$. Así, $p | f_A(n)$ para todo $n$ suficientemente grande.
Pero si nos tomamos un elemento de $A$, digamos $e$ suficientemente enorme y tomamos $m=pe$, es fácil ver que podemos contar las soluciones de $x_1+...+x_p=m$ de la misma manera, más la solución $x_1=...=x_p=e$. Así, $f_A(m) \equiv 1$ (mod $p$).
Así, $p | 1 \Rightarrow p=1$. De ahí es fácil ver que $A=\mathbb{N}-\{1,2,...,M\}$, para algun $M$, y ahí, con $N=M$ funciona. Así, $N$ no existe a menos de que $A$ sea todos los naturales mayores a cierta constante, y $p=1$.
Perdón, arriba, $X=\{a_1,...,a_p\}$, no $\{y_1,...,y_p\}$
Nota: $p$ divide al número de soluciones generadas por $X$ por que $p$ claramente divide a $\frac{p!}{z_1!...z_k!}$ por que $p|p!$ y no divide a $z_i!$ por que $k \ge 2$
Nota: que tonto, $p=1$ no se vale entonces nunca existe $N$.
Publicar un comentario