Plaza del juego de mesa con la superposición de la plaza de sub-partes

Question

Dos jugadores, a y B juegan un juego sobre un tablero con $NxN$ plazas. El jugador a se rellena todas las casillas con números del 1 al $N^2$ en una forma completamente aleatoria. Aquí está un ejemplo de un tablero de 5x5:

El jugador B no ve a la junta, pero puede pedir a Un jugador para decirle el contenido de cualquier parte cuadrada de la junta. Dos de los cuadrados de las partes (con el rojo y el verde marco) se muestra aquí:

El jugador a tiene que informar de los números en el cuadrado de la parte, pero él no tiene que informar de ellos en ningún orden en particular. Por ejemplo, para la parte roja de la junta de que él pudiera responder con: 23, 21, 12, 4, 14, 10, 5, 22, 25. Y para la parte verde podía contestar con: 15, 21, 11, 1.

Cómo muchas de las preguntas que el jugador B tiene a pedir antes de que él es capaz de reconstruir completamente el contenido de la junta?

Obviamente, él puede hacerlo pidiendo un contenido de cada uno de 1x1 plaza de la junta. Así que en el peor de los casos no tiene que pedir más de $N^2-1$ preguntas. Pero con una mejor estrategia que el número puede reducirse en gran medida.

Answer 1

Deje $f(N)$ el número de consultas utilizado por una estrategia óptima para resolver el $N\times N$ junta.

La reclamación. $f(N)\ge 2(N-1).$

Prueba. Considere la posibilidad de la $4(N-1)$ líneas de demarcación entre los campos consecutivos en la siguiente lista: $(1,1)$, $(2,1)$, $(3,1),\ldots, (N,1)$, $(N,2)$, $(N,3),\ldots, (N,N)$, $(N-1,N)$, $(N-2,N),\ldots, (1,N)$, $(1,N-1)\ldots,(1,2)$, $(1,1)$. Estas son las $4(N-1)$ "extremos" de la $N-1$ vertical y $N-1$ líneas horizontales de la cuadrícula que separa la placa en los campos. El fin de distinguir los campos separados por un "final", no debe ser una consulta que separa estos campos, es decir, que tiene este extremo, como parte de su perímetro. Una plaza en forma de consulta de lado de longitud $\le N-1$ puede cubrir en más de dos de estos extremos. Por lo tanto necesitamos, al menos, $2(N-1)$ consultas. $\square$

La combinación de esta límites inferiores con las estrategias en bof's respuesta, lo que demuestra que $f(N)\le 2N-2$ por extraño $N$ $f(N)\le 2N-1$ incluso $N$, vemos que $$f(N)=2N-2\qquad \text{if $N$ is odd.}$$

$$2N-2\le f(N)\le 2N-1\qquad \text{if $N$ is even.}$$

Se sospecha que en este caso el valor más alto es correcta; después de todo, mi argumento para el límite inferior hace que, posiblemente, no es suficiente el hecho de que al menos tres de las cuatro esquinas de los campos deben ser cubiertos por la consulta. En otras palabras, me atrevo a

Conjetura. $f(N)=2N-1-(N\bmod 2)$.

Algunas observaciones en apoyo de esta hipótesis: Si $N$ es par, entonces borde de la junta ha $N-1$ "extremos", un número impar. Si hay una solución con $2N-2$ de las consultas, cada final es cubierto exactamente una vez. Una consulta que cubre una esquina del campo se lleva a un extremo de la junta adyacentes bordes, mientras que la consulta sin un rincón de campo puede tomar los dos extremos de una arista, pero no cambia las paridades. Llegamos a la conclusión de que para cada borde de la placa, uno de los adyacentes esquina campos está cubierto por un número impar de consultas y la otra por un número par de consultas. Esto hace dos extrañamente y dos uniformemente cubierto esquina campos. Si ambos uniformemente cubierto esquina campos no están cubiertos en todo, no podemos distinguirlos. Por lo tanto, una de las esquinas del campo debe ser cubierto por al menos dos consultas. Mi intuición me dice que este es un derroche, apoyando la conjetura.

Answer 2

Para $N=2k+1$ hay una solución con $4k$ preguntas.

Deje $x_1,\dots,x_{N^2}$ ser el conjunto de todos los $1\times1$ plazas, y deje $S_1,\dots,S_{4k}$ todos los $(k+1)\times(k+1)$ plazas que toque el borde de la junta. Es fácil ver que, si $x$ $y$ son dos diferentes $1\times1$ cuadrados, hay algunos $S_i$ que contiene sólo uno de ellos. En otras palabras, el mapa de $x\mapsto\{S_i:x\subset S_i\}$ es una inyección de $\{x_1,\dots,x_{N^2}\}$ $\mathcal P(\{S_1,\dots,S_{4k}\}).$por lo Tanto, preguntando por el contenido de cada una de las plazas $S_1,\dots,S_{4k}$ nos permitirá reconstruir la junta.

Si $N=2k$ hay una solución con $4k-1$ preguntas, es decir, se hace uso de toda la $k\times k$ plazas que toque el borde de la junta directiva, a excepción de una esquina de la plaza.