jueves, 9 de febrero de 2012

Problema del dia

a) Sea $S(x)$ la suma de los digitos de $x$ en base decimal.Demuestre que para todo $p$ primo distinto de $2$ y $5$ la funcion $\frac{S(x)}{S(px)}$ no esta acotada para $x>0$.
b) Demuestre que $\frac{S(x)}{S(2x)}\le 5$ para todo $x>0$ y que esa cota no se puede mejorar.

28 comentarios:

Adán dijo...

$b)$. Primero vemos que $\frac{S\left(5\right)}{S\left(10\right)}=5$. Ahora, veamos que como

$S\left(x+y\right)=S\left(x\right)+S\left(y\right)-9z$

donde $z$ es la cantidad de acarreos efectuados al sumar $x+y$.

$\frac{S\left(x\right)}{S\left(2x\right)}\leq5 \leftrightarrow$
$S\left(x\right)\leq 10S\left(x\right)-45z \leftrightarrow$
$5z\leq S\left(x\right)$

Pero por cada acarreo en $x$, implica que tiene una cifra $w\geq5$, de donde se deduce inmediatamente la desigualdad arriba.

Adán dijo...
Este comentario ha sido eliminado por el autor.
Adán dijo...

$a)$. Veamos que para todo $p$ distinto de $2$ y $5$ existe una $k$ tal que

$K=\frac{10^{k}-1}{9}=10^{k-1}+\frac{10^{k-1}-1}{9}=11\ldots11$

es divisible entre $p$. Veamos que $S\left(K\right)=k$. Entonces, veamos los números de la forma $K_{y}=10^{yk-1}+\frac{10^{k-1}-1}{9}$. Sabemos que todos los números de esta forma son divisibles entre $p$, pero además, vamos a notar que si $M$ es un número de $m$ cifras, entonces para todo divisor $n$ de $M$ distinto de $1$, tenemos que $\frac{M}{n}$ tiene a lo más $k$ cifras.

Adán dijo...
Este comentario ha sido eliminado por el autor.
Adán dijo...

Además, tenemos que $S\left(K_{y}\right)=k$. Y veamos que

$K_{y}=10^{yk-1}+\frac{10^{k-1}-1}{9}$
$=\sum_{i=1}^{y-1}{\left(10^{\left(i+1\right)k-1}-10^{ik-1}}\right)+\frac{10^{k}-1}{9}$
$=\left(10^{k}-1\right)\left(\sum_{i=1}^{y-1}{10^{ik-1}}\right)+\frac{10^{k}-1}{9}$

Y veamos que cuando dividamos $K_{y}$ entre $p$, puesto que $10^{k}-1$ tiene $k$ cifras, entonces $\frac{10^{k}-1}{p}$ tiene a lo más $k$ cifras, y entonces, como tenemos que las potencias de la manera $10^{ik-1}$ tienen diferencia $k$ entre elementos consecutivos del mismo tipo, significa que las cifras de $\frac{10^{k}-1}{p}$ van a aparecer periódicamente en $K_{y}$ sin traslaparse para sumarse entre si o hacer acarreos, y al final resta $\frac{10^{k-1}-1}{9p}$.

Adán dijo...

Así podemos ver que $\frac{S\left(\frac{K_{y}}{p}\right)}{S\left(K_{y}\right)}}$ es estrictamente creciente, pues siempre se aumentan cifras a $\frac{K_{y}}{p}$, y por ende, tenemos que $\frac{S\left(x\right)}{S\left(px\right)}$ no esta acotada, como queríamos.

Juan dijo...

a) Construyo una secuencia $\{x_k\}_{k=1}$ que defino con $x_k=\displaystyle\frac{10\ldots01\ldots1}{p}=\displaystyle\frac{10^{k(p-1)-1}+\displaystyle\frac{10^{p-2}-1}{9}}{p}$, con $(p-1)(k-1)$ ceros y $p-2$ unos al final. Por el Teorema de Fermat es fácil ver que $x_k \in \mathbb{Z}$ $\forall k \in \mathbb{N}$. Ahora bien,$S(px_k$) es constante $\forall k \in \mathbb{N}$. (La constante es $p-1$). Ahora bien, si demuestro que $S(x_k)$ es creciente, habré acabado (ésto es fácil de ver). Consideraré $x_{k+1}-x_k$. Es fácil computar ésto, el resultado es $\displaystyle\frac{(10^{p-1}-1)\times10^{k(p-1)-1}}{p}=\displaystyle\frac{9\ldots90\ldots0}{9}$, con $p-1$ 9's y $k(p-1)-1$ ceros. Ahora, si demuestro que $v_{10}(x_{k+1}-x_k) \textgreater \lfloor log_{10}x_k\rfloor$, habré terminado, pues ésto básicamente dice que $x_{k+1}$ es $x_k$ pero con unos dígitos más a la derecha. Conocemos el número de la derecha de la ecuación, es $k(p-1)-1$. Ahora, analizando $log_{10}x_k$, es fácil ver que $x_k \le \displaystyle\frac{2\times10^{k(p-1)-1}}{p} \textless 10^{(k(p-1)-1)}$, por lo que la ecuación sí es cierta, y terminamos la parte a). Quod erat demonstrandum. $\clubsuit$.

