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
jueves, 30 de diciembre de 2010
Suscribirse a:
Comentarios de la entrada (Atom)
9 comentarios:
Este problema ya lo habia visto en este blog. No me agrada el problema ya que tras dias intentandolo siguio vivo.
¿puede haber algunas a's iguales?
Si pueden ser iguales
Ningun avance todavia?
pues intenté usar alguna inducción pero no sale aún :/
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
Igual he intentado lo que Chuck hizo, pero no me parece llevar a nada, he intentado otro par de ideas, pero nada
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
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