Cómo puedo probar que dominó por lo menos 8 es necesario para permitir una colocación que no domino adicional puede agregarse sin dos fichas compartiendo un borde
Cualquier ayuda será apreciada.
Editar: para la rejilla de 9 9 esta es la mejor solución:[](https://i.stack.imgur.com/Xdvni.png)
Lo que parecía una simple pregunta en la primera se convirtió en un desafío de programación. Sí, 8 fichas de dominó están obligados a ordenar borde-a-borde de contactos con más fichas de dominó, pero mi eventual enfoque era algo extraño...
En lugar de pensar acerca de los cuadrados de la cuadrícula, pensar en los bordes entre los cuadrados, de los cuales hay $2×8×7=112$. Ahora mira a un domino:
A la izquierda, el domino de sí mismo es en un azul profundo. Un nuevo domino hace de borde-a-borde de contacto o se superpone a la original de domino de la fib el nuevo domino se superpone una luz azul de la plaza de la fib el borde entre el nuevo domino dos plazas coincide con alguno de los cortos de color púrpura de los segmentos de línea. Este conjunto de más de 23 bordes me referiré como el original domino de la zona (si es cerca de la junta del borde, en algunos tramos puede estar fuera de la junta o de la caída en la junta de contorno; no consideramos que dichos bordes).
El problema de la colocación de fichas de dominó con el mandato de borde-a-borde de contactos – un dominante cubre – ahora se convierte en un problema de cubrir todos 112 los bordes por el domino de las zonas. Si el borde no se encuentran en cualquier zona, puede servir como el centro del borde de un nuevo domino, sin borde de contacto.
Ahora considere las configuraciones de las zonas que cubren las dos aristas incidentes en una esquina de la plaza. Hay cinco diferentes configuraciones viables a la reflexión, que voy a llamar de tipo 1 a tipo 5 de izquierda a derecha:
Los dos tachado configuraciones no son viables, ya que pueden ser sustituidos por las configuraciones inmediatamente debajo de ellos sin el descubrimiento de los cubiertos los bordes. Cualquier dominando cubriendo las necesidades cuatro de estas configuraciones, una para cada esquina.
Podemos muy fácilmente demostrar que sólo se puede utilizar en más de una instancia del tipo 4 y tipo 5 configuraciones combinadas. Ninguna de las configuraciones cubre los siguientes cantos:
Además, al menos dos zonas están obligados a cubrir estos bordes, lo que significa que de la esquina de las configuraciones puede utilizar en la mayoría de las cinco zonas.
El último paso es probar que ninguna de las combinaciones de esquina configuraciones con cinco y cuatro zonas se extienden a una completa dominante que cubren el 7 de fichas de dominó. Para ello me dirigí a la computadora, fuerza bruta, para cada combinación de esquina configuraciones y el resto de domino zonas para mostrar que cada uno de ellos, no podían cubrir todos 112 los bordes, en una forma que recuerda una de las hojas de Zygalski. El (Python + NumPy) código puede ser encontrado aquí. Brevemente, he eliminado tipo 5 de la consideración primera, mostrando que no domina cubriendo podría usarlo. Luego hice lo mismo con los tipos 4, 1, 2 y, finalmente, 3, probando la no existencia de 7-domino dominando los cubrimientos de las 8×8 de la junta.
Sin embargo, existen cerca-dominando las cubiertas que cubren 111 de 112 bordes (dejando exactamente un lugar para un nuevo domino sin hacer borde de contacto). Aquí hay uno:
El SVG fuente de las imágenes en esta respuesta se puede encontrar aquí.
Respuesta parcial sólo...
Nomenclatura: vamos a llamar a la configuración inicial de las fichas de dominó los "bloqueadores". Ellos colectivamente hacen que sea imposible colocar un "invasor" domino sin el invasor compartir un borde con algún bloqueador. El OP pide una prueba de que $N=8$ bloqueadores son necesarios en un $8 \times 8$ junta. Mi respuesta demuestra un menor resultado:
Si los bloqueantes no se les permite tocar los bordes del tablero, a continuación, $N=8$ son necesarias y suficientes.
Suficiencia:
8 . . . . . . . .
7 . x . x . x x .
6 . x . x . . . .
5 . . . . . x x .
4 . x x . . . . .
3 . . . . x . x .
2 . x x . x . x .
1 . . . . . . . .
a b c d e f g h
Necesidad:
Desde los bloqueadores no se les permite tocar cualquier borde de la placa (en mi versión), algunos bloqueador debe ocupar b2 con el fin de evitar un invasor en la a12. Del mismo modo bloqueadores deben ocupar b7, g2 y g7. Estos 4 bloqueadores, no importa cómo cada uno está orientado, dejará de1, de8, a45, h45 como 4 posibles ubicaciones para el invasor. Vamos a necesitar un extra de bloqueador para eliminar cada uno de estos 4 posibles invasores lugares. Por lo tanto 8 bloqueadores son necesarios.
Más ideas: Como se ha mencionado, esta prueba es incompleta. Traté de demostrar que permite bloqueadores de tocar los bordes del tablero (como en el OP solución de la muestra) no se puede realizar el bloqueo de la tarea más FÁCIL (es decir,$N < 8$), pero sin éxito... transformaciones Simples no parecen funcionar. E. g. en el OP solución, los bloqueadores en la a34 y cd1 colectivamente evitar que cualquier intruso en a1, y no podemos mover bloqueador fuera del borde de la placa sin toda una serie de otros movimientos.
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.
%5D(https://i.stack.imgur.com/Xdvni.png){kind=link}