Juan dijo...

b) Ésta parte está más fácil. Usando la fórmula S(2x)=2S(x)-9(#acarreos en x+x (a éste número le llamaré y por conveniencia)), entonces el problema se reduce a ver que S(x) $\le$ 10S(x)-45y, o que 5y $\le$ S(x). Pero ésto es cierto, pues hay un acarreo por cada dígito en x mayor o igual a 5. Para ver que la cota es la mejor posible basta considerar x=5. Quod erat demonstrandum. $\clubsuit$.

Juan dijo...

En donde dice 9..90..0/9, no es entre 9, es entre p. Perdón.

Chuck dijo...

a) Veamos, si $p=3$, para cualquier $n$ sea $x_{n}=33\dots 34$

con $n$ dígitos $3$, entonces $S(3x_{n})=3$ pero $S(x_{n})

=3(n+1)+1$, así que $\frac{S(x_{n})}{S(3x_{n})}$ diverge

conforme $n$ crece, así que no puede ser acotado.

Sea $p\neq 2,3,5$, sabemos que $(p,10)=1$, así que por el

Teorema de Fermat $p|10^{n(p-1)}-1$ y que $(p,3)=1$, así que

$a_{n}=100\dots011\dots 1$ con $n(p-1)$ dígitos $0$ y $p-2$ dígitos $1$ después de esto es múltiplo de $p$ (por el Teorema de Fermat, porque esto es congruente con $(10^{p-1}-1)/9$). Ahora veamos que $S(a_{n})$ es constante para toda $n$, pero que $S(\frac{a_{n}}{p})$ es estrictamente creciente y que por lo tanto, no se puede acotar el cociente.

Para probar lo anterior veamos que $a_{n+1}-a_{n}=99\dots 900\dots 0$ con $p-1$ dígitos $9$ y $(n+1)(p-1)-1$ dígitos $0$. Y esto también es múltiplo de $p$, y además $(10,p)=1$, así que $A_{n}:=\frac{a_{n+1}-a_{n}}{p}$ no altera los dígitos de $\frac{a_{n}}{p}$, pues claramente $A_{n}$ tiene $(n+1)(p-1)-1$ dígitos $0$, y $\frac{a_{n}}{p}$ tiene a lo más $(n+1)(p-1)-1$ dígitos. Además, $A_{n}\neq 0$, así que la suma de los dígitos crece y no se pudo acotar el cociente.

Chuck dijo...

b) Para ver que no se puede mejorar, evaluamos en $x=5$ y obtenemos la igualdad. Para demostrar que se puede acotar, veamos que al multiplicar por $2$ sucede algo de lo siguiente:
1) El dígito estaba entre $0$ y $4$ inclusive, entonces en $S(2x)$ estos suman el doble de lo normal, incluso si el dígito anterior a éstos al ser multiplicado por $2$ da más de $10$, pues es menor o igual a $18$ y entonces sólo aumenta en $1$ al doble de éste dígito, es decir, que a lo más es $9$ y no alcanza a pasar al siguiente dígito, así que siguen haciendo que en la suma total, valgan el doble en el denominador del cociente.
2) El dítgito estaba entre $5$ y $9$ inclusive, entonces en $S(2x)$, lo que le corresponde en suma a cada uno, independientemente de si el anterior le agrega una unidad o no a este dígito (por un argumento análogo al de arriba, no afecta), es de $1,3,5,7,9$ para $5,6,7,8,9$ respectivamente, y el cociente de de al menos $\frac{1}{5}$.

