Publicado el 6 de Junio, 2011, 6:07
|
Problema simple en Teoría de Números El enunciado es simple:
Vamos, tienen una última oportunidad de resolverlo, antes de leer la solución. A ver, ¿cómo era? Me costó un tiempo resolverlo: me metí por caminos que no llevaban a ninguna parte, como tratar de probarlo por inducción, o armando algoritmos que formaran conjuntos cada vez más cercanos a lo que se pedía. Hasta que me vino el momento !ajá! La solución es: Tomemos los n números, en cualquier orden A, B, C, D, E, ..... , N Si alguno de esos números es divisible por n, ya está solucionado el problema. Si no hay ninguno así, formamos los conjuntos y sus sumas: A, A+B, A+B+C, A+B+C+D, ..... , A+B+C+D+...+N ¿Se entiende? Cada conjunto/suma tiene un elemento más que el anterior. Si alguna de las sumas es divisible por n, ya está la solución. Pero vayamos por el camino difícil: supongamos que ninguno de esos conjuntos es divisible por n. Entonces, cada uno tiene un resto r al dividir por n. Son n restos, distintos de 0. Son n restos, cada uno de los cuales es igual a uno de los n-1 restos: 1, 2, 3, .... n-1 A ver, de nuevo: son n números tomados de n-1 posibles restos. Entonces: ALGUNO SE TIENE QUE REPETIR. Es la aplicación simple del principio de la caja de Dirichlet (ver Pigeonhole principle, de donde tomé la imagen, 10 palomas en 9 lugares). Sea estos dos conjuntos/sumas que dan el mismo resto al dividor por n: A+B+C y A+B+C+D+E Basta retirar/restar el más chico del más grande y queda D+E que DEBE SER DIVISIBLE por n. Pues A+B+C = nr + r1 quedando (A+B+C+D+E) - (A+B+C) = n(s-r) divisible por n. Queda entonces demostrado ;-) Nos leemos! Angel "Java" Lopez |
Veo que me reclaman la solución de este problema todos los días (broma, broma ;-) ) En realidad, nadie preguntó nada, ni dejó comentario... snif... Pero antes que me olvide la solución, acá la dejo publicada. Me estoy refiriendo a la solución del problema que publiqué hace casi un año en: