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.
lunes, 3 de octubre de 2011
Problema del día Teoría de Números (03 de Octubre))
Por demostrar que las expresiones $2x+3y$ y $9x+5y$ son divisibles por 17 para el mismo conjunto de valores x,y
De la primera ecuacion tenemos: $2x+3y \equiv 17a \pmod{3}$ $2x \equiv 2a \pmod{3}$ se puede dividir porque $(2,3)=1$ $x \equiv a \pmod{3}$
Y tambien despejamos $y$, y la sustituimos a la segunda ecuacion para ver si con las mismas $x$ y $y$ se cumple la ecuacion. $y= \frac{17a-2x}{3}$
$9x+5y=17b$ $9x+5( \frac{17a-2x}{3})=17b$ $\frac{85a+17x}{3}=17b$ $5a+x=3b$ Sabiamos que $a \equiv x \pmod{3}$ entonces $5a+x \equiv 5a+a \equiv 6a \equiv 0 \pmod{3}$ Por lo tanto si se cumple la ecuacion con los mismos valores.
esta fue mi idea. si suponemos que tenemos x,y que cumplen que 2x+3y es multiplo de 17, entonces para probar que 9x+5y es multiplo, entonces debemos comprobar que 7x+2y cumple porque eso mas 2x+3y da 9x+5y, y tenemos que 2x+3y es multiplo de 17. lo mismo va para comprobar que 5x-y es multiplo de 17.
estas son todas las congruencias que hay para esas multiplicacones, para comprobar el problema, elegimos dos numeros de 2x y 3y y tomamos los correspondientes a esos numeros en 5x y y. en los de abajo, deben sumar 17, y en los de arriba deben ser iguales, para que al restarse de 0. ya probe todas las posibilidades y siempre se cumple para ambos.
Suponiendo que 2x+3y es múltiplo de 17, entonces 17 divide a 2x+3y y por tanto a 4(2x+3y)=8x+12y, ademas 17 divide a 17(x+y)=17x+17y, si divide a 17x+17y y a 8x+12y entonces divide a su diferencia que es 9x+5y, por tanto 9x+5y es múltiplo de 17 para las mismas x,y que 2x+3y. Suponiendo que 9x+5y es múltiplo de 17, como 17 divide a 17x+17y entonces divide a a la diferencia de 17x+17y y 9x+5y que es 8x+12y=4(2x+3y), como 17 divide a esto y es primo, debe dividir a 4 o a 2x+3y y como obviamente no divide a 4, divide a 2x+3y; por tanto 2x+3y es múltiplo de 17 para las mismas x,y que 9x+5y. Por tanto 2x+3y, 9x+5y son múltiplos de 17 para los mismos valores de x,y
suponiendo que 17 divide a 2x+3y. llamamos A=2x+3y y B=9x+5y sabemos que 4A+B=17(x+y) y como tenemos que 17 divide a A entonces 17 divide a 4a entonces 17 divide a B. suponiendo que 17 divide a B. tenemos que 4A+B=17(x+y) y como 17 divide a B 17 va a dividir a 4A, ademas si 17 divide a 4a tambien va a dividir a A porque MCD(17,4)=1 por lo tanto 2x+3y9x+5y son múltiplos de 17 para los mismos valores de x,y
lo que yo hize fue bueno pues supongamos que 17 si divide a 2x+3y si 17 divide a 2x+3y entonces tambien divide a 4(2x+3y)=8x+12y luego multiplique 17(x+y)=17x+17y y luego si 17 divide a 17x+17y y tambien a 8x+12y entonces tambien divide a la diferencia que es 9x+5y bueno si divide a 9x+5y pues entonces tambien divide a la diferencia que es 8x+12y=4(2x+3y) bueno entonces para que divida a 4(2x+3y) pues deve de dividir a 4 o a 2x+3y y pues como sabemos que 17 no divide a 4 pues entonces 17 divide a 2x+3y y tambien a9x+5y por lo ya dicho antes
si hablan de divisibilidad, para mi lo mas obvio es usar congruencias, entonces $ 2x + 3y \equiv 0 mod 17 $ y $ 9x + 5y \equiv 0 mod 17 $
primero vere a que llego con la primera $ 3y \equiv -2x mod 17 $ $ 3y \equiv 15x mod 17 $ ($ 17 -2 = 15 $) $ y \equiv 5x mod 17 $ ( se puedoe por que (3,17)=1) creo que es interesante encontrar una igualdad en $y$, ahora veamos si puedo llegar a una igualdad en la otra
$ 9x \equiv -5y mod 17 $ $ 9x \equiv 12y mod 17 $ $ 3x \equiv 4y mod 17 $ (17, 3) = 1 $ 15x \equiv 20y mod 17 $ $ 15x \equiv 3y mod 17 $ $ 5x \equiv y mod 17$
en las dos ecuaciones $y$ es congruente a $5x$, por ende deben ser los mismos numeros x,y para las 2 ecuaciones
Observe que muchos tienen ideas similares así es que intente algo diferente. Digamos que: $2x + 3y = 17a$ y $9x + 5y = 17b$. Trabajando un poco con problema encontramos un tipo de secuencia para ambas variables. Si $x$ tiene los siguientes valores: $4, 5, 6, 7, \cdots$. Y estos son combinados con $y$ y sus siguientes valores: $3, 8, 13, 18, \cdots$. Respectivamente en el orden expresado. En ambas ecuaciones se obtienen múltiplos de 17. Creo que esto podría resolverse por inducción, digamos lo siguiente: $x=3 + n$ $y= -2 + 5n$ Donde $n$ es cualquier natural. De esta manera $x, y$ obtienes los valores antes mencionados. Observamos que tenemos un valor inicial cuando $n=1$, ya que obtenemos las siguientes igualdades: $2x + 3y = 17a$ $= 2(3+n) + 3(-2+5n) = 17a$ $=2(4) + 3(3) = 17$ En la primera ecuación $a=n$ $9x + 5y = 17b$ $= 9(3+n) + 5(-2+5n) = 17b$ $=9(4) + 5(3) = 51$ En la segunda ecuación $b= 2+n$ Para que nuestra hipótesis de inducción sea correcta, se debe cumplir que, si ya se cumple para un valor inicial y un valor $n$ se debe cumplir para $n+1$. Se obtiene, sabiendo los valores de $a$ y $b$: Pn: $2(3+n) + 3(-2+5n) = 17n$ P(n+1): $2(3+n+1) + 3[-2 + 5(n+1)] = 17(n+1)$ $=2(4+n) + 3(3 +5n) = 17(n+1)$ Observamos que la diferencia entre Pn y P(n+1) es que, P(n+1) tiene dos unidades más que Pn [2(3+n) con respecto a 2(4+n)] y además tiene 15 unidades más [3(-2+5n) con respecto a 3(3 +5n)]. Por lo tanto, $17(n+1) = 17n + 2 + 15$ Lo cual es correcto y queda demostrado que los valores para $x$ y $y$ en la primera ecuación cumplen con lo antes mencionado: $x=3 + n$ $y= -2 + 5n$ Análogamente en la segunda ecuación queda demostramos lo mismo, que $x, y$ tienen los mismo valores que en la primer ecuación, y los valores de estos cumplen con la secuencia antes mencionada ($x=4,5,6,7,\cdots$, $y=3,8,13,18, \cdots$) para ambas ecuaciones, por lo tanto, las expresiones dadas son divisibles por $17$ para el mismo conjunto de $x , y$.
Yo lo hice algo talachero pero igual y me salio jeje Sacando con mod17 temenos que X puede ser congruente con:1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,0mod17 por lo que, en ese orden: 2X≡2,4,6,8,10,12,14,16,1,3,5,7,9,11,13,15 o 0mod17 9X≡9,1,10,2,11,3,12,4,13,5,14,6,15,7,16,8 o 0mod17 Luego para que cada una de las expresiones completas sea congruente con 0 modulo 17, saque congruencias de 3Y tales que cumplieran con que 2X+3Y≡0mod17, y tenemos las congruencias posibles para 2X entonces saque el complemento para que la suma de ambas sean congruentes con 0 En orden para complementar 2X tenemos 3Y≡15,13,11,9,7,5,3,1,16,14,12,10,8,6,4,2 o 0mod17 pero para sacar la congruencia de Y en cada una se necesita que las congruencias tambien se puedan dividir entre tres por lo que les di valores divisibles entre 3 3Y≡15,30,45,9,24,39,3,18,33,48,12,27,42,6,21,36 o 0mod17 Por lo que, en el mismo orden 3Y≡5,10,15,3,8,13,1,6,11,16,4,9,14,2,7,12 o 0mod17 Ahora solo saque congruencias mod17 con 5Y 5Y≡8,16,7,15,6,14,5,13,4,12,3,11,2,10,1,9 o 0mod17. Por lo que, como sabemos que con 3Y si cumple solo faltaria checar que 9X+5Y≡0mod17 en cada uno de los casos y asi fue, en cada una de las sumas me salio que los terminos eran congruentes con 0mod17 por lo que si cumple.
@Alberto Ponce: La primera suposición es correcta, si demuestras eso terminas, y eventualmente con talacha modulo 17 puede salir, sin embargo no me consta de que este bien hecha la talacha porque como lo mencionas hay que considerar 289 casos, que me parecen difíciles de hacer uno por uno, a menos que hallas acotado de otra forma no especificada.
@Luis Chacón: Excelente :)
@Antonio López: :)
@Martin Contreras: :)
@ Chuyito_ito: Muy clara la solución, solo un detalle, al llegar a mismas ecuaciones módulo 17 por los dos lados, se requiere que todos los pasos sean si y solo si para poder pasar de una a otra, si van a hacer pero cuando en la segunda parte multiplicaste por 5 falta decir que el paso inverso que es dividir también es válido, por los mismos argumentos de los casos anteriores en que divides diciendo que (5,17)=1, solo eso… pero está muy bien :) …. Pero sigo enojada con tigo por lo que me dijiste ¬¬
@Alejandro Reyes: Primero, es cierto que ese conjunto de x,y cumple la primera ecuación, (se podía sacar solo desarrollando y eliminado términos pero que bueno que practiques inducción xD ) , luego supongo que hiciste algo similar con la segunda ecuación y llegaste al que el conjunto de x=n+3,y=5n-2 cumple, pero ¿como demuestras que no existen otros conjuntos de x ,y que cumplan alguna de las 2 ecuaciones?, si demuestras que no hay más posibles soluciones para x,y entonces terminas el problema, mientras tanto aun está incompleto.
@Padilla: Pues talachero pero se ve bien la talacha y los argumentos de como la hiciste, no pasa nada pero solo te falto quitarle el 3 al 3y de la penúltima lista de congruencias. :)
Supongamos que 17 divide a 2x+3y 17│2x+3y <=>17│2x+3y+17y=2x+20y porque 17│17y <=>17│2x+20y+34x=36x+20y porque 17│34x <=>17│(36x+20y)/4=9x+5y porque (17,4)=1 Con lo cual concluimos que 17│2x+3y<=>17│9x+5y, que es lo que queríamos demostrar.
$2x+3y=17a$
ResponderBorrar$9x+5y=17b$
De la primera ecuacion tenemos:
$2x+3y \equiv 17a \pmod{3}$
$2x \equiv 2a \pmod{3}$ se puede dividir porque $(2,3)=1$
$x \equiv a \pmod{3}$
Y tambien despejamos $y$, y la sustituimos a la segunda ecuacion para ver si con las mismas $x$ y $y$ se cumple la ecuacion.
$y= \frac{17a-2x}{3}$
$9x+5y=17b$
$9x+5( \frac{17a-2x}{3})=17b$
$\frac{85a+17x}{3}=17b$
$5a+x=3b$
Sabiamos que $a \equiv x \pmod{3}$ entonces
$5a+x \equiv 5a+a \equiv 6a \equiv 0 \pmod{3}$
Por lo tanto si se cumple la ecuacion con los mismos valores.
Ahora al reves, en modulo 5 vemos:
$9x+5y \equiv 17b \pmod{5}$
$4x \equiv 2b \pmod{5}$ ahora multiplicamos por 4
$4x \cdot 4 \equiv 2b \cdot 4 \pmod{5}$
$16x \equiv 8b \equiv \pmod{5}$
$x \equiv 3b \equiv \pmod{5}$
Y despejamos $y$ y la sustituimos.
$y= \frac{17b-9x}{5}$
$2x+3y=17a$
$2x+3( \frac{17b-9x}{5} )=17a$
$\frac{51b-17x}{5}=17a$
$3b-x=5a$
Como sabiamos que
$x \equiv 3b \equiv \pmod{5}$
$0 \equiv 3b-x \equiv \pmod{5}$
Entonces tambien se cumple la primer ecuacion.
Por lo tanto los dos conjuntos $(x,y)$ que cumplen son los mismos.
esta fue mi idea. si suponemos que tenemos x,y que cumplen que 2x+3y es multiplo de 17, entonces para probar que 9x+5y es multiplo, entonces debemos comprobar que 7x+2y cumple porque eso mas 2x+3y da 9x+5y, y tenemos que 2x+3y es multiplo de 17. lo mismo va para comprobar que 5x-y es multiplo de 17.
ResponderBorrarlo comprobe con talacha ):
5x=5,10,15,3,8,13,1,6,11,16,4,9,14,2,7,12,0mod17
y=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,0mod17
2x=2,4,6,8,10,12,14,16,1,3,5,7,9,11,13,15,0mod17
3y=3,6,9,12,15,1,4,7,10,13,16,2,5,8,11,14,0mod17
estas son todas las congruencias que hay para esas multiplicacones, para comprobar el problema, elegimos dos numeros de 2x y 3y y tomamos los correspondientes a esos numeros en 5x y y. en los de abajo, deben sumar 17, y en los de arriba deben ser iguales, para que al restarse de 0. ya probe todas las posibilidades y siempre se cumple para ambos.
Suponiendo que 2x+3y es múltiplo de 17, entonces 17 divide a 2x+3y y por tanto a 4(2x+3y)=8x+12y, ademas 17 divide a 17(x+y)=17x+17y, si divide a 17x+17y y a 8x+12y entonces divide a su diferencia que es 9x+5y, por tanto 9x+5y es múltiplo de 17 para las mismas x,y que 2x+3y.
ResponderBorrarSuponiendo que 9x+5y es múltiplo de 17, como 17 divide a 17x+17y entonces divide a a la diferencia de 17x+17y y 9x+5y que es 8x+12y=4(2x+3y), como 17 divide a esto y es primo, debe dividir a 4 o a 2x+3y y como obviamente no divide a 4, divide a 2x+3y; por tanto 2x+3y es múltiplo de 17 para las mismas x,y que 9x+5y.
Por tanto 2x+3y, 9x+5y son múltiplos de 17 para los mismos valores de x,y
Este comentario ha sido eliminado por el autor.
ResponderBorrarsuponiendo que 17 divide a 2x+3y.
ResponderBorrarllamamos A=2x+3y y B=9x+5y sabemos que 4A+B=17(x+y) y como tenemos que 17 divide a A entonces 17 divide a 4a entonces 17 divide a B.
suponiendo que 17 divide a B.
tenemos que 4A+B=17(x+y) y como 17 divide a B 17 va a dividir a 4A, ademas si 17 divide a 4a tambien va a dividir a A porque MCD(17,4)=1 por lo tanto 2x+3y9x+5y son múltiplos de 17 para los mismos valores de x,y
lo que yo hize fue bueno pues supongamos que 17 si divide a 2x+3y
ResponderBorrarsi 17 divide a 2x+3y entonces tambien divide a 4(2x+3y)=8x+12y
luego multiplique 17(x+y)=17x+17y y luego si 17 divide a 17x+17y y tambien a 8x+12y entonces tambien divide a la diferencia que es 9x+5y
bueno si divide a 9x+5y pues entonces tambien divide a la diferencia que es 8x+12y=4(2x+3y)
bueno entonces para que divida a 4(2x+3y) pues deve de dividir a 4 o a 2x+3y y pues como sabemos que 17 no divide a 4 pues entonces 17 divide a 2x+3y y tambien a9x+5y por lo ya dicho antes
si hablan de divisibilidad, para mi lo mas obvio es usar congruencias, entonces
ResponderBorrar$ 2x + 3y \equiv 0 mod 17 $ y $ 9x + 5y \equiv 0 mod 17 $
primero vere a que llego con la primera
$ 3y \equiv -2x mod 17 $
$ 3y \equiv 15x mod 17 $ ($ 17 -2 = 15 $)
$ y \equiv 5x mod 17 $ ( se puedoe por que (3,17)=1)
creo que es interesante encontrar una igualdad en $y$, ahora veamos si puedo llegar a una igualdad en la otra
$ 9x \equiv -5y mod 17 $
$ 9x \equiv 12y mod 17 $
$ 3x \equiv 4y mod 17 $ (17, 3) = 1
$ 15x \equiv 20y mod 17 $
$ 15x \equiv 3y mod 17 $
$ 5x \equiv y mod 17$
en las dos ecuaciones $y$ es congruente a $5x$, por ende deben ser los mismos numeros x,y para las 2 ecuaciones
Este comentario ha sido eliminado por el autor.
ResponderBorrarObserve que muchos tienen ideas similares así es que intente algo diferente.
ResponderBorrarDigamos que: $2x + 3y = 17a$ y $9x + 5y = 17b$.
Trabajando un poco con problema encontramos un tipo de secuencia para ambas variables.
Si $x$ tiene los siguientes valores: $4, 5, 6, 7, \cdots$. Y estos son combinados con $y$ y sus siguientes valores: $3, 8, 13, 18, \cdots$. Respectivamente en el orden expresado. En ambas ecuaciones se obtienen múltiplos de 17.
Creo que esto podría resolverse por inducción, digamos lo siguiente:
$x=3 + n$
$y= -2 + 5n$
Donde $n$ es cualquier natural. De esta manera $x, y$ obtienes los valores antes mencionados. Observamos que tenemos un valor inicial cuando $n=1$, ya que obtenemos las siguientes igualdades:
$2x + 3y = 17a$
$= 2(3+n) + 3(-2+5n) = 17a$
$=2(4) + 3(3) = 17$
En la primera ecuación $a=n$
$9x + 5y = 17b$
$= 9(3+n) + 5(-2+5n) = 17b$
$=9(4) + 5(3) = 51$
En la segunda ecuación $b= 2+n$
Para que nuestra hipótesis de inducción sea correcta, se debe cumplir que, si ya se cumple para un valor inicial y un valor $n$ se debe cumplir para $n+1$. Se obtiene, sabiendo los valores de $a$ y $b$:
Pn: $2(3+n) + 3(-2+5n) = 17n$
P(n+1): $2(3+n+1) + 3[-2 + 5(n+1)] = 17(n+1)$
$=2(4+n) + 3(3 +5n) = 17(n+1)$
Observamos que la diferencia entre Pn y P(n+1) es que, P(n+1) tiene dos unidades más que Pn [2(3+n) con respecto a 2(4+n)] y además tiene 15 unidades más [3(-2+5n) con respecto a 3(3 +5n)].
Por lo tanto, $17(n+1) = 17n + 2 + 15$
Lo cual es correcto y queda demostrado que los valores para $x$ y $y$ en la primera ecuación cumplen con lo antes mencionado:
$x=3 + n$
$y= -2 + 5n$
Análogamente en la segunda ecuación queda demostramos lo mismo, que $x, y$ tienen los mismo valores que en la primer ecuación, y los valores de estos cumplen con la secuencia antes mencionada ($x=4,5,6,7,\cdots$, $y=3,8,13,18, \cdots$) para ambas ecuaciones, por lo tanto, las expresiones dadas son divisibles por $17$ para el mismo conjunto de $x , y$.
Yo lo hice algo talachero pero igual y me salio jeje
ResponderBorrarSacando con mod17 temenos que
X puede ser congruente con:1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,0mod17 por lo que, en ese orden:
2X≡2,4,6,8,10,12,14,16,1,3,5,7,9,11,13,15 o 0mod17
9X≡9,1,10,2,11,3,12,4,13,5,14,6,15,7,16,8 o 0mod17
Luego para que cada una de las expresiones completas sea congruente con 0 modulo 17, saque congruencias de 3Y tales que cumplieran con que 2X+3Y≡0mod17, y tenemos las congruencias posibles para 2X entonces saque el complemento para que la suma de ambas sean congruentes con 0
En orden para complementar 2X tenemos
3Y≡15,13,11,9,7,5,3,1,16,14,12,10,8,6,4,2 o 0mod17
pero para sacar la congruencia de Y en cada una se necesita que las congruencias tambien se puedan dividir entre tres por lo que les di valores divisibles entre 3
3Y≡15,30,45,9,24,39,3,18,33,48,12,27,42,6,21,36 o 0mod17
Por lo que, en el mismo orden
3Y≡5,10,15,3,8,13,1,6,11,16,4,9,14,2,7,12 o 0mod17
Ahora solo saque congruencias mod17 con 5Y
5Y≡8,16,7,15,6,14,5,13,4,12,3,11,2,10,1,9 o 0mod17.
Por lo que, como sabemos que con 3Y si cumple solo faltaria checar que 9X+5Y≡0mod17 en cada uno de los casos y asi fue, en cada una de las sumas me salio que los terminos eran congruentes con 0mod17 por lo que si cumple.
@Alberto Ponce: La primera suposición es correcta, si demuestras eso terminas, y eventualmente con talacha modulo 17 puede salir, sin embargo no me consta de que este bien hecha la talacha porque como lo mencionas hay que considerar 289 casos, que me parecen difíciles de hacer uno por uno, a menos que hallas acotado de otra forma no especificada.
ResponderBorrar@Luis Chacón: Excelente :)
@Antonio López: :)
@Martin Contreras: :)
@ Chuyito_ito: Muy clara la solución, solo un detalle, al llegar a mismas ecuaciones módulo 17 por los dos lados, se requiere que todos los pasos sean si y solo si para poder pasar de una a otra, si van a hacer pero cuando en la segunda parte multiplicaste por 5 falta decir que el paso inverso que es dividir también es válido, por los mismos argumentos de los casos anteriores en que divides diciendo que (5,17)=1, solo eso… pero está muy bien :) …. Pero sigo enojada con tigo por lo que me dijiste ¬¬
@Alejandro Reyes: Primero, es cierto que ese conjunto de x,y cumple la primera ecuación, (se podía sacar solo desarrollando y eliminado términos pero que bueno que practiques inducción xD ) , luego supongo que hiciste algo similar con la segunda ecuación y llegaste al que el conjunto de x=n+3,y=5n-2 cumple, pero ¿como demuestras que no existen otros conjuntos de x ,y que cumplan alguna de las 2 ecuaciones?, si demuestras que no hay más posibles soluciones para x,y entonces terminas el problema, mientras tanto aun está incompleto.
@Padilla: Pues talachero pero se ve bien la talacha y los argumentos de como la hiciste, no pasa nada pero solo te falto quitarle el 3 al 3y de la penúltima lista de congruencias. :)
@Alberto: No me queda clara tu solución, de hecho no me queda claro que el argumento que usaste demuestre el problema.
ResponderBorrarSupongamos que 17 divide a 2x+3y
ResponderBorrar17│2x+3y
<=>17│2x+3y+17y=2x+20y porque 17│17y
<=>17│2x+20y+34x=36x+20y porque 17│34x
<=>17│(36x+20y)/4=9x+5y porque (17,4)=1
Con lo cual concluimos que 17│2x+3y<=>17│9x+5y, que es lo que queríamos demostrar.