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, 10 de octubre de 2011
Problema del día, Teoría de números (10 de Octubre)
Ya que Karina y Daniel andan de viaje yo pondré los problemas de hoy y del miercoles.
Demuestra que (n−1)2 divide a nn−1−1 para todo entero n con n≥2
tenemos que nn−1−1=(n−1)(nn−2+...+n+1) por lo tanto n-1 divide a nn−1−1 y queremos que n divida a lo otro y como nn−2,...,n son multiplos de n van a ser congruentes a -1 mod n-1 y esto se sumara n-2 veces, entonces la suma de todo eso va a ser congruente n-2 mod n-1 y 1 es congruente a 1 mod n-1 por lo tanto la suma de rodo esto es congruente a n-1 mod n-1 que es congruente a 0 y por lo tanto (n−1)2 divide a nn−1−1
Se puede decir que nn−1−1=(n−1)(nn−2+⋯+1) y el demuestra el problema si n−1 divide a (nn−2+⋯+n+1)
Sabemos que cualquer multiplo de n sera congruente a 1 mod n-1 por lo que la suma anterior seria de n-1 unos y eso suman n-1 y es divisible entre n-1 y queda demostrado.
llo llegue a que nn−1−1$esiguala{n-1}\{n^{n-2} +\cdots +n+}1porlocualyatenemosque{n-1}\dividean^{n-1}-1\yluegotenemosque{n^{n-2} +\cdots +n+1}\$ es multiplo de n y eso es todo a lo que he llegado lo seguire intentando
Primero factorizé (n−1)2 y nn−1−1 en (n−1)(n−1) y (n−1)(nn−2+nn−3+...+n+1) respectivamente. Si a*a*k=a*b entonces a*k=b, aplicando eso al problema, para demostrar que (n−1)(n−1) divide a (n−1)(nn−2+nn−3+...+n+1) basta con demostrar que n-1 divide a (nn−2+nn−3+...+n+1). Vemos todo en mod n-1, como en todos son n's elevadas a alguna potencia, se pueden ver como 1's (porque n≡1 mod n-1) que elevados a cualquier potencia es 1, como estamos sumando los 1's con exponente de 0 hasta n-2, tenemos n-1 1's que sumados dan n-1 y por tanto congruencia 0. Para n=1, n-1=0, 02=0 y creo que 0 no divide a ningún número. (No encontré una respuesta distinta a la que ya habían dicho)
Se expresa n(n−1)−1 como una Diferencia de Potencias y se obtiene la siguiente igualdad: nn−1−(1)n−1=(n−1)(nn−2∗10+nn−3∗11+⋯+n1∗1n−3+n0∗1n−2). Se observa claramente que entonces, n−1 divide a nn−1−1. Ahora resta demostrar que n−1 divide a (nn−2∗10+nn−3∗11+⋯+n1∗1n−3+n0∗1n−2). Se llama a esta ecuación α. En este paso tuve la idea de usar la formula de suma de potencias e intentar utilizar las igualdades obtenidas pero me di cuenta que estaba en algo incorrecto (Solo como comentario). De vuelta al problema, entonces es posible decir que: (nn−2∗10+nn−3∗11+⋯+n1∗1n−3+n0∗1n−2)=(nn−2+nn−3+⋯+n1+n0), (1 a k potencia seguirá siendo 1). Se tiene una suma de potencias de base n desde n0 hasta nn−2. Cada base n es congruente a 1(modn−1). (De manera que 4 es congruente con 1 mod 3, por dar un ejemplo) Entonces se representa la ecuación antes mencionada como: nn−2+nn−3+⋯+n1+n0≡(1)n−2+(1)n−3+⋯+(1)1+(1)0 Al tener n−1 elementos sumándose, el valor de esta operación será n−1. Por lo tanto, n−1 divide a α. De esta queda demostrado lo que se pide.
nn−1−1=(n−1)(nn−2+⋯+n+1)
ResponderBorrarentonces n−1 divide a nn−1−1, si n−1 dividiera a (nn−2+⋯+n+1) entonces ya acabariamos
n≡n−(n−1)≡1modn−1 por ende
nk≡1modn−1 y por lo tanto
(nn−2+⋯+n)+1≡(n−2)+1modn−1 ya que hay n−2 factores de n,
(n-2) +1 \equiv n-1 equiv 0 mod n-1
por ende n−1 divide a (nn−2+⋯+n+1) y por lo tanto (n−1)2 divide a nn−1−1
Sabemos que nn−1−1=(n−1)(nn−2+⋯+1)
ResponderBorrarEntonces aqui hay un n−1, y queremos que n−1 tambien divida a lo demas.
nn−2+⋯+n+1≡(1)n−2+⋯+(1)+1≡1+⋯+1≡n−1≡0(modn−1)
Entonces (n−1)2 divide a nn−1−1
tenemos que nn−1−1=(n−1)(nn−2+...+n+1) por lo tanto n-1 divide a nn−1−1 y queremos que n divida a lo otro y como nn−2,...,n son multiplos de n van a ser congruentes a -1 mod n-1 y esto se sumara n-2 veces, entonces la suma de todo eso va a ser congruente n-2 mod n-1 y 1 es congruente a 1 mod n-1 por lo tanto la suma de rodo esto es congruente a n-1 mod n-1 que es congruente a 0 y por lo tanto (n−1)2 divide a nn−1−1
ResponderBorrarSe puede decir que
ResponderBorrarnn−1−1=(n−1)(nn−2+⋯+1)
y el demuestra el problema si n−1 divide a
(nn−2+⋯+n+1)
Sabemos que cualquer multiplo de n sera congruente a 1 mod n-1 por lo que la suma anterior seria de n-1 unos y eso suman n-1 y es divisible entre n-1 y queda demostrado.
Entonces (n−1)2 divide a nn−1−1
llo llegue a que nn−1−1$esiguala{n-1}\{n^{n-2} +\cdots +n+}1porlocualyatenemosque{n-1}\dividean^{n-1}-1\yluegotenemosque{n^{n-2} +\cdots +n+1}\$ es multiplo de n
ResponderBorrary eso es todo a lo que he llegado lo seguire intentando
Primero factorizé (n−1)2 y nn−1−1 en (n−1)(n−1) y (n−1)(nn−2+nn−3+...+n+1) respectivamente. Si a*a*k=a*b entonces a*k=b, aplicando eso al problema, para demostrar que (n−1)(n−1) divide a (n−1)(nn−2+nn−3+...+n+1) basta con demostrar que n-1 divide a (nn−2+nn−3+...+n+1). Vemos todo en mod n-1, como en todos son n's elevadas a alguna potencia, se pueden ver como 1's (porque n≡1 mod n-1) que elevados a cualquier potencia es 1, como estamos sumando los 1's con exponente de 0 hasta n-2, tenemos n-1 1's que sumados dan n-1 y por tanto congruencia 0. Para n=1, n-1=0, 02=0 y creo que 0 no divide a ningún número. (No encontré una respuesta distinta a la que ya habían dicho)
ResponderBorrarEste comentario ha sido eliminado por el autor.
ResponderBorrarEste comentario ha sido eliminado por el autor.
ResponderBorrarProblemas con LATEX una disculpa.
ResponderBorrarSe expresa n(n−1)−1 como una Diferencia de Potencias y se obtiene la siguiente igualdad:
nn−1−(1)n−1=(n−1)(nn−2∗10+nn−3∗11+⋯+n1∗1n−3+n0∗1n−2).
Se observa claramente que entonces, n−1 divide a nn−1−1. Ahora resta demostrar que n−1 divide a (nn−2∗10+nn−3∗11+⋯+n1∗1n−3+n0∗1n−2). Se llama a esta ecuación α.
En este paso tuve la idea de usar la formula de suma de potencias e intentar utilizar las igualdades obtenidas pero me di cuenta que estaba en algo incorrecto (Solo como comentario).
De vuelta al problema, entonces es posible decir que:
(nn−2∗10+nn−3∗11+⋯+n1∗1n−3+n0∗1n−2)=(nn−2+nn−3+⋯+n1+n0), (1 a k potencia seguirá siendo 1).
Se tiene una suma de potencias de base n desde n0 hasta nn−2.
Cada base n es congruente a 1(modn−1). (De manera que 4 es congruente con 1 mod 3, por dar un ejemplo)
Entonces se representa la ecuación antes mencionada como:
nn−2+nn−3+⋯+n1+n0≡(1)n−2+(1)n−3+⋯+(1)1+(1)0
Al tener n−1 elementos sumándose, el valor de esta operación será n−1. Por lo tanto, n−1 divide a α.
De esta queda demostrado lo que se pide.
@Chuy,Alberto,Antonio,Alberto Ponce,Alex: tienen un detalle tan pequeño que lo voy a pasar por alto :) (ver siguiente comentario)
ResponderBorrar@Luis: Muy bien en mencionar al 1 :)
@Martin: Sigue intentando :P