Un número $n$ es salvaje si los enteros de $1$ a $n$ se puede partir en tres conjuntos $A$, $B$, $C$ (ajenos dos a dos cuya unión sea el total) de modo que:
a) La suma de los elementos en cada uno de $A$, $B$ y $C$ sea igual.
b) $A$ tiene sólo números impares.
c) $B$ tiene sólo números pares, y
d) $C$ tiene todos los múltiplos de $3$ (y quizás algunos otros números).
Muestra que $8$ es salvaje, que si $n$ es salvaje par entonces $\frac{n+4}{12}$ es entero y encuentra todos los números salvajes menores a $100$.
Extra: Encuentra todos los números salvajes. Hint el viernes.
miércoles, 9 de marzo de 2011
Suscribirse a:
Comentarios de la entrada (Atom)
3 comentarios:
Denotemos $\Sigma\{X\}$ como la suma de los elementos del conjunto $X$.
Veamos primero que como la suma de los $n$ elementos debe poder particionarse en tres conjuntos, entonces $\Sigma\limits_{i=1}^{n}=\frac{n(n+1)}{2}$ es múltiplo de 3, por lo que ya sea que $n$ es múltiplo de $3$, o $n+1$ es múltiplo de $3$. Ahora veamos $C$ contiene a todos los múltiplos de tres, entonces podemos clasificar a $n$ de dos maneras, cuando $n=3k$ y cuando $n=3k+2$ para $k$ un entero no negativo. Para cualquiera de los casos, podemos ver que $\Sigma\{C\}\geq 3\Sigma\limits_{i=1}^{k}i=\frac{3k(k+1)}{2}$ y que como la suma de los $n$ términos serían $\frac{3k(3k+1)}{2}$ ó $\frac{(3k+2)(3k+3)}{2}$ dependiendo del caso,entonces como $\Sigma\{C\}$ debe ser una tercera parte de la suma de los $n$ términos, entonces $\frac{3k(3k+1)}{6}=\Sigma\{C\}\geq\frac{3k(k+1)}{2}$ ó $\frac{(3k+2)(3k+3)}{6}=\Sigma\{C\}\geq\frac{3k(k+1)}{2}$ pero el primero es evidentemente falso, ya que eso significaría que $1\geq 3$ que no es cierto, por lo que sólo se puede que $n=3k+2$ y entonces como $\Sigma\{C\}=\frac{(3k+2)(k+1)}{2}$ y la suma de los múltiplos de $3$ es de $\frac{3k(k+1)}{2}$ debe contener términos no múltiplos de $3$ que sumados nos den $k+1$.
Ahora analicemos los conjuntos $A$ y $B$ y veamos que como uno contiene sólo impares y el otro sólo pares (pero no contienen necesariamente a todos) entonces podemos dividir en otros dos casos, cuando $n$ es par o cuando es impar y aunado al único caso posible analizado anteriormente, $n=6k+2$ ó $n=6k+5$. Si en un principio metemos a todos los impares en $A$ y a todos los pares en $B$:
En el primer caso, como la suma de los elementos de cada conjunto debe ser $\frac{(6k+2)(2k+1)}{2}=(3k+1)(2k+1)$ y la suma de los elementos pares es $2\Sigma\limits_{i=1}^{3k+1}i=(3k+1)(3k+2)$ y la de los impares es el faltante para completar el total, entonces es $(3k+1)^{2}$. Luego, a la hora de sacarles los que deben estar en $C$ por ser múltiplos de $3$ a $B$ le quitaremos los múltiplos de $6$ que es equivalente a $6\Sigma\limits_{i=1}^{k}i=3k(k+1)$ y a $A$ le quitaremos los restantes para el total de múltiplos de tres, que es $3k^{2}$ , por lo que por ahora en caso de que $n=6k+2$ entonces $B$ tiene $(3k+1)(3k+2)-3k(k+1)=(2k+1)(3k+1)+k+1$ osea que le sobran $k+1$ y se los debemos dar a $C$ pero esto sólo es posible si $k$ es impar, por lo que funciona cuando $n=6(2m+1)+2=12m+8$ y entonces si $n$ es par, entonces es congruente a $8$ módulo $12$ y eso significa que $\frac{n+4}{12}$ es entero. Es fácil ver que sí se puede hacer si $k$ es impar, porque simplemente, eliminamos el término $2m+2$ de $B$ y lo pasamos a $C$. En este caso, también debemos ver que $A$ se queda con $(3k+1)^{2}-3k^{2}=(3k+1)(2k+1)+k$ por lo que a $A$ le sobran $k$ entonces como $k$ es impar, basta con quitar a $2m+1$ de la lista de $A$ y dársela a $C$ para acabar. Pero veamos que si $3|m+1$ entonces no podemos pasar el término $2m+2$ de $B$ a $C$ porque ya estaba ahí, pero sí podemos pasar a $2$ y a $2m$ (que son distintos porque $m\geq 2$) y basta con eso. De manera similar, si $3|m+2$ no podemos pasar a $2m+1$ de $A$ a $C$ puesto que ya estaba ahí, sin embargo, podemos pasar a $1$, $7$ y $2m-7$ (no se puede con el 5 ya que el tercer número sería múltiplo de 3) y los dos primeros son los más pequeños que permiten que cumpla (y se necesitan tres números al menos, porque con dos, tenemos una suma par, y con 5 la suma de los que no dependen de $m$ crece y acotarían aún más a $m$), por lo que sirve para $m\geq 10$ ya que para los anteriores tales que $3|m+2$ ya sea que $2m-7$ es negativo, o se repite el valor de $1$ ó $7$.
Mientras que en el segundo caso, cuando $n=6k+5$ entonces lo único que cambia es que cada conjunto debe tener $(6k+5)(k+1)$ elementos y por consecuencia $\Sigma\{A\}=(3k+3)^{2}-3k(k+2)=(6k+5)(k+1)+k+4$ y que $\Sigma\{B\}=(3k+3)(3k+2)-3k(k+1)=(6k+5)(k+1)+k+1$. Para $B$ es lo mismo, por lo que $k=2m+1$ y se aplica la misma estrategia, por lo que siempre se puede. Mientras que con $A$ con quitar al término $2m+5$ basta, a menos que $3|m+2$ en cuyo caso, pasamos de manera similar a $1$, $7$ y $2m-3$ y ésto se puede para $m\geq 4$.
Así que en conclusión, se pueden para $n=12m+8$ dónde $m\geq 10$ y en casos más pequeños, para cuando $m$ toma los valores de $0$,$2$,$3$,$5$,$6$,$8$,$9$. Que equivalen a $8$,$32$,$44$,$68$,$80$,$104$,$116$ respectivamente, por lo que solo los primeros $5$ son menores a $100$. Mientras que para $n=12m+11$ se pueden para todos los $m\geq 4$ y también se puede para cuando $m$ toma los valores de $0$,$2$ y $3$ que equivalen a cuando $n$ es $11$,$35$ y $47$, además de los que sí funcionan para esta forma de $n$ que son en orden ascendente $59$,$71$,$83$ y $95$ antes de pasarse de $100$.
Muy bien Jorge!
Publicar un comentario