México rumbo a la IMO: Solución 27 de mayo, Irving

viernes, 28 de mayo de 2010

Solución 27 de mayo, Irving

3 comentarios:

Enrique Treviño dijo...: Esta chida la solucion. Yo habia conjeturado esa respuesta de otra manera (aunque no la he demostrado aún). Lo que hice fue lo siguiente.
Me di cuenta que como la suma de todos los elementos es múltiplo de p, si tienes un conjunto de i elementos que cumple, entonces hay uno de 2p-i elementos tambien.
Luego me puse a pensar cuantos subconjuntos de i elementos tienen su suma = 0 mod p. Si i = 0, entonces es 1. Si i = 1, entonces es 2. Pero lo importante fue ver que para i = 1, si p es impar, entonces la respuesta es 2 para cualquier congruencia mod p. Entonces se distribuyen uniformemente. Despues demostre que se distribuyen uniformemente para i = 2. Luego mi conjetura fue que se distribuye uniformemente para todo i excepto 0, p y 2p (es decir los múltiplos de p). La razon es que (2p C i)/p no es entero en esos casos. Me di cuenta que aunque no fuera uniforme, era cerca de uniforme en esos casos. Meti los numeros que deberian salir y me salio la misma formula que te salio a ti.; 29 de mayo de 2010, 1:29 a.m.
Unknown dijo...: Si es cierto lo que dice Daniel, era con p elementos, leímos mal el problema, o no lo habrán modificado después? Se me hace raro que dos personas lo hayamos leído mal y entendido lo mismo!; 30 de mayo de 2010, 5:21 p.m.
Enrique Treviño dijo...: Que curioso.

Como quiera esta técnica también se puede usar para el otro caso.

Digamos que queremos saber para (i,p)=1 cuantos subconjuntos de i elementos suman un multiplo de p.

Demostrare que el numero de elementos es 1/p*(2pCi).
La demostracion es la siguiente:

Sea {a_1,...,a_i} un subconjunto tal que a_1+...+a_i = 0 mod p.
Entonces {a_1+1,a_2+1,...,a_i+1} cumple que su suma es i mod p.
{a_1+2,...,a_i+2} suman 2i mod p. etc. Entonces tenemos una bijección entre subconjuntos que suman 0,i,2i,...,(p-1)i mod p. Entonces todos son iguales y nos da la demostración.

Como sabemos que hacer con i = 0 e i = 2p y sabemos el número total, podemos despejar que pasa con i = p.; 30 de mayo de 2010, 7:20 p.m.

Publicar un comentario

Suscribirse a: Comentarios de la entrada (Atom)