La comunidad de olímpicos, ex-olímpicos, entrenadores y seguidores de la Olimpiada en Chihuahua, wherever they are in the world.
Por supuesto cualquier olímpico mexicano (para que parar ahí, de todo el mundo pues), esta invitado a comentar.
domingo, 30 de septiembre de 2012
Problema del día. Algebra (30 de septiembre)
Prueba que para cada entero positivo n existe un número de n dígitos múltiplo de 5n y compuesto únicamente de dígitos impares.
nos damos cuenta que funciona para el 1 nuestra hipotesis es que funciona hasta n y P.D que funciona has n+1 bueno por la hipotesis tenemos que existe un numero Y congruente a 0 mod 5 a la n, entonces existe un numero 5y tal que se congruente a 0 mod 5 a la n+1 y ya que Y tiene puros numeros impares sabemos que las multiplicaciones van a impares por 5 por lo tanto todos los numeros van a ser impares
Lo vemos por inducción. Caso base: n=1, 5 es múltiplo de 51 y tiene 1 dígito que es impar. Supongamos que es cierto para k. Hacemos X el número que cumple para k. Las posibles congruencias módulo 5k+1 de X son 0,5k,2(5k),3(5k),4(5k) porque X es múltiplo de 5k y 5k+1=5(5k), las posibles congruencias de 10k son son las mismas por las mismas razones. Entonces alguno de 10k,3(10k),5(10k),7(10k),9(10k) tiene cada una de esas congruencias. Si X cumple para k, alguno de X+10k,X+3(10k),X+5(10k),X+7(10k),X+9(10k) es congruente a 0(modk+1) (porque sin importar la congruencia de X, alguno de esos múltiplos de 10k es congruente a -X). Este número tiene k+1 dígitos (porque X tiene k y al sumarle un múltiplo de 10k le agregamos otro), todos son impares (porque todos los de X lo son y le agregamos un impar) y es múltiplo de 5k+1, por lo tanto si existe para k entonces existe para k+1, como existe para n=1, existe para todos los naturales.
Hasta ahorita lo que llevo es lo siguiente: -Sabemos que todo 5n termina en 25, intentamos ver un patrón para ver las ultimas dos cifras de un múltiplo de 5n: 25∗1=25 25∗2=50 25∗3=75 Cumple 25∗4=100 25∗5=125 25∗6=150 25∗7=175 Cumple 25∗8=200 Observamos que 5n(x≡3mod4) es la única manera de que el múltiplo tenga de 5n tenga todas sus cifras impares. Podemos descomponer el numero como: P.D a1∗10n−1+a2∗10n−2+a3∗10n−3...7∗101+a5∗100\equv0mod5n
Esto es lo poco que avance... P.D. Que para toda n , se cumple que 5n∣M , con M=(5n)k compuesto de n digitos impares. Con inducción, hacemos nuestra base: n→5n∣M Asegurando que esa esa n existe viendo el caso en que n=1 : 1→51∣5 Entonces buscamos un n+1 que cumpla: n+1→5n+1∣M1 , talque M1=(5n+1)q ⇒M1≡Y(mod5)n+1 ⇒Y≡M1(mod5)n+1 Con eso último no se me ocurrio que hacer, asi que ahora uso M : M≡X(mod5)n+1 (5n)k≡X(mod5)n+1 ⇒X≡(5n)0,(5n)1,(5n)2,(5n)3,(5n)4(mod5)n+1 (Alguna de esas congruencias) Creo que de eso puede surgir algo útil... pero hasta aquí tengo.
Me di cuenta de que todos los 5n acaban en 25 , con n>1 Entonces el número al que divide, al ser un múltiplo de 25 va a terminar en 25 , 50 , 75 o 00 . Pero como debe estar compuesto de dígitos impares, el número por el que se multiplica 5n , es decir k , debe ser ≡3(mod4) . Falta demostrar que con eso, el número tendría puros dígitos impares.
Intento.- Vi los casos chicos para encontrar algún patrón: Lo siguiente es de la forma: Para:→Múltiplo de:→Número que cumple: n=1→5→5 n=2→25→75 n=3→125→375 n=4→625→9375 n=5→3125→59375 n=6→15625→35975 De aquí sacamos que para toda n existe un número que cumple tal que es el resultado de agregar un dígito impar a la izquierda al número que cumple para n−1 para lo cual intentaré inducción utilizando los casos n=1,n=2 como casos base. Se debe cumplir que: ∃k∀n:5na1+10n(2k+1)=5n+1a2 donde a1,a2∈N y 0≤k≤4 hasta aqui llevo
Tu idea es la correcta. Para terminar, sólo falta decir que, como 10n es múltiplo de 5n pero no de 5n+1, entonces entre los números 1⋅10n, 3⋅10n, 5⋅10n, 7⋅10n y 9⋅10n hay uno que módulo 5n+1 va a ser congruente a −5na1.
s facil ver que se cumple para los casos n=1,2,3. Veo que 5n divide a 10n entonces escribimos el nuemro 5n veo que para n>3 5n tiene menos de n digitos entonces si le sumamos (2k+1)∗10n a 5n tal que se forme un numero de n digitos eso seguira siendo multiplo de 5n ya que 5n divide a 10n.Entonces viendo que el caso n=3 cumple (375 es el numero que cumple) entonces si a ese numero le agrego un digito impar, y asi le hago para toda n se tendria un numero de n digitos impares, solo hay que ver que sea multiplo de 5n. Entonces veo que al numero que cumple para n-1 le tengo que sumar (2k+1)(10n) solo me falta demostrar que existe (2k+1)(10n) tal que sea congruente a -(el numero que cumple para n-1) modulo 5n. Eso es lo que llevo.
Tu idea es la correcta. Para terminar, sólo falta decir que, como 10n es múltiplo de 5n pero no de 5n+1, entonces entre los números 1⋅10n, 3⋅10n, 5⋅10n, 7⋅10n y 9⋅10n hay uno que módulo 5n+1 va a ser congruente a -(el numero que cumple para n-1) modulo 5n.
Buscamos un entero ktal que
ResponderBorrar10n\textgreater5nk\textgreater10n−1
Leftrightarrow2n\textgreaterk\textgreater2n−1
Vemos que a partir de n\textgreater1,n≡25mod100
Dividimos en cuatro casos:
k≡1mod4⇒5nk≡25mod100
k≡2mod4⇒5nk≡50mod100
k≡3mod4⇒5nk≡75mod100
k≡4mod4⇒5nk≡0mod100
⇒k≡3mod4
Luego vemos que a partir de n>2 si
n≡1mod2⇒5n≡125mod1000
n≡0mod2⇒5n≡625mod1000
Luego vemos 5nkmod1000 y concluimos que si:
5n≡125mod1000⇒k≡3mod8
5n≡625mod100⇒k≡7mod8
De todo esto sacamos que:
2n\textgreaterk\textgreater2n−1
Si n≡1mod2⇒k≡3mod8
Si n≡0mod2⇒k≡7mod8
Tambien podemos ver que al fijarnos en 5nmod10x
podremos acotar kmod2x
Es lo que llevo, aun no encuentro como asegurar la existencia de k
Incompleto.
BorrarLos casos pequeños están bien, pero falta resolverlo en general.
He visto muy poca actividad en este problema (y ya es el tercer día), así que voy a dar una sugerencia:
ResponderBorrarInducción.
nos damos cuenta que funciona para el 1 nuestra hipotesis es que funciona hasta n y P.D que funciona has n+1 bueno por la hipotesis tenemos que existe un numero Y congruente a 0 mod 5 a la n, entonces existe un numero 5y tal que se congruente a 0 mod 5 a la n+1 y ya que Y tiene puros numeros impares sabemos que las multiplicaciones van a impares por 5 por lo tanto todos los numeros van a ser impares
ResponderBorrarIncompleto.
BorrarLas multiplicaciones por 5 no generan digitos impares. Basta con ver que (5)(5)=25, que tiene un digito par.
Este comentario ha sido eliminado por el autor.
ResponderBorrarLo vemos por inducción.
ResponderBorrarCaso base: n=1, 5 es múltiplo de 51 y tiene 1 dígito que es impar.
Supongamos que es cierto para k.
Hacemos X el número que cumple para k.
Las posibles congruencias módulo 5k+1 de X son 0,5k,2(5k),3(5k),4(5k) porque X es múltiplo de 5k y 5k+1=5(5k), las posibles congruencias de 10k son son las mismas por las mismas razones. Entonces alguno de 10k,3(10k),5(10k),7(10k),9(10k) tiene cada una de esas congruencias.
Si X cumple para k, alguno de X+10k,X+3(10k),X+5(10k),X+7(10k),X+9(10k) es congruente a 0(modk+1) (porque sin importar la congruencia de X, alguno de esos múltiplos de 10k es congruente a -X).
Este número tiene k+1 dígitos (porque X tiene k y al sumarle un múltiplo de 10k le agregamos otro), todos son impares (porque todos los de X lo son y le agregamos un impar) y es múltiplo de 5k+1, por lo tanto si existe para k entonces existe para k+1, como existe para n=1, existe para todos los naturales.
Correcto.
BorrarHasta ahorita lo que llevo es lo siguiente:
ResponderBorrar-Sabemos que todo 5n termina en 25, intentamos ver un patrón para ver las ultimas dos cifras de un múltiplo de 5n:
25∗1=25
25∗2=50
25∗3=75 Cumple
25∗4=100
25∗5=125
25∗6=150
25∗7=175 Cumple
25∗8=200
Observamos que 5n(x≡3mod4) es la única manera de que el múltiplo tenga de 5n tenga todas sus cifras impares.
Podemos descomponer el numero como:
P.D
a1∗10n−1+a2∗10n−2+a3∗10n−3...7∗101+a5∗100\equv0mod5n
→
a1∗(4y−1)(5n−1)+a2∗(4y−1)(5n−2)+a3∗(4y−1)(5n−3...7∗(4y−1)(101)+5∗(4y−1)(100)\equv0mod5n
Esto es lo que llevo
Incompleto.
BorrarEs verdad que debe ser ≡3(mod4), pero falta una manera de construir los números.
Esto es lo poco que avance...
ResponderBorrarP.D. Que para toda n , se cumple que 5n∣M , con M=(5n)k compuesto de n digitos impares.
Con inducción, hacemos nuestra base:
n→5n∣M
Asegurando que esa esa n existe viendo el caso en que n=1 :
1→51∣5
Entonces buscamos un n+1 que cumpla:
n+1→5n+1∣M1 , talque M1=(5n+1)q
⇒M1≡Y(mod5)n+1
⇒Y≡M1(mod5)n+1
Con eso último no se me ocurrio que hacer, asi que ahora uso M :
M≡X(mod5)n+1
(5n)k≡X(mod5)n+1
⇒X≡(5n)0,(5n)1,(5n)2,(5n)3,(5n)4(mod5)n+1 (Alguna de esas congruencias)
Creo que de eso puede surgir algo útil... pero hasta aquí tengo.
Me di cuenta de que todos los 5n acaban en 25 , con n>1
BorrarEntonces el número al que divide, al ser un múltiplo de 25 va a terminar en 25 , 50 , 75 o 00 . Pero como debe estar compuesto de dígitos impares, el número por el que se multiplica 5n , es decir k , debe ser ≡3(mod4) .
Falta demostrar que con eso, el número tendría puros dígitos impares.
Este comentario ha sido eliminado por el autor.
BorrarIncompleto.
BorrarEs verdad que debe ser ≡3(mod4), pero falta una manera de construir los números.
Intento.-
ResponderBorrarVi los casos chicos para encontrar algún patrón:
Lo siguiente es de la forma:
Para:→Múltiplo de:→Número que cumple:
n=1→5→5
n=2→25→75
n=3→125→375
n=4→625→9375
n=5→3125→59375
n=6→15625→35975
De aquí sacamos que para toda n existe un número que cumple tal que es el resultado de agregar un dígito impar a la izquierda al número que cumple para n−1 para lo cual intentaré inducción utilizando los casos n=1,n=2 como casos base.
Se debe cumplir que:
∃k∀n:5na1+10n(2k+1)=5n+1a2 donde a1,a2∈N y 0≤k≤4
hasta aqui llevo
Tu idea es la correcta.
BorrarPara terminar, sólo falta decir que, como 10n es múltiplo de 5n pero no de 5n+1, entonces entre los números 1⋅10n, 3⋅10n, 5⋅10n, 7⋅10n y 9⋅10n hay uno que módulo 5n+1 va a ser congruente a −5na1.
Este comentario ha sido eliminado por el autor.
ResponderBorrars facil ver que se cumple para los casos n=1,2,3.
ResponderBorrarVeo que 5n divide a 10n entonces escribimos el nuemro 5n veo que para n>3 5n tiene menos de n digitos entonces si le sumamos (2k+1)∗10n a 5n tal que se forme un numero de n digitos eso seguira siendo multiplo de 5n ya que 5n divide a 10n.Entonces viendo que el caso n=3 cumple (375 es el numero que cumple) entonces si a ese numero le agrego un digito impar, y asi le hago para toda n se tendria un numero de n digitos impares, solo hay que ver que sea multiplo de 5n. Entonces veo que al numero que cumple para n-1 le tengo que sumar (2k+1)(10n) solo me falta demostrar que existe (2k+1)(10n) tal que sea congruente
a -(el numero que cumple para n-1) modulo 5n. Eso es lo que llevo.
Tu idea es la correcta.
BorrarPara terminar, sólo falta decir que, como 10n es múltiplo de 5n pero no de 5n+1, entonces entre los números 1⋅10n, 3⋅10n, 5⋅10n, 7⋅10n y 9⋅10n hay uno que módulo 5n+1 va a ser congruente a -(el numero que cumple para n-1) modulo 5n.