El principio del palomar es una verdad matemática de caracter axiomática, que a pesar de su simple enunciado (que es correcto lógicamente), permite probar afirmaciones de una mayor magnitud.
Enunciado
Cita Si se tienen \( n \) palomas y \( m \) palomares, donde \( n > m \) entonces hay al menos un palomar que tiene más de una paloma.
Ejemplo I: Demuestre que cualquier subconjunto de seis elementos del conjunto \( S = \left \{ 1,2,...,9 \right \} \) debe contener dos elementos cuya suma sea 10.
Resolución
Hay cuatro maneras para que dos elementos (diferentes) de \( S \) sumen 10:$$ 1+9=10,2+8=10,3+7=0,4+6=10 $$Consideremos los siguientes subconjuntos de S: $$ S_{1} = \left \{ 1,9 \right \}, S_{2} = \left \{ 2,8 \right \}, S_{3} = \left \{ 3,7 \right \}, S_{4} = \left \{ 4,6 \right \}, S_{5} = \left \{ 5 \right \} $$Serán los nidos. Todo elemento de \( S \) está en algún nido.
Sea \( A \) un subconjunto de \( S \) con seis elementos. Los elementos de \( A \) serán las palomas. Hay seis palomas. Toda paloma está en algún nido. Hay cinco nidos. Por el principio del palomar, como hay más polmas que nidos, existe algún nido con dos o más palomas. Eso significa que existe algún \( S_{i} \) con dos o más elementos de \( A \).
Como los \( S_{j} \) tienen dos o un elemento, el subconjunto \( S_{i} \) que tiene dos o más elementos de \( A \) contiene exactamente dos elementos de \( A \), entonces no es \( S_{5} \) y es \( S_{1}, S_{2}, S_{3} \) o \( S_{4} \). Luego, hay dos elementos de \( A \) que suman 10, como queríamos demostrar. \( \quad \square \)
Ejemplo II: Sea \( A \subset B \) un sobconjunto de \( n \) elementos distintos del conjunto \( B = \left \{ 1,2,3,...,50 \right \} \). ¿Cuál es el menor \( n \) que garantiza que existen dos elementos distintos de \( A \) que suman 42?
Resolución
Se hacen 20 nidos correspondientes a todas las parejas de elementos distintos en el conjunto que suman 42 (desde 1+41 hasta 20+22). Los números no utilizados se colocan en 10 nidos individuales; en total tenemos 30 nidos:$$ \left \{ (1,41),(2,40),...,(19,23),(20,22),(21),(42),...,(49),(50) \right \} $$Luego, si se eligen al menos 31 elementos distintos del conjunto, se puede asegurar por el principio del palomar que al menos dos de ellos caen en el mismo nido. Necesariamente será un nido de los elementos, que suman 42, de modo que se puede asegurar que al menos dos de ellos suman 42. Por otra parte, si solamente se eligen 30 elementos, podría tomarse uno en cada nido y ningún par de elementos sumaría 42.
En conclusión el mínimo número de elementos que debe tener \( A \) para asegurarse de que haya dos que sumen 42 es 31.
|
|