Con estas dos observaciones, si un dígito en $x$ es $a$, entonces lo que a éste le corresponde en suma en $2x$ es de al menos $\frac{a}{5}$ (si está en el caso 1), es de $2$ y sino, es de al menos $\frac{1}{5}$) así que $5S(2x)\geq S(x)$ y de aquí obtenemos la desigualdad que buscábamos.

Adán dijo...
Este comentario ha sido eliminado por el autor.
Adán dijo...

Olvidé mencionar una detalle. $S\left(K_{y}\right)$ crece una cantidad constante mayor o igual a $1$ conforme $y$ crece. Como $S\left(K\right)=k$ es constante, tenemos que $\frac{S\left(\frac{K_{y}}{p}\right)}{S\left(K_{y}\right)}$ crece al menos $\frac{1}{k}$ conforme $y$ crece, por lo que $\frac{S\left(x\right)}{S\left(px\right)}$ no está acotado.

JulioC dijo...
Este comentario ha sido eliminado por el autor.
JulioC dijo...
Este comentario ha sido eliminado por el autor.
JulioC dijo...
Este comentario ha sido eliminado por el autor.
JulioC dijo...

a) Veo q por el teorema de Fermat $10^(p-1)-1$ es divisible por p, pues (10,p)=1.
Entonces $10^(k(p-1))+p-1$ es divisible por p. Sea $a_k=(10^(k(p-1))+p-1)/p$. Entonces $S(a_k)=1+S(p-1)$.
Supongamos q existe un n tal q n>= $\frac{S(x)}{S(px)}$ para toda x.
Tomamos $k=9p(p-1)(n(1+S(p-1))+1)$. Entonces a_k tiene al menos 9(p-1)n(1+S(p-1))+1 dígitos. Veamos los dígitos de a_k
Y como p>=3 entonces p-1 tiene menos de p-1 dígitos.

JulioC dijo...

Por tanto dentro de los primeros p-1 dígitos hay uno que no es cero de otra manera pa_k no sería $10^(k(p-1))+p-1$. Pero p_1<p. Entonces pa_k tendrá un dígito distinto de 0 dentro de los dígitos en los q debería haber un 0. Entonces hay otro numero distinto de los q ya había contado. Repitiendo este razonamiento tomando el último dígito d pa_k con los dígitos de a_k q ya tengo, resulta q hay otro dígito distinto de 0 de a_k, que m deja otro dígito de pa_k distinto de 0 a una distancia menor de 9(p-1) del anterior pues k(p-1) tiene a lo más 9(p-1) -1 dígitos.

JulioC dijo...

Entonces como a_k tiene al menos 9(p-1)n(1+S(p-1))+1, entonces el proceso anterior genera al menos n(1+S(p-1))+1 dígitos distintos de 0. Entonces S(a_k)> n(1+S(p-1))+1. Entonces $\frac{S(x)}{S(px)}$>n. Contradicción. Por lo tanto para todo p primo distinto de 2 y 5 la funcion $\frac{S(x)}{S(px)}$ no esta acotada para .

JulioC dijo...

b) Sea x=a_n10^n+a_{n-1}10^{n-1)+…+a_0. Entonces x=2a_n10^n+2a_{n-1}10^{n-1)+…+2a_0 y sabemos q 2a_i es par entre 0 y 18 (Entonces 2a_i+1<10 si 2a_i<10 y 2a_i+1>=10 si 2a_i>=10). Entonces S(2x)=S(2a_n)+S(2a_{n-1})+…+S(2a_0) . Pero para y=1,2,…,9; 5S(2y)<=S(y). Entonces S(2a_n)+S(2a_{n-1})+…+S(2a_0)<=5(S(a_n)+S(a_{n-1})+…+S(a_0)) . Por lo tanto , y no se puede mejorar porq S(5)/S(10)=5

alberto dijo...

a)
Vemos que para $p\textgreater 5$, por el pequeño teorema de fermat y porque $(p,3)=1$:
$p \mid \frac{10^{k(p-1)}-1}{9}$

