21 votos

Demuestra que si se colocan 33 torres en un tablero de ajedrez, al menos cinco no se atacan entre sí

La pregunta pide que se demuestre que cuando se colocan 33 torres en un $8 \times 8$ tablero de ajedrez que hay un total de 5 torres que no se atacan entre sí.

Lo que sé:

  1. 64 casillas
  2. Los grajos atacan en línea recta
  3. al menos 1 fila debe tener más de 5 torres
  4. al menos 1 columna debe tener más de 5 torres

He montado un tablero de ajedrez vacío y he escogido al azar una fila y un lugar de 5 y una columna que contenía cinco y descubrí que, independientemente de dónde los coloque, una diagonal en forma de X tendrá cuatro torres en ella. Así que conté todos los huecos en los que tendría que haber una torre colocada para completar la diagonal de 5 y me salieron 12. Pero no sé cómo usar eso.

Entiendo que el concepto que funciona a través de las diagonales y que 32 es el número máximo que se puede colocar en un tablero de ajedrez con sólo tener 4 en cada diagonal. En el momento que colocas la 33 haces que al menos una diaganol tenga 5 en ella. Haciendo que los 5 no se ataquen entre sí.

Pero no sé cómo escribir eso en forma de prueba. El profesor me dijo que usara el principio de la paloma, pero no estoy seguro de qué es la paloma y qué es el agujero.

1 votos

Este problema me resultaba familiar.. "Estrategias de resolución de problemas", 4. El principio de la caja, problemas, 74: Se colocan 33 torres en un tablero de ajedrez de 8x8. Demuestre que puede elegir cinco de ellas que no se ataquen entre sí.

0 votos

El problema está mal planteado aquí, aunque esto tiene poco efecto en la solución prevista. Dejando de lado la sutileza de que en el ajedrez las piezas sólo pueden atacarse entre sí si pertenecen a bandos opuestos (las piezas del mismo bando pueden defender entre sí; así que incluso con sólo 9 torres habría 5 del mismo bando, por lo tanto mutuamente no atacantes), las reglas del ajedrez no permiten que las torres salten sobre las casillas ocupadas, así que con un tablero tan lleno, puede haber fácilmente familias de torres no atacantes de las cuales algunas comparten una fila o un archivo.

30voto

DiGi Puntos 1925

Mira las diagonales extendidas, que he numerado desde $1$ a través de $8$ en el diagrama siguiente:

$$\begin{array}{|c|c|c|c|c|c|c|c|} \hline 1&2&3&4&5&6&7&8\\ \hline 2&3&4&5&6&7&8&1\\ \hline 3&4&5&6&7&8&1&2\\ \hline 4&5&6&7&8&1&2&3\\ \hline 5&6&7&8&1&2&3&4\\ \hline 6&7&8&1&2&3&4&5\\ \hline 7&8&1&2&3&4&5&6\\ \hline 8&1&2&3&4&5&6&7\\ \hline \end{array}$$

Hay ocho, cada una de las cuales comprende ocho casillas, por lo que una de ellas debe contener al menos cinco de las torres.

1 votos

¡Muchas gracias! Yo estaba intentando esta idea similar, pero estaba usando las filas horizontales o verticales y tratando de numerarlas. ¡Después de todo el tiempo que me centré en las diagonales no sé por qué no hice eso! ¡Gracias!

0 votos

@Jerry: ¡De nada!

1 votos

¡Qué argumento tan bonito! Me ha alegrado este día tan sombrío.

4voto

Jake Puntos 118

Supongo que el problema aquí es demostrar que la afirmación es cierta independientemente de su disposición.

Tus puntos sobre las reglas son correctos, pero primero te corregiría que en un tablero de ajedrez se podrían colocar 32 piezas con sólo cuatro en cualquier fila o hilera (colocando todas las piezas en las casillas blancas o en todas las casillas negras), por lo que al colocar la pieza 33, una fila y una columna deben tener "cinco o más", no "más de cinco".

Para ser pedante, una pieza que puede capturar a otra en su turno no está "atacando", está "amenazando". Y hay una regla más a tener en cuenta, sólo para ser dolorosamente obvio: una torre no puede moverse "a través" de otra pieza para capturar una pieza más allá de ella. Parece que has pasado esto por alto, porque parece que estás obsesionado con mantener las torres en las diagonales.

Eso nos lleva a una posible prueba: como una fila debe tener cinco o más torres sin importar su colocación, y una columna debe tener cinco o más torres sin importar su colocación, entonces hay tres torres en la fila de cinco y tres torres en esa columna de cinco que están separadas por al menos otra torre entre sí. En el peor de los casos, dos de estas torres son la misma (la 33ª torre) y, por tanto, dada una cuadrícula de torres colocadas sólo en las casillas negras, al colocar la 33ª torre en cualquier fila o columna, se identifican tres en una fila y dos torres adicionales en una columna que no pueden tocarse.

En realidad parece una estimación extremadamente baja, porque si se colocan 32 torres en todos los espacios negros, hay una diagonal de 8 que no se amenazan entre sí. Así que, imaginemos el peor de los casos:

