miércoles, 15 de mayo de 2013
Problema del día (15-05-2013) (Chiu)
Sea $A=\{a_{1},a_{2},...,a_{n}\}$ con $a_{i}\in\mathbb{R}$. Sea $P(A)$ la media aritmética de los elementos de $A$. Llamamos a $B$ un subconjunto equilibrado de $A$ si $B\subseteq A$ $(B\neq\emptyset)$ y $P(B)=P(A)$.
Si $M=\{1,2,...,9\}$,¿cuál es la cantidad de subconjuntos equilibrados de $M$?
Suscribirse a:
Comentarios de la entrada (Atom)
19 comentarios:
Que problema más feo te escogiste...
Veamos que un subconjunto equilibrado de $B$ de $M$ debe cumplir $P(B)=5$, pues se tendría $P(B)=P(M)=\frac{(1+2+3+4+5+6+7+8+9)}{9} = 5$. Ahora, notemos que si $B$ cumple, entonces el complemento de $B$ cumple, pues tendré que, si $C$ es el complemento de $B$, $\sum_{x \in C} x = \sum_{x \in M} x - \sum_{x \in B} x $$= 45 - 5|B| = 5(9-|B|) = 5|C|$. Así, tengo que el número de subconjuntos equilibrados de $M$ con $4$ elementos o menos es igual al número de subconjuntos equilibrados de $M$ con $5$ elementos o más. Contaré el número de subconjuntos equilibrados de $M$ con $4$ o menos elementos, y al resultado lo multiplicaré por $2$ para obtener la respuesta.
Llamemos $X$ $:$ $\{1,$ $2,$ $3,$ $4\}$ $\mapsto$ $\mathbb{N}_0$ a la función que cuenta el número de subconjuntos equilibrados de $M$con un número determinado de elementos. Es decir, $X(y)$ ($y=$ $1$, $2$, $3$, $4$) cuenta el número de subconjuntos equilibrados de $M$ con $y$ elementos. Entonces la respuesta es $2(X(1)+X(2)+X(3)+X(4))+1$, pues hay que contar $B=M$ aún (pues el vacío no lo contaremos)
Es fácil ver que $X(1)=1$ pues deberé tener $B=\{1\}$.
Es fácil ver que $X(2)=4$ pues deberé tener que $B=\{1$, $9\}$, $\{2$, $8\}$, $\{3$, $7\}$ o $\{4$, $6\}$.
Ahora calculemos $X(3)$. Son las tercias de números menores a $9$ que suman a $3(5)=15$. Claramente deberá haber un número en $B$ menor a $5$ (el promedio), pues de lo contrario todos los elementos serían $5$ y $|B|=1$. Llamemos al menor elemento de $B$, $d$. Por el argumento anterior, $d \le 4$.
Si $d=1$, $X(3)$ cuenta el número de parejas de números mayores a $1$ y menores o iguales a $9$ que suman a $15-1=14$. Claramente hay solamente $2$: ($9$, $5$) y ($8$, $6$). (Notemos que una de estas parejas contiene al número $5$.)
Si $d=2$, $X(3)$ cuenta el número de parejas de números mayores a $2$ y menores o iguales a $9$ que suman a $15-2=13$. Claramente hay solamente $3$: ($9$, $4$), ($8$, $5$) y ($7$, $6$). (Notemos que una de estas parejas contiene al número $5$.)
Si $d=3$, $X(3)$ cuenta el número de parejas de números mayores a $3$ y menores o iguales a $9$ que suman a $15-3=12$. Claramente hay solamente $2$: ($8$, $4$) y ($7$, $5$). (Notemos que una de estas parejas contiene al número $5$.)
Si $d=4$, $X(3)$ cuenta el número de parejas de números mayores a $4$ y menores o iguales a $9$ que suman a $15-4=11$. Claramente hay solamente $1$: ($6$, $5$). (Notemos que una de estas parejas contiene al número $5$.)
Así, $X(3)=2+3+2+1=8$, y exactamente $4$ de los conjuntos $B$ que cuenta no contienen al número $5$.
Continuará...
Finalmente, computemos $X(4)$.
Si $B$ es contado en $X(4)$ y contiene al número $5$, entonces es fácil ver que $B - \{5\}$ es contado en $X(3)$ y no contiene a $5$. Entonces, por el comentario anterior, hay $4$ tales conjuntos $B$.
Ahora cuento a los conjuntos $B$ que son contados en $X(4)$ y no contiene al número $5$. Llamo $Y=\{1,2,3,4\}$ y $Z=\{6,7,8,9\}$. Si $B$ contuviera a $3$ o más elementos de $Y$, entonces $20 = \sum_{x \in B} x \le 2+3+4+9 = 18$, lo cual llevaría a una contradicción. Similarmente, si $B$ contuviera a $3$ o más elementos de $Z$, entonces $20 = \sum_{x \in B} x \ge 6+7+8+1 = 22$, lo cual llevaría a una contradicción. Así, $B$ contiene a exactamente $2$ elementos de $Y$ y $2$ de $Z$.
Ahora, llamo $y$ a la suma de elementos de $Y \cap B$ y $z$ a la suma de elementos de $Z \cap B$. Claramente $y+z=20$, $3 \le y \le 7$ y $13 \le z \le 17$. Así, ($y$, $z$) = ($3$, $17$), ($4$, $16$), ($5$, $15$), ($6$, $14$) o ($7$, $13$).
Vemos que hay $1$ pareja de elementos de $Y$ que suman a $3$, $1$ que suman a $4$, $2$ que suman a $5$, $1$ que suman a $6$ y $1$ que suman a $7$. Análogamente, hay $1$ pareja de elementos de $Z$ que suman a $17$, $1$ que suman a $16$, $2$ que suman a $15$, $1$ que suman a $14$ y $1$ que suman a $13$. Como $B$ se puede formar como la unión de una pareja de elementos de $Y$ y una de $Z$, vemos que hay $1 \times 1$ conjunto(s) $B$ que cumplen ($y$, $z$) = ($3$, $17$), $1 \times 1$ conjunto(s) $B$ que cumplen ($y$, $z$) = ($4$, $16$), $2 \times 2$ conjunto(s) $B$ que cumplen ($y$, $z$) = ($5$, $15$), $1 \times 1$ conjunto(s) $B$ que cumplen ($y$, $z$) = ($6$, $14$), Y $1 \times 1$ conjunto(s) $B$ que cumplen ($y$, $z$) = ($7$, $13$),
Por tanto, hay $1+1+4+1+1=8$ conjuntos $B$ contados en $X(4)$ y que no contienen a $5$. Así, vemos que $X(4)=4+8=12$, por lo que la respuesta es $2(X(1)+X(2)+X(3)+X(4))+1=2(1+4+8+12)+1=51$. Hemos acabado.
RESPUESTA: $\boxed{51}$
Vemos que
$$P\left(M\right)=\frac{1+2+3+4+5+6+7+8+9}{9}=5$$
así que si $N$ es un subconjunto equilibrado de $M$ entonces $P\left(N\right)=5$. Luego, vemos que
$$P\left(N\right)=P\left(M-N\right)=5$$
si $N$ es equilibrado, pues si $N$ tiene $d$ elementos, entonces la suma de los elementos de $N$ es $5d$ y la de $M-N$ es $5\left(9-d\right)$.
Esto nos dice que basta encontrar los conjuntos $N$ equilibrados con a lo más $4$ elementos, y ahorita publico esos casos (que creo que es básicamente todo el problema...)
Si $N$ tiene $1$ elemento, tenemos que $N=\left\{a\right\}$ por lo que
$$\frac{a}{1}=5$$
de donde es claro que $a=5$ y tenemos $1$ caso.
Si $N$ tiene $2$ elementos, tenemos que $N=\left\{a, b\right\}$ por lo que
$$\frac{a+b}{2}=5$$
de donde $a+b=10$ y esto nos genera $4$ casos
$$\left\{1, 9\right\}$$
$$\left\{2, 8\right\}$$
$$\left\{3, 7\right\}$$
$$\left\{4, 6\right\}$$
y acabamos con este caso.
Si $N$ tiene $3$ elementos, tenemos que $N=\left\{a, b, c\right\}$ por lo que
$$\frac{a+b+c}{3}=5$$
de donde $a+b+c=15$ y esto nos genera $8$ casos
$$\left\{1, 5, 9\right\}$$
$$\left\{1, 6, 8\right\}$$
$$\left\{2, 4, 9\right\}$$
$$\left\{2, 5, 8\right\}$$
$$\left\{2, 6, 7\right\}$$
$$\left\{3, 4, 8\right\}$$
$$\left\{3, 5, 7\right\}$$
$$\left\{4, 5, 6\right\}$$
y acabamos con este caso.
Si $N$ tiene $4$ elementos, tenemos que $$N=\left\{a, b, c, d\right\}$$ por lo que
$$\frac{a+b+c+d}{4}=5$$
de donde $a+b+c+d=20$ y esto nos genera $12$ casos
$$\left\{1, 2, 8, 9\right\}$$
$$\left\{1, 3, 7, 9\right\}$$
$$\left\{1, 4, 6, 9\right\}$$
$$\left\{1, 4, 7, 8\right\}$$
$$\left\{1, 5, 6, 8\right\}$$
$$\left\{2, 3, 6, 9\right\}$$
$$\left\{2, 3, 7, 8\right\}$$
$$\left\{2, 4, 5, 9\right\}$$
$$\left\{2, 4, 6, 8\right\}$$
$$\left\{2, 5, 6, 7\right\}$$
$$\left\{3, 4, 5, 8\right\}$$
$$\left\{3, 4, 6, 7\right\}$$
y acabamos este caso.
Ahora, tenemos un total de $25$ casos, y tenemos otros $25$ casos con $5$ o más elementos, y el caso adicional de $M$, por lo que el total de casos son
$$25+25+1=\boxed{51}$$
casos.
:O Lo hicieron a pata o_O
Está bastante bien, pero el chiste de este problema es tratar de hacer algo para no tener que hacer tantos casos.
¿Qué idea podría servir para reducir las cuentas?
Màs simple. En vez de M me tomo $N=\{-4,-3,-2,-1,0,1,2,3,4\}$. El problema es el mismo.
Llamo $f(x)$ al numero de subconjuntos de $\{1,2,3,4\}$ que suman a x. Entonces la respuesta es obviamente $2(\sum f(x)^2)+1$.
Ahora f(x) es 0 excepto si x=1,2,3,4,5,6,7,8,9 o 10. Y las cuentas están más fáciles.
Perdón, arriba es 2(suma)-1
Luego ves que f(x)=f(11-x) y te facilita aun mas las cuentas. Para terminar ves que f(1)=f(2)=1 y que f(3)=f(4)=f(5)=1 y acabas
perdon arriba es f(5)=2
Maldito Chiu troll
Sea $f(x)=(1+x^{-4})(1+x^{-3})\ldots (1+x^4)$. Sea w raíz décima de la unidad. $(f(1)+f(w)+...+f(w^9))/10-3 $ es el numero que queremos, porque cuenta solo los que son multiplos de 10 en su exponente, y le resta 1 del $x^{10}$, del $x^{-10}$ y del conjunto vació.
Sea $g(x)=1+x+x^2+x^3+x^4=(x-w^2)(x-w^4)(x-w^6)(x-w^8)$. Entonces $g(-1)=1$, por lo tanto$f(w^{2k})=2g(-1)=2$. Analogamente sea $h(x)=1+x^2+x^4+x^6+x^8=(x-w)(x-w^2)(x-w^3)(x-w^4)(x-w^6)(x-w^7)(x-w^8)(x-w^9)$ y tenemos $f(w^(2k+1))=-h(-1)=5$, con la excepción de $f(w^5)=0$ porque 1+x=1+w^5=0. Entonces esa suma es
$(512+4*2+4*5+0)/10-3=540/10-3=51$.
:P Facilillo
Publicar un comentario