jueves, 30 de diciembre de 2010

Problema de fin del 2010 (Re: A nasty problem)

Para los que quieren empezar 2011 con un buen reto. Este problema nadie lo resolvio en el ciclo olimpico anterior, veremos si en este hay mas suerte.


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.

Panda

9 comentarios:

Diego627 dijo...

Este problema ya lo habia visto en este blog. No me agrada el problema ya que tras dias intentandolo siguio vivo.

José.Ra dijo...

¿puede haber algunas a's iguales?

IrvinG dijo...

Si pueden ser iguales

David (sirio11) dijo...

Ningun avance todavia?

FerchoAñorvus dijo...

pues intenté usar alguna inducción pero no sale aún :/

Jorge 'Chuck' dijo...

Me fui por casos, intentando usar inducción también, con el principio de casillas, usando separadores como en este: Si incluimos en nuestro conjunto S={a1, a2, … , a32} al 59 y es el más grande, entonces tras realizar A, con 31 ai’s y repartiendo 61 puntitos, vemos que por el principio de casillas, hay al menos un ai que queda con un valor de 1 y que por lo tanto existe la colección {59, 1} que suma 60 y de modo que la otra también sumará 60.
Si en S incluimos al 58 y es el más grande, tras realizar A en este contexto, hay al menos un número menor o igual a 2. Si se da la igualdad, acabamos formando al {2, 58}. En caso contrario, hay al menos 2 unos, puesto que si repartiéramos equitativamente, todos tienen dos, luego para que ninguno tenga 2, deben tener o más, o menos de 2, pero la suma debe ser constante. Si hay 2 menores a 2 acabamos, que es lo mismo que haya 2 mayores, puesto que los menores decrecen en a lo más 1 y los mayores aumentan en a lo menos 1, y si ninguno de estos se da, es porque hay a lo más 2 números distintos de dos y por lo mismo hay al menos un 2. Si hay 2 1’s, entonces formamos la colección {1, 1, 58} y acabamos.

Pero no estoy seguro de que se pueda hacer una inducción, ya lo acabé para más casos pero... no veo la inducción :S

Manuel Alejandro dijo...

Igual he intentado lo que Chuck hizo, pero no me parece llevar a nada, he intentado otro par de ideas, pero nada

Leo dijo...

Yo también estuve intentando ese problema por mucho tiempo y siempre acababa teniendo que intentar muchos casos. Un camino que podrían intentar tomar es el siguiente (yo y otros olímpicos más nos rendimos a la mitad de este camino):

El chiste es encontrar algunos números que sumados den 60.

Lema: Si tienes n números entonces la suma de algunos de ellos es múltiplo de n

Aplicar este lema directamente no sirve. Pero a lo mejor se puede obtener una versión más fuerte que sirva para el problema. Lo difícil es incorporar la condición de que todos son menores o iguales a 60.

Ahorita no recuerdo que más le pude sacar al problema, pero siempre llegaba a tener que hacer casos feos.

Saludos

David (sirio11) dijo...

Yo a este problema le dedique mucho, mucho tiempo hasta que lo resolvi, tengo 2 soluciones y ambas implican resolver miles de casos, por eso siempre he buscado si alguien pudiera sacar una solucion chida.
Como quiera ahi les va la idea de una de mis soluciones:

Decimos que {3} es generado si existe 1+1+1 o 2+1 o 3

Para resolverlo demostré los sigs teoremas:

a) {2} es generado o {60} es generado
b) {3} es generado o {60} es generado
c) {4} es generado o {60} es generado
d) {5} es generado o {60} es generado
e) Si {2},{3},{4},{5} son generados entonces {60} es generado.

Por lo tanto {60} es generado.

Publicar un comentario