Imagina que tienes un 8x8 completamente blanco el campo de plazas en la pantalla. Ahora usted puede hacer clic en cualquier plaza. Al hacer esto, todas las casillas de la columna y la línea (incluyendo el que se hace clic en él) va a cambiar su color (si es blanco es negro y viceversa). Cuántos pasos al menos se necesitaría para crear un estándar de tablero de ajedrez? Traté de hacerlo de forma manual, pero lo tengo muy complicado y he perdido la cuenta de la situación. Pero si yo pudiera decirle a mi problema a Mathematica que podría ser muy fácil. Es allí una manera de escribir un código para calcular esto? O incluso una fórmula para hacer esto manualmente sin ningún tipo de programa?
Respuestas
¿Demasiados anuncios?
Dominik
Puntos
7739
MPeti
Puntos
231
Una prueba válida sin matemáticas avanzadas:
Ninguna célula debe ser pulsado más de una vez.
Haciendo clic en algún lugar de dos veces, usted acaba de revertir los cambios. Puesto que el orden de los clics no hacer una diferencia, esto es, incluso si usted hace otras clics entre estos. Tan sólo necesitamos considerar uno o cero hace clic en cada celda.
El número de clics fuera de cada fila/columna debe ser par.
Si hay un número impar de clics fuera de una fila determinada, el número de células cambiado en esa fila sería extraño, que conduce a un número impar de casillas negras allí. (Hace clic en la fila que no afectan a este, ya que el cambio de todas las celdas de esa fila).
El número de clics en total debe ser par.
Cada uno de los cambios de fila 15 células, de modo que un número impar de clics en total llevaría a un número impar de cambios de color, lo que resulta en un número impar de casillas negras en el tablero. (gracias user21820)
El número de clics en el interior de cada fila/columna debe ser par.
Restar el número de clics que fuera una fila (un número) del número total de clics (otro número). El resultado será incluso.
Una celda cambiará en la final si y sólo si se ha hecho clic.
Buscar en una fila. Los clics en la fila de salir de sus celdas sin cambios, ya que hay un número par de ellos. El que las células son modificados por los clics en otras filas? Podemos utilizar el hecho de que debe haber un número par de clics en cada columna, así que contar.
Mira las celdas de la fila:
- Si se hace clic, ahora hay un solo clic en su columna. No tiene que ser un número impar más en otras filas. Estos son los clics fuera de la fila que cambiar esta celda. Dado que hay un número impar de ellos, la célula será cambiado en la final.
- Si no hace clic, no tiene que ser un número par de clics en otros lugares en la columna. Esto significa que la hace clic fuera de la fila también salir de la celda sin cambios.
La solución óptima es de 32 clics.
Hemos demostrado que necesitamos haga clic en todas las celdas que queremos cambiar para obtener un tablero de ajedrez para colorear. Hay 32 de estos, así que lo mejor que podemos hacer. De hecho, ese es el único número de movimientos que puede conducir a un tablero de ajedrez para colorear si no lo hacemos clic en cualquier celda dos veces.
Cerber
Puntos
330
Tenga en cuenta que en la partida de la junta, supone todo blanco sin falta de generalidad, hay 32 plazas de color correctamente. Entonces uno puede trivial comprobar que después de un solo clic en cualquier cuadrado de esta partida de la junta hay 33 o 32 + 1, plazas de color correctamente.
Vamos a analizar que primero se mueve más cerca. Se realiza la inversión de la precisión de 15 plazas: la plaza de clic; los otros siete en su fila; y los otros siete en su columna.
Para llegar a un tablero de ajedrez de la original todo en blanco bordo de la final cuadrados blancos debe haber sido intercambiado un número par de veces, y los cuadrados de color negro debe haber sido intercambiado un número impar de veces. Es trivial comprobar que al hacer clic una vez en cada cuadrado negro, en cualquier orden, un tablero de ajedrez. Tenemos que demostrar que este es mínimo.
Este 32-mover solución a cabo 32 * (7+7+1) = 32 * 15 = 480 el color de los swaps de un cuadrado. Nota, además, que un solo clic, sólo puede posiblemente llegar a 7 cuadrados negros (al hacer clic en un cuadrado negro) o 8 cuadrados negros (al hacer clic en un cuadrado blanco). Por lo tanto para cubrir todos los cuadrados negros requiere un mínimo de 8 clics (Un clic es necesario en cada una de las 8 filas, así como en cada una de las 8 columnas).
Cualquier conjunto de 8 clics llevará a cabo de 8 * 15 = 120 color swaps. Cualquier selección de 8 clics que cubre todos los cuadrados negros se han intercambiado todos los cuadrados en el tablero dos veces, excepto el 8 plazas clic que se han intercambiado una sola vez. Por supuesto 64 + 64 - 8 = 120 como se señaló anteriormente. Por lo tanto, sólo 8 plazas (net) han cambiado de color.
Otros cuatro patrones, pueden también intercambio neto de 8 plazas cada uno.
Mediante la composición de cuatro adecuados patrones de podemos, finalmente, cubierta de una red de 32 color swaps, pero este es nuestro ya descubrió posible solución; por lo que es posible y mínima. Esto se basa en la conmutatividad de clic, que es trivialmente probado.
Esta prueba no tiene todo el rigor que me gustaría, pero debería ser suficiente para guiar a alguien a una rigurosa prueba.
Desde que le había pedido a esta primera en Mathematica sitio. He hecho un pequeño programa en el que usted puede jugar para ver las variaciones de forma gráfica.
Ejecutar el código en Mathematica y se genera la dinámica de la cuadrícula se muestra a continuación.
chess = Table[0, {i, 1, 8}, {j, 1, 8}]
toggle[m_] := Which[m === 1, 0, m === 0, 1];
click[m_, n_] := Module[{},
Table[chess[[m, j]] = toggle[chess[[m, j]]], {j, 1, 8}];
Table[chess[[j, n]] = toggle[chess[[j, n]]], {j, 1, 8}];
chess[[m, n]] = toggle[chess[[m, n]]];
]
Row[{Column[{Button["Reset", chess = Table[0, {i, 1, 8}, {j, 1, 8}]],
Grid@Array[Button[{#1, #2}, click[#1, #2]] &, {8, 8}]}],
Dynamic[ArrayPlot[chess, Mesh -> True, ImageSize -> 300]]}]
Puede hacer clic en los elementos para ver el cambio.
