viernes, 4 de junio de 2010

A nasty problema

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.

11 comentarios:

José Luis Miranda Olvera dijo...

Las a-s son distintas
o puede haber dos iguales?

David (sirio11) dijo...

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

José Luis Miranda Olvera dijo...

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.

David (sirio11) dijo...

Si deben de tener todos los elementos, de hecho eso esta implícito en la palabra partición.

Unknown dijo...

Ya estoy intentando este problema pero aún no me ha salido...

José Luis Miranda Olvera dijo...
Este comentario ha sido eliminado por el autor.
David (sirio11) dijo...

Yo creo que el proceso que hiciste para llegar a esa conclusión te debe de servir

José Luis Miranda Olvera dijo...

Creo que 6, 12, 24, 30 se pueden obtener como sumas de subconjuntos.

José Luis Miranda Olvera dijo...

Creo que 6, 12, 18, 24, 30 se pueden obtener como sumas de subconjuntos.

Georges dijo...

Todavia no me sale el problema.. pero ya lo estuve intentando un rato.

Georges dijo...

Todavia no me sale el problema.. pero ya lo estuve intentando un rato.

Publicar un comentario