Story Transcript
0.1.
1
POLINOMIOS TORRES
0.1 Polinomios Torres Un tablero es un arreglo rectangular de casillas cuadradas de igual arista, que pueden ser blancas o sombreadas, y que están unidas por sus aristas. Las casillas sombreadas se consideran nulas o borradas. Veremos, más adelante, que en algunos casos conviene invertir los roles blancas-sombreadas. La Figura 0.1 muestra varios ejemplos de tableros. En la parte ( ) no se dibujaron las casillas nulas. En ( ) y en ( ) se muestra el mismo tablero, pero en ( ) no se dibujaron las casillas nulas externas. b
c
d
d
()
()
a
()
b
()
c
d
Figura 1: Ejemplos de Tableros Una torre es una pieza que como en el juego de ajedrez se puede mover de la posición donde se encuentre a cualquier casilla no nula, que se encuentre en la misma la o en la misma columna que ella, sin importar si hay o no casillas nulas en su camino. Si dos torres están en la misma línea ( la o columna) se dice que se pueden capturar mutuamente. Dado un tablero y un número de torres se desea saber de cuántas maneras se pueden colocar las torres en las casillas no nulas del tablero sin que se capturen (que no haya dos torres en la misma la ni en la misma columna). Para un tablero dado, a este número, lo llamaremos ésimo número de torre y lo denotaremos por k . Por ejemplo, para el tablero 1 de la Figura 2 se tiene que 0 porque hay sólo una manera de colocar cero torres en dicho tablero; 1 porque la torre podría colocarse en cualquiera de las seis casillas del tablero. Para ver que 2 podríamos dibujarlas C C cada una de las siete formas. Finalmente porque, para que no se capturen, las 3 Figura 2: Un ejemplo más tres torres sólo se pueden colocar en la diagonal. Es claro que k si ; esto se debe a que cada torre debe estar en una la diferente y sólo hay tres las. Podemos concluir que la función genera2 3 . Como esta función generatriz triz de esta sucesión es es realmente un polinomio formal se le denomina polinomio torre del tablero. El 2 3. polinomio torre del tablero 2 de la Figura 2 es 2 Comentario: Tal vez la forma más fácil de contar 2 para el tablero 1 de la Figura 2 es elegir las dos columnas donde se colocarán las torres. Si elegimos las columnas 1 y 2 hay cuatro formas de colocar las torres, si elegimos la 1 y la 3 hay dos posibilidad y nalmente si elegimos la 2 y la 3 sólo hay una forma de k
k
k
t
C
t
t
= 6
t
t
= 1
= 7
1
2
= 1
t
= 0
k
4
T (z) = 1 + 6z + 7z
C
+z
T (z; C ) = 1 + 5z + 6z t
C
+ 2z
2 colocar las torres. Luego, en base al principio de adición, hay un total de siete formas de colocar 2 torres en el tablero 1 . De nición 0.1 (Polinomio Torre) Dado un tablero se denomina polinomio torre del tablero a la función generatriz de la sucesión que cuenta cuántas maneras hay de colocar en dicho tablero torres sin que se capturen. A continuación trataremos de hallar el polinomio torre de algunos tableros pequeños. Ejemplo 0.1 Halle los polinomios torre de los tableros de la Figura 3. Explicación: El polinomio torres de 1 es , porque sólo hay una 1 manera de colocar cero torres en 1 el tablero después de colocarlas queda C C C igualy hay una única manera de colocar una torre en dicho tablero. Los polinomios torres de 2 y 3 son respectivamente y 2 3 . Podemos inferir que el polinoC C C mio torre de un tablero formado por una la o una columna de casillas es 2 Figura 3: Tableros Pequeños . 4 porque hay cuatro formas de colocar 1 torre y dos formas de colocar 2 torres 2 . Hallar en 4 . Claramente, 5 6 es algo más complicado. Parahallar 2 elegimos las dos columnas donde se colocaran las dos torres (hay 32 formas de hacerlo) y cualquiera haya sido la forma elegida hay 3 2 maneras de elegir las las donde se colocaran. Finalmente se colocan las dos torres en las las y columnas elegidas y como esto es como colocar dos torres en 4 hay 2 formas de hacerlo. Por lo tanto hay 32 2 maneras de colocar dos torres en 6 . Finalmente veamos que 3 , Como hay exactamente tres columnas iguales y cada columna debe tener una torre podemos aplicar el principio fundamental con las tres operaciones colocar la ésima torre en la ésima columna. Para la primera tenemos 3 posibilidades, para la segunda tenemos sólo 2 porque no podemos usar la la en la que colocamos la primera torre y nalmente para la tercera torre tenemos una única posibilidad. Da un 2 3. total de maneras. Por lo tanto el polinomio torre de 6 es C
C
C
k
C
T (z; C ) = 1 + z
C
1
2
3
C
C
T (z; C ) = 1 + 2z
T (z; C ) =
1 + 3z
4
5
C
6
n
T (z; C ) = 1 + nz
C
T (z; C ) = 1 + 3z + z
T (z; C ) = 1 + 4z + 2z
T (z; C )
t
C
2
C
t
= 18
= 3!
i
i
3!
C
1+9z +18z +6z
Ejercicio 0.1 (a) Halle una fórmula para el número de maneras que hay de colocar torres en un tablero de sin casillas nulas. El tablero 1 de la Figura 4 es uno de tales tableros. (b) Repita el proceso si el tablero es de y el tablero tiene la mitad de las casillas nulas e intercaladas con las no nulas, como en el tablero de ajedrez. El tablero 2 de la Figura 4 es uno de 2 2 tales tableros (c) Qué tal si el tablero es de con impar, hay d n2 e o b n2 c casillas nulas y las casillas están intercaladas. n
2n
n
n
C
2n
C
n
n
n
0.1.
3
POLINOMIOS TORRES
Ejercicio 0.2 Halle el polinomio torre de los tableros de la Figura 4 Justi que
su respuesta.
C
C
1
C
2
3
Figura 4: Algunos Tableros
Ejercicio 0.3 Demuestre que los polinomios torres de los tableros sombreados de la Figura 0.1 son respectivamente
T (z; C2 ) = 1 + (2n + 1)z + [2
n
2
+
n
1
T (z; C1 ) = 1 + 2nz + 2
2 ]z
y
n
2
z
T (z; C3 ) + 1 + 3nz + 6
C
2
,
n
2
z
2 +6
3 z .
n
3
C
1
3
C
2
Figura 5: Tableros de columnas completas n
Ejercicio 0.4 Demuestre que el polinomio torre de un tablero no se altera si se le intercambia un par de las o de columnas.
Teorema 0.1 Si
es una casilla no nula del tablero , entonces donde ij es el tablero que resulta de anular la la y la columna en el tablero y cij es el tablero que resulta de anular la casilla ij . c
cij
C
T (z; Cij ) + zT (z; Cij ) j
C
Prueba: Sea
T (z; C ) =
C
i
C
c
1
el número de maneras de colocar torres en el tablero , en base al principio de adición, partimos las con guraciones que queremos contar en dos conjuntos disjuntos, a saber, los que usan a la casilla ij , esto es, se colocó una torre en ella, y los que no usan a la casilla ij . Si usan a la casilla ij , no se podrá colocar ninguna torre es las casillas que están en la misma la o columna que la casilla ij . Esto es equivalente a eliminar la ésima la y la ésima columna de . Hay tantas formas como n 1 ij . tn (C )
n
C
c
c
c
c
i
j
1
Nombrar para conquistar
C
t
(C
)
4 Si no se usa la casilla ij , hay que colocar las torres en el tablero original con la casilla ij borrada, esto es, hay n cij formas de hacerlo. Por consiguiente, c n n 1 ij n ij . Ahora bien, si multiplicamos en ambos lados por n y sumamos sobre todos los valores de , tomando en cuenta que n si 62 IN , se tiene que c
n
c
t
(C ) = t
t
(C
)+ t
(C
(C
)
)
z
n
t
= 0
n
1 X
tn (C )z
n
1 X
=
n=0
1 (Cij )z
tn
n=0
De donde se concluye que
n
1 X
+
c
tn (Cij )z
n
n=0
2
c
T (z; C ) = zT (z; Cij ) + T (z; Cij )
De nición 0.2 (Subtableros Disjuntos) Dos subtableros blero son disjuntos si y sólo si líneas. C
y
C1
C2
1 y 2 de un tano tienen casillas en las mismas C
C
El en la Figura 6 el tablero 1 está formado por dos subtableros disjuntos pero en el tablero 2 no contiene subtableros disjuntos. C
c
C1
C2
Figura 6: Tableros Disjuntos
Teorema 0.2 Si el tablero está formado por dos tableros disjuntos 1 y 2, 1 2 , Prueba: Las formas de colocar torres en el tablero se pueden clasi car
entonces
C
T (z; C ) = T (z; C )
C
C
T (z; C )
n
C
disjuntamente en las que tienen torres en el subtablero 1 y las restantes en el subtablero 2. Si, por ejemplo, queremos contar aquellas que tienen torres en el subtablero 1 tenemos, en base al principio fundamental, que usar dos operaciones: 1) colocar torres en 1 y 2) colocar las restantes en 2 . Hay por lo tanto k 1 n k 2 . Note que debido a que los tableros son disjunto cualquiera haya sido la elección en la primera operación el número de maneras de efectuar la segunda operación es el mismo n k 2 . Luego, en base al principio de adición, se tiene que 0; 1; 2; : : : n
n; n
1; n
1; : : : ; 2; 1; 0
C
C
k
C
k
n
t
k
C
t (C )t
C
(C )
(C )
n X tn (C ) =
tk (C1 )tn
k (C2 )
.
k =0
y por consiguiente
T (z; C ) = T (z; C1 )
T (z; C2 )
2
0.1.
5
POLINOMIOS TORRES
Ejemplo 0.2 Use los teoremas 0.1 y 0.2 para hallar el polinomio torre del tablero
.
C =
Explicación: Basándonos en el teorema 0.1 y la casilla del tablero se puede expresar como sigue:
T (z;
) = T (z;
) + zT (z;
)
T (z;
) = T (z;
) + zT (z;
) + zT (z;
c13
el polinomio torre
)
Se expresa el polinomio torre del tablero en base al polinomio torre del tablero que resulta de eliminar la casilla 13 y del que resulta de eliminar la primera la y la tercera columna. El proceso se repite con nuevo tablero grande usando la casilla 23 . Como los últimos tableros tableros son disjuntos sus polinomios torres son fáciles de hallar usando el teorema 0.2. C
c
c
T (z; C )
2
2
2
=
(1 + 4z + 2z )(1 + 6z + 6z ) + 2z(1 + 2z)(1 + 4z + 2z )
=
1 + 12z + 44z
2
+ 56z
3
+ 20z
4
Ejercicio 0.5 Halle los polinomios torres de los tableros de la Figura 7
Figura 7: Para hallar el polinomio
Ejemplo 0.3 El jefe de producción de una planta productora de pinturas tiene que plani car la producción de cuatro lotes de pinturas 1 2 3 4 en cinco de sus tanques de fabricación 1 2 3 4 5 . Debido a que los tanques 4 y 5 se necesitan de nuevo después de mediodía para fabricar otros lotes y el lote 1 se lleva todo un día de trabajo, el lote 1 no se puede programar en el los tanques 4 ni 5 . El lote 2 no se puede fabricar en los tanques 3 ni 4 porque L ;L ;L ;L
T ;T ;T ;T ;T
T
T
L
L
T
T
L
T
T
6 necesita de un agitador que sólo está en los otros tres tanques. Los lotes 3 y 4 no pueden fabricarse en los tanques 1 y 2 por ser estos tanques muy pequeños. Determine de cuántas maneras puede el jefe de producción plani car la fabricación de estos cuatro lotes. L
L
T
T
Explicación: En la Figura 8 se muestra un tablero que tiene sombreadas las restricciones de producción.
Cada la corresponde a un lote y las casillas sombreadas en cada la inT T T T T dican que ese lote no se puede fabricar L usando dicho tanque. Una asignación L consiste en seleccionar o marcar en esL te tablero exactamente una casilla en L cada la de tal manera que haya a lo sumo una casilla marcada en cada columna. Esto es equivalente a colocar Figura 8: Tablero de Restricciones cuatro torres en el tablero que no se capturen mutuamente. Resolveremos el problema de dos formas diferentes. La primera forma consiste en hallar 4 en este tablero. Puesto que para colocar cuatro torres en las casillas blancas hay que colocar una en cada la dividamos el problema en tres tipos de asignaciones: aquellas en las cuales el lote 1 se asignó respectivamente a 1 , 2 o 3 . (Esto es, se colocó una torre en la la 1 y en la casilla de 1 , 2 o 3 respectivamente) Si colocamos una torre en la casilla 11 ya no podremos colocar torres C óC C en la la uno ni en la columna uno, por lo tanto eliminamos la la uno y la columna uno y obtenemos el tablero 11 de la Figura 9 en el cual debemos colocar las restantes 3 torres. Esto se puede hacer de 8 formas difeFigura 9: Subtableros rentes. Si colocamos una torre en la casilla 12 , después de eliminar la la 1 y la columna 2 nos queda el mismo tablero de la Figura 9 y por lo tanto hay otras 8 maneras de colocar las tres torres restantes. Finalmente si colocamos la primera torre en la casilla 13 nos queda el segundo tablero de la Figura 9 y en él hay sólo 4 formas de colocar las restantes tres torres. Por lo tanto hay un total de 20 formas de colocar cuatro torres en el tablero original. La otra manera de resolver el problema resulta muy interesante porque se usa el principio de inclusión exclusión y para calcular los i se halla el polinomio torre del tablero sombreado que por estar formado, en este caso, por dos tableros disjunto resulta fácil de calcular. 1
2
3
4
5
1 2 3 4
t
L
T
T
11
T
12
T
T
T
13
c
C
c
c
s
De nuevo queremos determinar el número de formas de colocar cuatro torres que no se capturen en el tablero de la Figura 9. Tomamos como como conjunto base el conjunto de formas de colocar las cuatro torres si todas las casillas fuesen válidas. Hay maneras de hacer esto porque la torree de la primera 5!
0.1.
7
POLINOMIOS TORRES
la la puedo colocar de formas diferentes, y una vez colocada, la segunda la podemos colocar en cualquiera de las cuatro que no se han usado, la tercera en cualquiera de las tres restantes, la cuarta en cualquiera de las dos restantes y por último la quinta tiene sólo una forma de colocarse. Las propiedades son: 1 : tiene la torre de la la 1 colocada en las columnas etiquetadas como 4 o 5 , esto es, el lote 1 de asigna al tanque 4 o al 5 . 2 : tiene la torre de la la 2 colocada en las columnas 3 o 4 . 3 : tiene la torre de la la 3 colocada en las columnas 1 o 2 . 4 : tiene la torre de la la 3 colocada en las columnas 1 o 2 . Para hallar 1 hay que elegir en que casilla se colocará la torre de la primera la: tenemos 2 posibilidades y después colocar las torres de las restantes las lo cual se hace de maneras diferentes, esto es, . 1 Como también se tiene que . Lo 2 3 4 1 interesante es que 8 es justamente el número de maneras de colocar una torre en el tablero sombreado. Lo mismo nos pasará con los otros coe cientes, por ello calcularemos el polinomio torre del tablero sombreado. Como el tablero sombreado está formado por dos subtableros disjuntos se obtiene que 5
p
T
T
T
T
T
T
T
T
T
T
p
p
p
N (p )
4!
N (p ) = 2
N (p ) = N (p ) = N (p ) = 2
T (z; C1 )
2
4!
s
2
T (z; c2 ) = (1 + 4z + 2z )(1 + 4z + 3z ) = 1 + 8z + 21z
Se concluye que N (p01 p02p03 p04 ) = N
8
4! + 21
3!
20
2! + 6
2
= 8
4!
4!
T (z; C ) =
+ 20z
3
1! = 20
+ 6z
4
Los coe cientes del polino-
Ejercicio 0.6 El departamento de computación de cierta universidad dispone de cinco profesores 1 2 5 para asignarles cinco cursos 1 5 , uno a cada uno. Los profesores sólo pueden o quieren dictar los cursos que se listan a continuación: 1 1 2 2 2 3 3 1 5 4 4 5 5 4 5 . ¾De cuántas maneras se puede hacer la asignación? P ;P ;:::;P
c ;:::;c
[P ; c ; c ]; [P ; c ; c ]; [P ; c ; c ]; [P ; c ; c ]; [P ; c ; c ]
Me gustas cuando callas porque estás como ausente, y me oyes desde lejos, y mi voz no te toca. Parece que los ojos se te hubieran volado y parece que un beso te cerrara la boca. Como todas las cosas están llenas de mi alma emerges de las cosas, llena del alma mía. Mariposa de sueño, te pareces a mi alma, y te pareces a la palabra melancolía. Me gustas cuando callas y estás como distante. Y estás como quejándote, mariposa en arrullo. Y me oyes desde lejos, y mi voz no te alcanza: déjame que me calle con el silencio tuyo. Déjame que te hable también con tu silencio claro como una lámpara, simple como un anillo. Eres como la noche, callada y constelada. tu silencio es de estrella, tan lejano y sencillo. Me gustas cuando callas porque estás como ausente. Distante y dolorosa como si hubieras muerto. Una palabra entonces, una sonrisa bastan. Y estoy alegre, alegre de que no sea cierto. Poema 15. Pablo Neruda.
ti
mio torre nos dan el número de maneras de elegir y colocar las torres elegidas mientras que los factoriales nos dan las formas de colocar las restantes torres. i