hitcounter

Sospechosos Habituales

Hace mucho tiempo en la inhóspita blogosfera una panda de frikis creó Sospechosos Habituales. Desde aquel fatídico día nadie está libre de sospecha. No trates de disimular, si vienes mucho por aquí tu también serás un... Sospechoso Habitual


Problema matemático del día: N torres y N damas


He aquí una nueva entrega del "Problema matemático del día". En esta ocasión, no me he basado en el Calendario matemático, sinó en un par de ejercicios de práctica que tuve que hacer el primer año de carrera (la asignatura era informática).

Son dos problemas, pero pueden juntarse en uno solo. Dado que es un problema difícil, os dejo todo el fin de semana antes de postear el siguiente.

Sin más preámbulos, os dejo con el problema N torres y N reinas.

En un tablero de ajedrez de tamaño estándar (un cuadrado de 8 casillas de lado), ¿de cuántas formas distintas podemos colocar 8 torres de forma que al menos dos de ellas se amenacen entre sí? (*)

Dado un tablero de ajedrez estándar (de 8 casillas de lado, como el del problema anterior), ¿de cuántas formas podemos colocar 8 damas que no se amenacen entre sí? (**)

Bonus:¿Podéis generalizar los dos resultados anteriores para un tablero de NxN casillas, con N piezas, siendo N un número entero positivo?


En ajedrez, se dice que una pieza amenaza a otra cuando en el turno del jugador que la controla, puede "comerse" a la pieza amenazada con el movimiento de la suya propia. Para comerse a una pieza, basta con colocarse en la misma casilla que el objetivo al mover.

(*)Las torres sólo pueden moverse en horizontal o vertical, sobre el tablero. Puede moverse tantas casillas en línea recta como desee, y no puede girar en un mismo movimiento (deberá esperar al siguiente turno). Por lo tanto, sólo puede amenazar a piezas que estén sobre su misma vertical u horizontal.

(**)Las damas pueden moverse como las torres y como los álfiles. Es decir, pueden moverse en horizontal, vertical o diagonal sobre el tablero. Al igual que la torre, puede moverse tantas casillas como desee, pero no puede cambiar de dirección en el mismo movimiento. Por consiguiente, sólo puede amenazar a piezas que estén sobre su misma horizontal, su misma vertical o sobre una de las dos diagonales que pasan sobre la casilla que ocupa.


Pistas:
1. Los dos problemas son bastante difíciles, en especial si hace tiempo que no se tocan las matemáticas. Hay que recordar que el resultado pedido es un número que se basa en contar formas de colocar piezas, con lo que es muy útil contar con algunas nociones sobre combinatoria.
2. La generalización es bastante sencilla en el caso de las torres, pero para las reinas no lo es tanto.
3. Para hallar el resultado en el caso de las torres, es mejor ir directos a por la generalización, pues contar el número de casos uno por uno puede ser demasiado lento (el resultado es del orden de 1.000.000.000).
4. En el caso de las damas, resulta más sencillo coger un tablero de ajedrez normal e ir haciendo combinaciones. El resultado es menor de 100.

Mucha suerte a todos.


Sospechoso: (Denúnciame)

Fichado el día 24 febrero 2006 a las: 18:50


  • Bueno, veo que en esta ocasión no ha habido respuestas al post. Supongo que me habré pasado tres pueblos con el problema ^^U Lo lamento.

    En fin, aquí os dejo las soluciones:

    8 torres: 4.426.165.368

    8 damas: 92

    No pongo las generalizaciones porque me serían imposibles de escribir correctamente aquí. Sin embargo, ambos casos pueden generalizarse.

    Por Blogger Unknown @ 28/2/06 9:46 p. m.  


  • Creo que el resultado para las ocho torres es incorrecto. El numero dado corresponde al numero binomial (64 8) que es el numero de formas de colocar ocho torres en un tablero. Pero a este numero se debe restar esas posiciones en que ninguna torre amenace a otra, que son exactamente 8!, por lo que el resultado debería ser

    (64 8) - 8! = 4.426.125.048

    Por Anonymous Anónimo @ 8/4/07 6:51 p. m.  


  • ¿Alguien podria explicar la generalización de N torres porfavor?, y lo del numero binomial (64 8)?
    Gracias

    Por Anonymous Anónimo @ 17/5/09 9:17 p. m.  


Publicar un comentario




« VOLVER