Cualquier torre amenaza a un máximo de otras cuatro piezas, que son las cuatro situadas más cerca de ella en la misma fila o columna. Esas mismas 4 torres son las únicas que amenazan a la torre original. Las otras 28 torres están en una fila y columna diferentes, o están separadas de la torre en cuestión por una o más torres. Así que, literalmente hablando, una torre cualquiera sería "neutral" (no amenazaría ni sería amenazada por) al menos con otras 28 piezas, y hasta 30 (para una pieza en una esquina), y cada una de ellas sería un par de torres que no se atacan entre sí. De esas 28, cada una de ellas sólo puede atacar a otras cuatro como máximo, por lo que el número de parejas de torres no amenazantes es al menos el número de combinaciones de 29 cosas tomadas de 2 en 2, que es camino más de cinco (406 de hecho).

Así, dada una torre inicial, no hay más de 4 que puedan atacarle y no menos de 28 que no. Escojamos el peor caso de las 28 restantes; una torre amenazada por cuatro torres completamente diferentes a las que amenazan a la primera. Hay cuatro torres que amenazan a esta torre como acabo de decir, así que de 33 torres tenemos dos que simplemente no pueden atacarse porque hay una torre en cada lado, y hemos eliminado 8 más como posibilidades porque amenazan a una de estas dos torres que hemos identificado. Hay 23 torres más entre las que elegir; continuemos nuestro patrón y elijamos otra torre amenazada por otras cuatro, así que tenemos tres torres que no pueden atacarse entre sí y quedan 18. Dos repeticiones más de esto y tienes un grupo de cinco torres que no se amenazan entre sí (porque cada una está amenazada por cuatro torres únicas que definitivamente no son ninguna otra torre del grupo), 20 más que amenazan a una y sólo una torre de esas cinco (y por tanto no pueden formar parte del grupo), y tienes todavía tienen 8 torres adicionales que no podrían amenazar ni ser amenazadas por ninguna de las cinco que ya hemos identificado.

Ese es el peor caso; básicamente cinco grupos de cinco torres cada uno en forma de cruz, con otras ocho torres colocadas arbitrariamente, y estamos eligiendo las cinco torres que están amenazadas por la mayor cantidad de otras torres, y así eliminamos la mayor cantidad de posibilidades para otros miembros de este grupo. Tenemos más que suficientes torres adicionales para repetir este motivo cruzado una vez más (y hay algunas permutaciones de colocación que permiten que seis de estas formaciones cruzadas quepan en un tablero de 8x8), así que de hecho podemos identificar 6 piezas de 30, en el peor de los casos, que no pueden amenazarse entre sí porque cada una de ellas ya está amenazada por otras cuatro torres únicas.

Además, la pieza 31, no importa dónde la coloques, no puede amenazar a ninguna de las seis que hemos identificado y viceversa (aunque esta pieza está ahora amenazada por al menos una torre de las que amenazan a las otras 6), así que de hecho es posible identificar un grupo de al menos siete torres de estas 33, en cualquier permutación de colocaciones, que no amenacen a ninguna otra torre del grupo.

La pieza 32 puede amenazar trivialmente a la 31; sin embargo, la última colocada, la 33, no puede formar ninguna formación en la que las piezas 31, 32 y 33 todo se amenazan entre sí; dos de ellas serán mutuamente no amenazantes, y como hemos establecido, no pueden amenazar a las 6 centrales cruzadas, por lo que hay, al menos, 8 torres en cualquier formación de 33 que no pueden amenazar a ninguna otra torre de ese grupo.

0voto

znq Puntos 101

He aquí una idea: si tomas una fila con cinco o más torres en ella (cal esta fila $r_1$ ), las torres primera, tercera y quinta no se atacan entre sí porque hay otras torres entre ellas. Sabemos que esa fila tiene que existir por el principio de encasillamiento ( $\lceil \frac{33}{8} \rceil = 5$ ).

Así que ahora todo lo que tienes que hacer es encontrar dos torres que no ataquen a ninguna de estas tres. Si alguna de las columnas en las que están estas torres tiene cuatro o más torres adicionales, podemos aplicar el mismo argumento a la columna para obtener dos torres más que no ataquen a ninguna de las otras, y ya está.

Por lo tanto, supongamos que cada una de las columnas que contiene una de las torres iniciales tiene como máximo otras tres torres en ella. Eso significa que de las 33 torres con las que empezamos, quedan 33 - 5 - 15 = 13 torres por colocar, y hay cinco columnas donde podrían ir. De nuevo, el encasillamiento ( $\lceil \frac{13}{5}\rceil = 4$ ) nos dice que una de estas columnas debe tener al menos tres torres en ella, y la primera y la última torre de la columna no se atacan entre sí. Así que ahora tenemos nuestras cinco torres: las tres de la fila con la que empezamos, más dos en una columna disjunta de cualquiera de las columnas que contienen las torres iniciales.

Espero que esto ayude.

0 votos

Buen intento, pero el argumento no es correcto. Ciertamente, no todas las torres que quedan al eliminar la fila inicial tienen que estar en una de las cinco columnas que has señalado. El resto, ni siquiera puedo seguirlo (¿dónde está el valor $27$ utilizado).

0 votos

@MarcvanLeeuwen Ups, tienes razón: ese argumento original no funcionaba. Lo he corregido con un argumento más matizado y creo que las matemáticas siguen cuadrando en este caso.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X