Este es uno de los problemas que he resuelto que casi me saco de mis casillas y siempre he querido ver una solución elegante, pues mi solución es muy poco elegante. Quizás alguno de ustedes ya lo haya resuelto y quieran compartir su solución y si no, quizás lo intenten y encuentren una solución chida.
Tienen 32 números naturales tales que a_1+a_2+a_3+.......+a_32 = 120
Todas las a's pertenecen al conjunto {1,2,3,4,...........,59,60}
Demostrar que puedes encontrar 2 colecciones disjuntas (particiones) de los 32 números, tales que la suma de los elementos de una colección es igual a la suma de los elementos de la otra.
viernes, 4 de junio de 2010
Suscribirse a:
Comentarios de la entrada (Atom)
11 comentarios:
Las a-s son distintas
o puede haber dos iguales?
Pueden ser iguales, por ejemplo:
2+2+2+...+2+1+59 = 120 (30 2's)
y las particiones serian: 2+2+...+2 = =60 = 1+59
Las particiones entre las 2 deben tener todos los elementos?,
Si no hay una condicion de este tipo el problema es sencillo, hay en total 2 a la 32 subconjuntos que pueden tener 121 valores: de 0 a 120, por lo tanto hay al menos dos subconjuntos con el mismo valor. Los subconjuntos son distintos, por tanto a ambos podemos quitarles los elementos comunes y su suma seguira siendo igual al compararlas. Al menos uno de ellos es no vacio, puesto que tiene naturales su suma es mayor a 0 y el otro subconjunto es no vacio.
Si deben de tener todos los elementos, de hecho eso esta implícito en la palabra partición.
Ya estoy intentando este problema pero aún no me ha salido...
Yo creo que el proceso que hiciste para llegar a esa conclusión te debe de servir
Creo que 6, 12, 24, 30 se pueden obtener como sumas de subconjuntos.
Creo que 6, 12, 18, 24, 30 se pueden obtener como sumas de subconjuntos.
Todavia no me sale el problema.. pero ya lo estuve intentando un rato.
Todavia no me sale el problema.. pero ya lo estuve intentando un rato.
Publicar un comentario