Alguien puede elegir libremente diez números. Tú prometes que, escondidos entre todos sus grupos posibles, encontrarás dos grupos separados que pesen exactamente lo mismo.
Los diez elegidos
Enunciado
Una persona elige diez números enteros distintos entre 1 y 100.
Tú haces una promesa:
«Sean cuales sean los diez números elegidos, podré tomar algunos de ellos y separarlos en dos grupos no vacíos y sin ningún número en común, de modo que ambos grupos sumen exactamente lo mismo».
¿Puedes cumplir siempre esa promesa?
Ver solución
Solución
Con diez números pueden formarse:
2¹⁰ = 1024 subconjuntos.
La suma mínima es 0, correspondiente al conjunto vacío. La suma máxima posible no supera la de los diez números mayores entre 1 y 100:
91 + 92 + ··· + 100 = 955.
Por tanto, todas las sumas son enteros comprendidos entre 0 y 955: solo 956 valores posibles.
Como existen 1024 subconjuntos y únicamente 956 sumas posibles, el principio del palomar garantiza que dos subconjuntos distintos, llamémoslos A y B, tienen la misma suma.
A y B podrían compartir números. Eliminamos de ambos todos los elementos comunes. Las sumas siguen siendo iguales, porque restamos la misma cantidad a los dos lados, y los grupos resultantes quedan disjuntos.
Además, ninguno puede quedar vacío. Si el grupo procedente de A quedara vacío, entonces A sería un subconjunto de B. Como A y B son distintos, B contendría al menos un entero positivo adicional, por lo que su suma sería estrictamente mayor que la de A: una contradicción. El mismo argumento vale intercambiando A y B.
Así obtenemos siempre dos grupos no vacíos, sin elementos comunes y con exactamente la misma suma.