(para p=3 hacemos lo mismo pero usamos que $3 \mid 111$
Ahora vemos los numeros de la forma $a_k= 10\dots 01\dots 1$, con $k(p-1)$ ceros y $p-2$ unos al final. Vemos que $S(a_k)=p-1$.
Podemos reescribir estos numeros como:
$a_k= 10^{p-2}(10^{k(p-1)}-1) + \frac{10^{p-1}}{9}$
Con esto es facil ver que $p\mid a_k$
Entonces queremos que $\frac{S(\frac{a_k}{p})}{S(a_k)}$ no este acotado, y ya que $S(a_k)$ es constante, queremos que $S(\frac{a_k}{p})$ crezca infinitamente.


$S(\frac{a_k}{p})= S(\frac{10^{p-2}(10^{k(p-1)}-1) + \frac{10^{p-1}}{9}}{p})$

Usamos la formula que dice:
$S(a+b)=S(a)+S(b)-9c$ donde c son los acarreos, entonces:
$S(\frac{a_k}{p}) = S(\frac{10^{p-2}(10^{k(p-1)}-1)}{p}+\frac{10^{p-1}-1}{9p})$
$=S(\frac{10^{p-2}(10^{k(p-1)}-1)}{p})+S(\frac{10^{p-1}-1}{9p})-9c$

Como el primer numero tiene $p-2$ ceros al final y el segundo son p-1 unos divididos entre un primo mayor a dos, que va a dar un numero de a lo mas p-2 digitos, significa que no va a haber ningun acarreo. Y podemos quitar los ceros al final del primer numero y la suma de los digitos sera la misma $\then$

$S(\frac{a_k}{p})=S(\frac{10^{p-2}(10^{k(p-1)}-1)}{p})+S(\frac{10^{p-1}-1}{9p})$
$=S(\frac{(10^{k(p-1)}-1)}{p})+S(\frac{10^{p-1}-1}{9p})$

$S(\frac{10^{p-1}-1}{9p})$ es constante para todas las $a_k$, entonces ahora queremos demostrar que $S(\frac{10^{k(p-1)}-1}{p})$ crece.

$S(\frac{10^{k(p-1)}-1}{p})=S[(\frac{10^{p-1}-1}{p})(\sum ^{k-1}_{i=0} (10^{p-1})^i)]$
Por la cantidad de ceros y digitos vemos que al sumarlos no habra acarreos, entonces eso es igual a:
$=kS(\frac{10^{p-1}-1}{p})$

Y como $S(\frac{10^{p-1}-1}{p})$ es constante para toda las $k$, y k es claramente creciente, demostramos lo que queriamos, por lo que
$\frac{S(\frac{a_k}{p}}{S(a_k)}$ crece, lo que hace que no se pueda acotar asi que terminamos.

alberto dijo...

casi perfecto todo el latex XD
faltaron dos parentesis, en "(para p=3 hacemos lo mismo pero usamos que $3 \mid 111$)" y al final en "$\frac{S(\frac{a_k}{p})}{S(a_k)}$"

alberto dijo...

b)
Usamos la formula del caso anterior:
$S(2x)=2S(x)-9c$

PD
$\frac{S(s)}{S(2x)}=\frac{S(s)}{2S(x)-9c}\leq 5$
$\iff 5c \leq S(x)$

Para que se de un acarreo $2d\geq 10 \iff d \geq 5$, con lo que es claro lo que necesitabamos demostrar.
Se da la igualdad cuando el numero esta formado unicamente por 5s y 0s.

$\frac{S(5)}{S(10}=\frac{5}{1}=5$, por lo que esta cota no se puede mejorar.

Enrique dijo...
Este comentario ha sido eliminado por el autor.
Enrique dijo...
Este comentario ha sido eliminado por el autor.
Enrique dijo...

a) Por Teorema de Fermat, cuando $p\neq 2,5$, $p\mid 10^{k(p-1)}+p-1$ para todo entero no negativo $k$. Es evidente que $S(10^{k(p-1)}+p-1)=p$. Demostraremos que $S(\frac{10^{k(p-1)}+p-1}{p})$ no está acotado, ya que con esto demostraríamos que $S(\frac{10^{k(p-1)}+p-1}{p})/p=\frac{S(\frac{10^{k(p-1)}+p-1}{p})}{S(10^{k(p-1)}+p-1)}$ no está acotado y por lo tanto $\frac{S(x)}{S(px)}$ no está acotado. Basta probar que $S(\frac{10^{(k+1)(p-1)}+p-1}{p})>S(\frac{10^{k(p-1)}+p-1}{p})$. Sea $a=S(p-1)$. Entonces, $\frac{10^{(k)(p-1)}+p-1}{p}=\frac{10^{a}10^{(k)(p-1)-a}+p-1}{p}+\frac{p-1}{p}$ $=10^{a}(q+\frac{r}{p})+\frac{p-1}{p}=10^{a}q+\frac{10^{a}r+p-1}{p}$, con $q,r$ enteros positivos y $r\leq p-1$. Vemos que $S(10^{a}q+\frac{10^{a}r+p-1}{p})=S(q)+S(\frac{10^{a}r+p-1}{p})$, pues $\frac{10^{a}r+p-1}{p}$ tiene a lo más $a$ dígitos. Esto ocurre pues $\frac{10^{a}r+p-1}{p}\leq 10^{a} \Leftrightarrow 10^{a}r+p-1\leq 10^{a}p$ $\Leftrightarrow 10^{a}r\leq 10^{a}p-p+1$, lo cual es cierto pues $r\leq p-1\Rightarrow 10^{a}r\leq 10^{a}p-10^{a}\leq 10^{a}p-p+1$ $\Leftrightarrow p-1\leq 10^{a}$, lo cual siempre es cierto. De la misma manera, vemos que $\frac{10^{(k+1)(p-1)}+p-1}{p}=10^{a+p-1}q+\frac{10^{a+p-1}r+p-1}{p}$. Procediendo similarmente al caso anterior, obtenemos que $S(10^{a+p-1}q+\frac{10^{a+p-1}r+p-1}{p})=S(q)+S(\frac{10^{a+p-1}r+p-1}{p})$. Además, como $\frac{10^{a+p-1}r+p-1}{p}-\frac{10^{a}r+p-1}{p}=\frac{10^{a}(10^{p-1}r-r)}{p}$ es múltiplo de $10^{a}$, los últimos $a$ dígitos de $\frac{10^{a+p-1}r+p-1}{p}$ son iguales a los $x$ dígitos de $\frac{10^{a}r+p-1}{p}$ (si tiene menos dígitos, los demás los contamos como cero). Es claro que $\frac{10^{a+p-1}r+p-1}{p}$ tiene más dígitos que los $x$ que mencionamos pues es mayor que $\frac{10^{a}r+p-1}{p}$. Entonces, $S(\frac{10^{a+p-1}r+p-1}{p})>S(\frac{10^{a}r+p-1}{p})$ $\Rightarrow S(q)+S(\frac{10^{a+p-1}r+p-1}{p})>S(q)+S(\frac{10^{a}r+p-1}{p})$ $\Rightarrow S(\frac{10^{(k+1)(p-1)}+p-1}{p})>S(\frac{10^{k(p-1)}+p-1}{p})$, como queríamos.
b) Tomar $x=5$ es un ejemplo que la cota no puede mejorar. Ahora, tenemos que $S(2x)=2S(x)-9a$, donde $a$ es el número de ``acarreos'' efectuados en la suma decimal de $x+x$. Entonces, basta probar que $S(x)\leq 10S(x)-45a\Leftrightarrow S(x)\geq 5a$. Esto es cierto pues un acarreo ocurre por cada dígito de $x$ que sea mayor o igual a $5$, de donde $a$ es el número de dígitos de $x$ mayores o iguales a $5$. De aquí es trivial que se sigue que $S(x)\geq 5a$, como queríamos. Whew!

Jose Angel SoSa dijo...

b) Veamos que $S(2x)= 2S(x) - 9y$, donde $y$ es la cantidad de digitos de $x$ mayor o igual a 5. Esto es porque si $S(x)= a_{1} + a_{2} + a_{3} +...+ a_{n}$ con $a$ como los digitos entonces $S(2x)= 2a_{1} + 2a_{2} + 2a_{3} +...+ 2a_{n} -9y$ porque por cada digito mayor o igual a 5 al multiplicarlo por 2 se le sumaria en realidad el resultado menos 9 ---> S(10)=2*5-9 ; S(12)=2*6 - 9 ; S(14)=2*7 - 9 ; S(16)=2*8 - 9 ; S(18)=2*9 - 9
entonces si en total hay $y$ digitos mayores o iguales a 5, entonces se le restan 9 y's.
Ahora como queremos que $\frac{S(x)}{S(2x)}\le 5$ es lo mismo que querer $S(x)\le (5)(2S(x) - 9y)$ entonces queremos que $5y\le S(x)$
Pero si lo es pues $y$ es la cantidad de digitos mayores o iguales a 5, y como en S(x) se suman los digitos que lo son y ademas los que no lo son, se da la desiguadad, la igualdad se da con por ejemplo x=5

Juan dijo...
Este comentario ha sido eliminado por el autor.

Publicar un comentario