Un $n\cdot n$ cuadriculada problema?

Question

Pensé que de este problema cuando yo estaba jugando a un juego llamado BINGO con mi amigo. El juego básicamente es como este:

Supongamos $2$ personas que están jugando el juego(se puede jugar con cualquier número de personas, aunque). Ambos hacen un $5\cdot 5$ cuadrado de la cuadrícula y llenar los números de $1$ $25$en la cuadrícula al azar, es decir, usted puede llenar cualquiera de los números en cualquier lugar dentro de la cuadrícula. Así que cada uno tiene su propia red y no mostrar a los demás.

El primer jugador ahora llama a cualquier número entre el$1$$25$. El segundo jugador, a continuación, puede llamar a cualquiera de los restantes $24$ números. Los jugadores de llamar a los números de forma alternativa y mantener dando vueltas a los números de la cuadrícula. El primer jugador que consiga $5$ grupos de $5$ a través de los números de la fila, columna o diagonal (superposición de números permitidos) gana el juego. Bingo!

Así que el final de la cuadrícula puede ser algo como esto:

Ahora, este juego puede ser fácilmente extendido a $6\cdot 6$ o $7\cdot 7$ (usted puede llamar a este BAZINGA). En genreal $n\cdot n$ cuadrícula donde tienes que conseguir $n$ $n$ a través de los números de fila,columna o diagonal.

Por último, la pregunta es esta:

¿Cuál es el número mínimo de números que se utiliza para hacer que el grupo de números como lo requiere el juego. Para $5\cdot 5$ cuadrícula, al menos 17 entradas tienen que ser utilizados (como en la imagen de arriba). ¿Cómo puedo generalizar el resultado para $n\cdot n$ cuadrícula?

Creo que existe una relación recursiva. Aunque esto no me ayuda en ganar el juego, su solución es muy apreciado.

Answer 1

Depende de a $n$ ser par o impar así que vamos a tratar con estos por separado:

Impares:

El mínimo es como la forma en que has dibujado por $n=5$. Tenemos:

Las células de la primera $\frac{n-1}{2}$ líneas verticales: $\frac{n-1}{2} \times n$.

Adicional a las células a través de la primera $\frac{n-1}{2}$ líneas horizontales: $\frac{n-1}{2} \times \frac{n+1}{2}$.

Extra celdas de la diagonal: $1$.

Recapitulación: \begin{eqnarray*} \mbox{Total} &=& \frac{n-1}{2} \times n + \frac{n-1}{2} \times \frac{n+1}{2} + 1 \\ && \\ &=& \frac{n^2 - n}{2} + \frac{n^2-1}{4} + 1 \\ && \\ &=& \frac{1}{4} \left(3n^2 - 2n + 3\right) \end{eqnarray*}

Esto le da a $17$ al $n=5$, lo cual está de acuerdo con su respuesta.

Incluso:

El mínimo es con la primera $\frac{n}{2}$ cols, la primera $\frac{n}{2} - 1$ filas además de la diagonal (desde la esquina superior derecha). Tenemos:

Las células de la primera $\frac{n}{2}$ líneas verticales: $\frac{n}{2} \times n$.

Adicional a las células a través de la primera $\frac{n}{2} - 1$ líneas horizontales: $\frac{n}{2} - 1 \times \frac{n}{2}$.

Extra celdas de la diagonal: $1$.

Recapitulación: \begin{eqnarray*} \mbox{Total} &=& \frac{n}{2} \times n + \left(\frac{n}{2} - 1\right) \times \frac{n}{2} + 1 \\ && \\ &=& \frac{1}{2}n^2 + \frac{1}{4}n^2 - \frac{n}{2} + 1 \\ && \\ &=& \frac{1}{4} \left(3n^2 - 2n + 4\right) \end{eqnarray*}

Answer 2

Vamos a ver.

Para 2x2, la respuesta es 4; solo hay 6 líneas, y la colocación de tres sólo le da tres de ellos.

Para 3x3 la respuesta es, pienso, 7, dispuestos en forma de H de formación; en esta situación, puede cubrir ambas diagonales.

4x4 creo que es el primer lugar hemos de llegar a algo que se parece a la solución general, y se toma hasta las 12: dos filas y dos columnas, de tal manera que una de las diagonales es totalmente cubiertos.

de 5x5 y para arriba, usted tiene dos filas y dos columnas, y una de las diagonales, que ya has cubierto de 4 piezas con las filas y columnas. Así que eso es $2n + 2(n-2) + n-4 = 5n - 8$.

No puedo pensar en una mejor manera de hacer cuadros más grandes, así que supongo que es tu respuesta.

... espera, tengo que hacer el recuento de las dos diagonales método demasiado, vamos a ver cómo resulta.

---

Bueno hay tres métodos diferentes aquí. La primera es con ninguna de las diagonales. Consigue $5n - a(5-a)$ plazas, donde $a$ es el número de filas que de relleno. Esto le da al máximo, $5n - 6$.

El segundo, con una diagonal, el primer lugar de dos filas y dos columnas para maximizar el solapamiento entre las (si usted pone tres y uno, se obtiene sólo 3 se superponen en lugar de 4). A continuación, puede colocar la diagonal de modo que golpea a todos los cuatro filas/columnas en distintos lugares, con un total $5n - 8$.

La tercera, con ambas diagonales, tiene dos casos: $n$ impar, y $n$ incluso.

La principal diferencia entre ellos es que el $n$ aún no da ninguna superposición entre las diagonales, donde $n$ impar; esto reduce extraño $n$'s requisito 1. $2n$ o $2n - 1$ hasta la fecha.

A continuación, podemos elegir una fila para cubrir, siempre y cuando no podemos elegir el centro en $n$ impar, esto da $n - 2$ para la colocación de los que uno, por lo tanto, estamos en $3n - 2$ o $3n - 3$

Ahora tomamos dos columnas, de tal forma que impacten tanto en las diagonales y la línea elegida en diferentes lugares. Esto le da a $n - 3$ para cada uno, por $2n - 6$ para ambos, y $5n - 8$ o $5n - 9$ para los cinco.

Así que la respuesta correcta es: Se puede colocar 16 en una cuadrícula de 5x5 para recoger cinco líneas, y $5n - 8 - (1 \text{ if } n \text{ is odd})$ en general. Esto funciona en todo el camino hacia abajo para tamaño 4.