viernes, 28 de mayo de 2010

Solución 27 de mayo, Irving

3 comentarios:

Quique12 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.

IrvinG 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!

Quique12 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.

Publicar un comentario