Subconjuntos sin múltiplos

Enviado por jmd el 15 de Junio de 2009 - 17:21.
Versión para impresiónEnviar a un amigo Share this

Todo subconjunto de tamaño mayor que $ n $ de $ A=\{1,2,\ldots,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,\ldots\}. $ 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 $ k\cdot 2^i,k\cdot 2^j $, para algún impar $ k $ de $ A $. De ahí el resultado.

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