miércoles, 23 de marzo de 2011
Problema del Día: n-adas separadas
Sea $X$ un conjunto con $n+1$ elementos ($n\geq 2$). Las $n-$adas ordenadas $(a_1,a_2,\ldots, a_n)$ y $(b_1,b_2,\ldots, b_n)$, cada una con todos sus elementos distintos, se les llama separadas si existen índices $i\neq j$ tales que $a_i=b_j$. Encuentra el máximo número de $n-$adas de modo que cualesquiera $2$ sean separadas.
Suscribirse a:
Comentarios de la entrada (Atom)
8 comentarios:
Y qué pasó con $X$?
¿Una $n$-ada que es la permutación de otra $n$-ada se considera como la misma? (por ejemplo $(a_1,a_2,a_3)$ es lo mismo que $(a_2,a_3,a_1)$?)
Son $n$-adas ordenadas, $(a_1,a_2,a_3)\neq (a_2,a_3,a_1)$.
No entendí para qué sirve $X$, creo que no sirve de nada... pero bueno, aquí está mi solución (Parte1):
Veamos que el máximo que puede haber es de $n^{2}-n+1$ ya que si tomamos a $(a_{1},a_{2},...,a_{n})$ para las que son separadas de esta hay a lo más $n-1$ que contienen a $a_{i}$ para $1\leq i\leq n$ ya que si se repiten dos $n$-adas con ese valor en la misma dimensión, entonces no están separadas. Luego, como hay $n$ valores de $i$ hay $n^{2}-n$ diferentes posibles $n$-adas a partir de la primera, lo que significa que en total el máximo es $n^{2}-n+1$.
Ahora veamos que sí existe un acomodo de modo que se puedan tener $n^{2}-n+1$ $n$-adas separadas dos a dos. Para esto, primero veamos que lo que queremos es que para cada valor en alguna de las $n$-adas, tiene que aparecer en exactamente $n$ de ellas, y como cada una tiene $n$ dimensiones, entonces hay $n^{2}-n+1$ valores distintos. Llamemos a estos $a_{1}$,$a_{2}$,...,$a_{n^{2}-n+1}$ de modo que exista la $n$-ada $b_{1}$ que es $(a_{1},a_{2},...,a_{n})$. Ahora crearemos las siguientes $n-1$ $n$-adas $(a_{n+1},a_{1},a_{n+2},...,a_{2n-1})$,...,$(a_{n^{2}-2n+3},...,a_{n^{2}-n+1},a_{1})$, los cuales sabemos que son separados dos a dos y llamaremos $b_{2}$,...,$b_{n}$. Debemos crear ahora los que tengan en cada dimensión los valores $a_{2}$,...,$a_{n}$ justo como hicimos con $a_{1}$, tomando valores de las $n$-adas desde $b_{2}$ hasta $b_{n}$, uno de cada uno, para lograr que sean separadas con ellas y de modo que no se use dos veces el mismo valor en distintas $n$-adas en la misma dimensión y que no se usen dos valores de la misma $n$-ada ya existente, ni que se repita con las que vamos creando, si es que existe este acomodo, es claro que todos estarán separados dos a dos puesto que si tomamos a una $n$-ada $z$ y vemos sus valores en cada dimensión, los comparte con exactamente $n-1$ $n$-adas (cada uno) y esos subconjuntos son disjuntos entre sí, por lo que está separada de todas.
Primero para crear esto tomaremos $n^{2}-n+1$ conjuntos (no ordenados) que cumplan lo que queremos, osea, que tengan $n$ elementos, que cualesquiera dos compartan sólo un elemento y que la unión de todos sea un conjunto de $n^{2}-n+1$. Para ver que existe, fijemonos en los conjuntos que contienen a $a_{1}$ y veamos que contienen a elementos (además de $a_{1}$) disjuntos de los que contienen los otros, si los elejimos selectivamente de la siguiente forma veremos que funciona:
(parte 2)
En el primer conjunto elegimos a $a_{2}$,...$a_{n}$ con el siguiente los $n-1$ siguientes y así sucesivamente. Ahora los que no tienen a $a_{1}$ pero sí continen a $a_{2}$ seleccionamos $a_{n+1}$,$a_{2n+1}$,...,$a_{n^{2}-2n+1}$, luego a $a_{n+2}$,...,$a_{n^{2}-2n+2}$, y así sucesivamente (notemos que como ya contábamos con el primer conjunto seleccionado, sólo hacía falta seleccionar $n-1$ más). Ahora para los que no contienen ni a $a_{1}$ ni a $a_{2}$ pero sí a $a_{3}$, tendrá a $a_{n+1}$, $a_{2n+2}$,...,$a_{n^{2}}$ (que como no existe y como estamos elijiendo un elemento de cada conjunto de los primeros $n$ que hicimos, entonces dentro de esos valores, tomaremos el valor de la congruencia respectiva, es decir, en este caso, de los $n-1$, vamos restando a $n^{2}$ o el valor que corresponda hasta que quede un número entre $0$ y $n-1$ y con eso se elije el número) y así sucesivamente, luego para el siguiente caso serán $a_{4}$ con $a_{n+1}$,$a_{2n+3}$,... y así sucesivamente para todos hasta $a_{n}$. Esta formación es fácil de ver que entre los que seleccionamos de cada conujunto, están separados entre sí (todos los que contienen a $a_{i}$ para $1\leq i\leq n$) y de hecho, también contra los que fueron creados anteriormente (para una $i$ menor, ya que si para $i,j,k$ fuera distinto, entonces $ik\equiv jk (mod n)$, pero entonces $i\equiv j(mod n)$ y como ambos son menores a $n$, entonces son iguales) por lo que todos son separados entre sí. Sólo hace falta ver que podemos ordenarlos para que cumpla lo que queremos.
En la primera dimensión siempre podemos lograr que haya uno de cada valor, sin mover estos valores, fijémonos en la siguiente dimensión, y como hay $n-1$ da cada valor, siempre podemos encontrar la forma de acomodarlos para que haya uno de cada tipo, y así sucesivamente, dejando a los que ya acomodamos fijos y viendo el siguiente, evidentemente, al final como queda uno de cada uno, entonces claramente se cumple y acabamos.
pues al menos se pueden n!, por que si ponemos todas las permutaciones de los numeros del 1 al n, todas esas son separadas cada 2. Observemos que ese conjunto es maximo, ya no se le pueden agregar n-adas. Ya solo habria que probar que el maximo es n!
Como $X$ fue mencionado en el problema, supongo que los elementos de las $n$-adas deben escogerse entre los elementos de $X$...
Haciendo esa suposición, tomemos todas las $n$-adas ordenadas formadas por $n-1$ elementos y el lugar restante vacío (por ejemplo, $(a_1,a_2,...,a_{n-1},\phi)$, donde $\phi$ es un lugar vacío), y las denominaremos como $n$-adas primitivas. Dos $n$-adas ordenadas no separadas tienen la misma $n$-ada primitiva (los mismos $n-1$ elementos ocupando los mismos lugares) y otro elemento cada una. Entonces, si queremos $n$-adas separadas dos a dos, no se podrá repetir ninguna $n$-ada primitiva. Ahora, tenemos que en total hay $\binom{n+1}{2}$ $n$-adas primitivas no ordenadas y hay $n!$ permutaciones de cada una, por lo que hay $\frac{n(n+1)!}{2}$ $n$-adas primitivas ordenadas, y como cada $n$-ada contiene $n$ $n-1$-adas, hay a lo más $\frac{(n+1)!}{2}$ $n$-adas separadas dos a dos.
Ahora, definiré un algoritmo para obtener las $n$-adas que queremos. Escribimos las $n$-adas primitivas en una tabla. Entonces, las iremos rellenando con números. Tenemos que cada $n$-ada primitiva se puede rellenar con uno de dos números. Como una $n$-ada tiene $n$ $n-1$-adas, al rellenar una $n$-ada primitiva, $n-1$ $n$-adas primitivas quedarán inutilizables, y las marcaremos con una cruz, y otras $n-1$ $n$-adas primitivas quedarán con sólo una opción de relleno, y éstas las marcaremos con una bolita. Es fácil ver que si marcamos una $n$-ada primitiva con dos bolitas, tendremos que marcarla con una cruz. Ahora, siempre que haya $n$-adas primitivas marcadas con una bolita, las rellenaremos. Cuando no, rellenaremos una $n$-ada arbitraria. Así, podemos deshacernos de las bolitas rellenándolas y podremos rellenar $\frac{(n+1)!}{2}$ $n$-adas primitivas; como cada una cancela $n-1$ de las otras, quedarán rellenadas o tachadas las $\frac{n(n+1)!}{2}$ $n$-adas primitivas de la lista.
$(a_{1},a_{2},a_{3})$ está separada de $(a_{1},a_{3},a_{2})$? si es así, entonces creo que tal vez eso debí meterlo a consideración.... pero la solución sale parecida a la que hice, sólo que la respuesta sería $n!$...
Publicar un comentario