Subconjuntos sin múltiplos

Versión para impresión

Todo subconjunto de tamaño mayor que n de A={1,2,,2n} tiene dos elementos tales que uno es múltiplo del otro.

Demostración(es)
Demostración: 

Para cada uno de los n impares k en A podemos construir el siguiente subconjunto de A:{k,2k,4k,}. Si n=5 se tendría:

k=1,{1,2,4,8}

k=3,{3,6}

k=5,{5,10}

k=7,{7}

k=9,{9}

Los subconjuntos así formados son disjuntos y su unión es A (cada elemento de A pertenece exactamente a uno de los subconjuntos).

Si ahora elijo un subconjunto de más de n elementos de A, por el principio de las pichoneras, habrá dos de ellos en uno de los subconjuntos. Es decir, son de la forma k2i,k2j, para algún impar k de A. De ahí el resultado.

Ver también: 
Múltiplo (de un entero)
Ver también: 
Partición (de un conjunto)