domingo, 15 de agosto de 2010

Problema 1

(este post es la resolución del problema planteado aquí)


Para encarar la solución de este problema, pensemos uno más pequeño. Supongamos que tenemos un conjunto con los números del 1 al 3 (en lugar de 1 a 2010).


A={1,2,3}


Ahora escribir todos los subconjuntos posibles de este conjunto, lo que llamamos el conjunto de partes de A y lo escribimos P(A), es mucho más simple:


P(A)={{0},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}} (el cero "0" representa el conjunto vacío)


Estos conjuntos ya tienen sus elementos ordenado de menor a mayor, por lo que lo único que falta es hacer la operación de suma alternada de los elementos. Llamaré A0, A1, A2, etc.. a cada subconjunto:


A0={0} -> 0
A1={1} -> 1
A2={2} -> 2
A3={3} -> 3
A4={1,2} -> 1-2=-1
A5={1,3} -> 1-3=-2
A6={2,3} -> 2-3=-1
A7={1,2,3} -> 1-2+3=2


Luego, la suma de todos esos resultados será:


0+1+2+3-1-2-1+2=4


Ese resultado por si solo no nos dice mucho. Para empezar, podemos observar que, siendo el total de subconjuntos 8, el 4 vendría a ser la mitad... podemos suponer, entonces, que el resultado será la mitad de la cantidad de subconjuntos, pero para eso tendríamos que tener, al menos, un ejemplo más. Y aun así no sería para nada suficiente, ya que de las infinitas posibilidades estaríamos tomando sólo 2 para dar una propiedad.


Debemos pensar un poco más.


Miremos los elementos de cada subconjunto. Una cosa que podemos notar es que el 1 aparece en la mitad de ellos, específicamente en A1, A4, A5 y A7. Lo mismo pasa con el 2 y con el 3, cada elemento aparece en la mitad de los subconjuntos. Bien...
El 1, por ser el menor de los elementos, aparecerá siempre en el primer lugar (siempre que aparezca, claro), por lo que siempre tendrá signo positivo y agregará a la suma total 1 por cada uno de los subconjuntos donde aparece, que son la mitad. Bien...
El 2? Aparece en la mitad de los subconjuntos, lo sabemos, pero en qué posición? En algunos, los que tienen el 1, aparece segundo. En otros, los que no tienen el 1, aparece primero... ¿Puede aparecer en otra posición que no sea la primera o la segunda? La respuesta es NO. Por lo tanto, aparecerá en algunos con signo positivo (cuando esté primero) y en otros con signo negativo (cuando esté segundo), pero la pregunta es cuántas veces está primero y cuántas segundo... y la respuesta, observando lo de arriba, es que la mitad de las veces que aparece, lo hace primero, la otra mitad, segundo.
Si se piensa un poco esto, hasta puede llegar a parecer evidente para alguno: todos los números aparecen en la mitad de los subconjuntos y la mitad de las veces que aparecen están en una posición par, la otra mitad en una posición impar...


Esto último significa que, por ejemplo, el 2, aparece la misma cantidad de veces primero (positivo) que segundo (negativo) por lo que en la suma total, se anulará a si mismo... y no agregará nada...


Como todos los números cumplen esto, al hacer la cuenta final sólo los unos agregarán algo a la cuenta y, como dije antes, esa cantidad es igual a la mitad de la cantidad de subconjuntos, es decir, en el ejemplo de recién, 4, ya que los subconjuntos son 8.


Hasta acá se entendió? Si la respuesta es afirmativa, siga leyendo, si no, vuelva para arriba y dese una segunda oportunidad...


Ahora bien, en el ejercicio planteado, el razonamiento es exactamente igual. La cantidad de subconjuntos es 2^2010, que es un número enorme. La mitad de esos subconjuntos tienen un 1 adelante, el resto de los números se anulará en la suma final. Por lo tanto, el resultado de la suma será la mitad de la cantidad de subconjuntos, es decir (2^2010)/2...
Pero como el número que estamos dividiendo por dos es justamente una potencia de dos, podemos restar los exponentes de ambos 2, (2010-1) y decir que la respuesta del ejercicio es:


2^2009


Saludos y nos estamos viendo...

No hay comentarios: