Un juego con fichas

Question

Alice pone fichas en algunas células de un a $8 \times 8$ junta :

• Hay al menos un corrector en cualquier $1\times 2$ o $2\times 1$ rectángulo.
• Hay al menos dos adyacentes fichas en cualquier $7\times 1$ o $1\times 7$ rectángulo.

Encontrar la menor cantidad de fichas cumplan estas condiciones.

Answer 1

El óptimo es $37$ a las damas.

Aquí es una solución de con $37$ fichas:

$\begin{array}{ccccccccc} -&O&O&-&O&-&O&-\\ O&-&O&O&-&O&-&O\\ -&O&-&O&O&-&O&-\\ O&-&O&-&O&O&-&O\\ O&O&-&O&-&O&O&-\\ -&O&O&-&O&-&O&O\\ O&-&O&O&-&O&-&O\\ -&O&-&O&O&-&O&-\\ \end{array}$

Ahora para la prueba de optimalidad: es fácil ver que cada línea o columna debe tener al menos $4$ a las damas. Por otra parte, sólo hay tres patrones que lograr esto, ellos son $-O-OO-O-$, $-OO-O-O-$, y $-O-O-OO-$. Dos de estos patrones puede ser de dos columnas consecutivas, porque de la primera línea que violaría la condición de $1$. En particular, tenemos a más de cuatro $4$-fichas de las columnas.

Si tenemos en más de tres $4$verificadores de columnas, entonces tenemos al menos $3\cdot 4+5\cdot 5=37$ damas, así que estamos bien.

Ahora nos fijamos en los patrones posibles de cuatro $4$-fichas de las columnas. Si se alternan, la primera línea de cada espacio en blanco, lo que infringe la condición de $2$. Lo que significa que se deje de dos columnas entre dos de ellos. Nos fijamos en el patrón en estas dos columnas. La primera y la última línea debe ser $OO$ para cumplir con la condición de $2$. Entonces tenemos un $2\times 6$ cuadrícula para llenar. Necesitamos al menos $6$ fichas para hacerlo en un tablero de ajedrez manera, pero esto no es suficiente, porque un tablero de ajedrez se viola la condición de $2$ dos $1\times 7$ columnas, por lo que necesitamos al menos $7$ fichas en esta $2\times 6$ cuadrícula, bringin el total de al menos $37=4\cdot 4+2\cdot 5+ 4+7$.

Esto concluye la prueba de que $37$ es óptimo.

Answer 2

para satisfacer la condición 1. cualquier columna debe tener 4 fichas, pero para cumplir con la condición 2, debe haber cinco fichas si la columna tiene una ficha en la final. Desde la repetición de este patrón es extraño, yo.e si dicen 00-0-0-0 es seleccionado para la columna 1 y la vuelta ciclista, yo.e c2 = -00-0-0- a continuación, colum 8 será un ser igual a la columna 1, ( ya que cambiar el patrón en algún punto de dividir el doble alrededor de pos 1 y pos 8, que no es válido). por lo tanto, hay 5 columnas de 5 y 3 columnas de 4, dando 37 damas.

No mucho la prueba, los involucrados, pero no estás seguro de dónde ir de allí.