Sistema de representantes distintos y tableros de ajedrez

Question

Sistema de representantes distintos y tableros de ajedrez

embaldosado
tablero de ajedrez
Matemáticas
combinatoria
diseños combinatorios

t42d

Encontré el siguiente problema, que se presentó en el contexto del tema de SDR (sistema de representantes distintos): puedo resolver el problema, pero no uso un SDR, y me pregunto si alguien ve una solución. que aplica un DEG:

Supongamos que nos dan un $m \times n$ tablero de ajedrez, con $m$ incluso. siempre que tengamos $n \geq 2$ , demuestre que si eliminamos un cuadrado blanco y un cuadrado negro, todavía podemos teselar el tablero restante con fichas de dominó.

Tengo una forma razonablemente sencilla de resolver el problema (básicamente es suficiente asumir WLOG que las celdas eliminadas $\textit{define}$ el tablero de ajedrez, actuando como las esquinas superior izquierda e inferior derecha, y mostrando que esta cuadrícula resultante se puede colocar en mosaico) haciendo un pequeño análisis de caso, pero esto no hace uso de un SDR (que es el contexto en el que este se hizo la pregunta). No sé si hay o no una solución que involucre un SDR, pero si la hay, no puedo encontrarla. En particular, ni siquiera estoy seguro de cómo se podría definir un DEG en este contexto. Entonces mi pregunta es, ¿alguien puede ver cómo resolver este problema haciendo uso de la existencia de algunos SDR? Nuevamente, conozco una solución en general, pero no una que involucre un SDR. Se permite cualquier resultado relacionado con SDR (p. ej., condición de Hall). ¡Avíseme si tiene alguna idea sobre cómo se podría definir un SDR aquí!

bof

Por qué

n \geq 3

$n\ge3$ ? no es

n \geq 2

$n\ge2$ ¿suficiente?

t42d

Ah, tienes razón sobre

n \geq 2

$n \geq 2$ siendo suficiente, gracias, lo arreglaré. Con respecto al comentario anterior, la forma en que se plantea este problema, eliminando las esquinas superior izquierda e inferior derecha de un

8 \times 8

$8 \times 8$ tablero de ajedrez simplemente no es una opción legal aquí, ya que el problema requiere que eliminemos dos cuadrados de

opposite

$\textit{opposite}$ color. En particular, si dejamos

m^{'}

$m’$ y

n^{'}

$n’$ sean las dimensiones del (sub)-rectángulo definido al permitir que los mosaicos eliminados sean las esquinas superior izquierda e inferior derecha, entonces exactamente uno de

m^{'}

$m’$ y

n^{'}

$n’$ será incluso (wlog podemos decir que será

m^{'}

$m’$ ).

bof

Si

m, n \geq 2

$m,n\ge2$ y

m n

$mn$ es par, entonces una torre puede hacer un recorrido por el tablero y volver a su punto de partida, visitando cada casilla una sola vez. (En la jerga de la teoría de grafos, el gráfico que tiene los cuadrados del tablero de ajedrez como vértices, con dos cuadrados adyacentes si comparten un lado, tiene un ciclo hamiltoniano). Eliminar dos cuadrados de color opuesto divide el recorrido cerrado de la torre en dos caminos, cada uno que contiene un número par de cuadrados.

t42d

Wow, eso es significativamente más elegante que mi manera. ¡Gracias por la información!

Respuestas (1)

Sistema de representantes distintos y tableros de ajedrez

Ah, tienes razón sobre $n \geq 2$ siendo suficiente, gracias, lo arreglaré. Con respecto al comentario anterior, la forma en que se plantea este problema, eliminando las esquinas superior izquierda e inferior derecha de un $8 \times 8$ tablero de ajedrez simplemente no es una opción legal aquí, ya que el problema requiere que eliminemos dos cuadrados de $\textit{opposite}$ color. En particular, si dejamos $m’$ y $n’$ sean las dimensiones del (sub)-rectángulo definido al permitir que los mosaicos eliminados sean las esquinas superior izquierda e inferior derecha, entonces exactamente uno de $m’$ y $n’$ será incluso (wlog podemos decir que será $m’$ ).
Si $m,n\ge2$ y $mn$ es par, entonces una torre puede hacer un recorrido por el tablero y volver a su punto de partida, visitando cada casilla una sola vez. (En la jerga de la teoría de grafos, el gráfico que tiene los cuadrados del tablero de ajedrez como vértices, con dos cuadrados adyacentes si comparten un lado, tiene un ciclo hamiltoniano). Eliminar dos cuadrados de color opuesto divide el recorrido cerrado de la torre en dos caminos, cada uno que contiene un número par de cuadrados.
Wow, eso es significativamente más elegante que mi manera. ¡Gracias por la información!

Mike Earnest · Answer 1

Para cada cuadrado negro, considere el conjunto de cuadrados blancos que lo rodean. Un SDR para esta colección de conjuntos corresponde a un mosaico de dominó; elegir un cuadrado blanco $W$ del conjunto para un cuadrado negro, $B$ , significa que $B$ y $W$ están cubiertos por un dominó. Luego debe probar que la condición de Hall se cumple para esta colección de conjuntos, lo que significa que cada conjunto de $k$ los cuadrados negros comparten un borde con al menos $k$ cuadrados blancos distintos. No estoy seguro de si hay alguna forma de hacer esto que en algún momento no use la idea en su solución.

Ah ok ya veo. ¡Gracias! Continuamente había estado pensando que el SDR necesitaba representar realmente las fichas de dominó, en lugar de simplemente corresponder a las fichas de dominó, por lo que no es de extrañar que nunca encontrara el SDR.

Sistema de representantes distintos y tableros de ajedrez

t42d

bof

t42d

bof

t42d

Respuestas (1)

Mike Earnest

t42d

Rompecabezas: ¿Cortar tetraedro regular en tetraedros regulares de distintos tamaños?

¿Es posible colocar una reina y al menos 29 caballos en un tablero de ajedrez de 8x8 de modo que no haya 2 piezas que se ataquen entre sí?

Formas de colocar 3 piezas de ajedrez para que ninguna esté en la misma columna o fila

¿De cuántas maneras diferentes podemos colocar N torres idénticas en un tablero de ajedrez SIN ESQUINAS de modo que no se ataquen dos de ellas (para N > 3)?

Problema de independencia: una torre y número máximo de caballos en el tablero de ajedrez 8×88×88 \times 8

Número de formas de poner dos caballos diferentes en un tablero de ajedrez para que se ataquen entre sí

Elegir un comité de dos personas que no estén sentadas una al lado de la otra.

¿Cuál es el número máximo de guerreros que se pueden poner en un tablero de ajedrez para que no se ataquen dos guerreros?

Principio del casillero para n reinas

Simetrías de estructuras combinatorias.