Angel "Java" Lopez en Blog

Publicado el 6 de Junio, 2011, 6:07

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:

Problema simple en Teoría de Números

El enunciado es simple:

Sean n números enteros cualesquiera (no necesariamente distintos). Demostrar que siempre existe una sub-colección no vacía cuya suma es divisible por n.

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
A+B+C+D+E = ns + r1

quedando

(A+B+C+D+E) - (A+B+C) = n(s-r)

divisible por n. Queda entonces demostrado ;-)

Nos leemos!

Angel "Java" Lopez
http://www.ajlopez.com
http://twitter.com/ajlopez