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.
jueves, 9 de febrero de 2012
Suscribirse a:
Comentarios de la entrada (Atom)
28 comentarios:
$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.
$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.
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}$.
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.
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$.
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$.
En donde dice 9..90..0/9, no es entre 9, es entre p. Perdón.
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.
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.
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.
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.
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.
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 .
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
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.
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)}$"
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.
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!
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
Publicar un comentario