La comunidad de olímpicos, ex-olímpicos, entrenadores y seguidores de la Olimpiada en Chihuahua, wherever they are in the world.
Por supuesto cualquier olímpico mexicano (para que parar ahí, de todo el mundo pues), esta invitado a comentar.
miércoles, 29 de septiembre de 2010
Problema del dia (29 Sep)
Sea $M$ un conjunto de 10 enteros entre 1 y 100. Probar que dentro de $M$ se pueden encontrar dos subconjuntos ajenos (es decir, sin elementos en común) de tal manera que la suma de los elementos de éstos conjuntos sea la misma.
Pues tengo que el número de sumas que puede tener M es de 955(Tenemos del 1 hasta 91+92+93+...+100=955). Y luego tenemos 2^10=1024 subconjuntos posibles del conjunto M, pero serían 1023 subconjuntos ya que no estamos contando el vacio. Y pues tenemos que por casillas hay dos conjuntos con la misma suma (Nota: todos los subconjuntos que contamos 2^10 son diferentes). Ahora, si los subconjuntos tienen elementos en común, simplemente podemos quitar esos elementos a ambos subconjuntos y la suma seguiría siendo la misma.
Nose si este bien o si tiene logica mi argumento, si algo esta mal les agradecería mucho que me lo indicaran. :)
Nomas para aclarar, con el numero de sumas de M, me refiero a todos los diferentes valores que el conjunto de M puede ser pero la verdad son 955(955= 91+92+93+...+100 [Suma máxima posible])- 55 (55=1+2+3+...+10 [Suma Mínima posible])=900, pero 955 es el rango de valores posibles para un subconjunto de M, teniendo a 955 como el valor máximo.
M tiene $2^{10}=1024$ subconjuntos, y como no estamos contando el vacio, lo quitamos y tenemos 1023. La maxima suma que puede tener ese subconjunto es cuando tomamos los diez numeros mas grandes, que son $91, 92, \dots, 100$. Lo sumamos y nos da 955. La minima es 1, asi que tenemos 955 sumas posibles diferentes, y 1023 subconjuntos, asi que por casillas al menos una se va a repetir 2 o mas veces. Esos dos subconjuntos son diferentes, pero no necesariamente ajenos. Si son ajenos pues esa es la suma de dos subconjuntos igual, pero si no lo son, le quitamos a ambos subcconjuntos los elementos que tengan en comun. Como eran diferentes y ninguno es 0, van a sobrar elementos en cada subconjunto nuevo, que van a seguir teniendo la misma suma porque le quitamos lo mismo a ambos subconjuntos.
a me falto decir que si los subconjuntos tienen elementos en comun, simplemente los quitamos y la suma de los subconjuntos se le habra restado lo mismo, por lo que seguiran teniendo la misma suma.
y no sabia como saber que los subconjuntos no tenian elementos en comun, pero ya viendo la solucion de alberto, pues los quitamos del subconjunto y ya xD
Cero comentarios? Parece que nadie quiere ir al nacional.
ResponderBorrarYo si lo he estado intentando pero no me ha salido :S y es que yo usualmente comento hasta que ya tenga una solucion
ResponderBorrarSoy Irving Mtz. Acosta
ResponderBorrarPues tengo que el número de sumas que puede tener M es de 955(Tenemos del 1 hasta 91+92+93+...+100=955). Y luego tenemos 2^10=1024 subconjuntos posibles del conjunto M, pero serían 1023 subconjuntos ya que no estamos contando el vacio. Y pues tenemos que por casillas hay dos conjuntos con la misma suma (Nota: todos los subconjuntos que contamos 2^10 son diferentes). Ahora, si los subconjuntos tienen elementos en común, simplemente podemos quitar esos elementos a ambos subconjuntos y la suma seguiría siendo la misma.
ResponderBorrarNose si este bien o si tiene logica mi argumento, si algo esta mal les agradecería mucho que me lo indicaran. :)
Nomas para aclarar, con el numero de sumas de M, me refiero a todos los diferentes valores que el conjunto de M puede ser pero la verdad son 955(955= 91+92+93+...+100 [Suma máxima posible])- 55 (55=1+2+3+...+10 [Suma Mínima posible])=900, pero 955 es el rango de valores posibles para un subconjunto de M, teniendo a 955 como el valor máximo.
ResponderBorrarMuy bien Irving. La respuesta es correcta.
ResponderBorrarEste problema fue de una internacional, creo que en los 70s. Que buena onda que te salió.
enserio? :O
ResponderBorrarque suave :D
M tiene $2^{10}=1024$ subconjuntos, y como no estamos contando el vacio, lo quitamos y tenemos 1023.
ResponderBorrarLa maxima suma que puede tener ese subconjunto es cuando tomamos los diez numeros mas grandes, que son $91, 92, \dots, 100$. Lo sumamos y nos da 955.
La minima es 1, asi que tenemos 955 sumas posibles diferentes, y 1023 subconjuntos, asi que por casillas al menos una se va a repetir 2 o mas veces.
Esos dos subconjuntos son diferentes, pero no necesariamente ajenos. Si son ajenos pues esa es la suma de dos subconjuntos igual, pero si no lo son, le quitamos a ambos subcconjuntos los elementos que tengan en comun. Como eran diferentes y ninguno es 0, van a sobrar elementos en cada subconjunto nuevo, que van a seguir teniendo la misma suma porque le quitamos lo mismo a ambos subconjuntos.
Bien hecho Alberto.
ResponderBorrarSaben que onda con los demás? Nadie parece comentar fuera de ustedes dos.
no :/
ResponderBorrarsolo se que leonardo no tiene internet
de los demas nada...
tenemos que existen $2^10$ subconjuntos
ResponderBorrarpero sabemos que entre la maxima suma y la minima
que son
maxima $91+92+93+...+100=955$
minima $1$
existen 955 resultados distintos, pero $2^10$ es mayor, por lo que habra sumas repetidas.
a y otra cosa:
karina habia dicho que se le descompuso su computadora o algo asi jeje pero si los hace ok
y los demas no se.
a me falto decir que si los subconjuntos tienen elementos en comun, simplemente los quitamos y la suma de los subconjuntos se le habra restado lo mismo, por lo que seguiran teniendo la misma suma.
ResponderBorrarhttp://picasaweb.google.com/lh/photo/DQRjJiEEfshFPQ6SSjmobmzY3-qDUM5OlqEu_XVViso?feat=directlink
ResponderBorrary no sabia como saber que los subconjuntos no tenian elementos en comun, pero ya viendo la solucion de alberto, pues los quitamos del subconjunto y ya xD