El menor de los valores requeridos en el cuadrado mágico?

Question

Un cuadrado mágico de orden $n$ $n \times n$ cuadrícula que contiene cada uno de los números de $1,2,\dots,n^2$, de modo que los números en cada fila, columna y diagonal suma el mismo número $n(n^2+1)/2$.

Esta pregunta es la continuación de la mitad llenos de magia la plaza de problema NP-completo? sobre la realización de un parcialmente lleno cuadrado mágico.

Para $n=3$ el medio de la plaza debe ser $5$, por lo que si el centro de la plaza se establece a otro valor, entonces no hay manera de completar el cuadrado mágico. Por otro lado, si $n=4$ y un único número especificado (en cualquier lugar en la red), entonces siempre hay una manera de completar el cuadrado mágico. Esto puede ser comprobado por la inspección de la lista de orden-4 cuadrados mágicos, desde el sitio de Harvey Heinz.

Deje $f(n)$ ser el número mínimo de valores que cuando se coloca en una $n\times n$ cuadrícula, se traduce en un patrón que no se puede completar para formar un cuadrado mágico. Por los dos ejemplos anteriores, $f(3) = 1$$f(4) \ge 2$. El valor de $f(n)$ también puede ser considerado como el menos número de valores que se requieren en un parcial $n \times n$ cuadrado mágico para la toma de problema a ser interesante.

Esto motiva la siguiente pregunta:

¿Cuál es el comportamiento asintótico de $f(n)$ $n$ tiende a infinito?

Yo estaría especialmente interesado en saber si $f(n) = O(\log n)$ o si $f(n) = \Omega(n)$ (con big-O la notación).

Considere la posibilidad de la $k$ más pequeño de los números especificados junto con el $n-k$ más grande de los números en la misma fila. Esto no se alcanzarán los $n^2(n-1)/2$ al $k \gt n/2$. A continuación, se deduce que el $1 \le f(n) \le \lceil (n+1)/2 \rceil$. Hay más nítidos los límites superior e inferior en $f(n)$, tal vez por distinguir el caso de $n$ a de $n$ impar?

Answer 1

Tengo una idea que puede conducir a una prueba de que $f(n) = \Omega(\sqrt{n})$, pero requieren un poco de trabajo a la carne.

Aquí es la idea:$n = m^2$. Vamos a tratar de dividir el n x n cuadrado mágico en $m^2$ más pequeño m x m cuadrados de tal manera que cada uno de nuestros m de las pistas se encuentra en un cuadro diferente. (O tan cerca que como podemos conseguir).

Específicamente, estamos buscando una permutación $\pi \in S_n$ tal que $\pi(n-k) = n - \pi(k)$. A continuación definimos la (a,b)-subsquare a ser el subconjunto $[\pi(ma),\pi(ma+1)...\pi(ma+m-1)]$ x $[\pi(mb),\pi(mb+1),...\pi(mb+m-1)]$ de nuestros original cuadrado de $a,b \in [0,...m-1]$. Podemos señalar que los números en la $x=y$ diagonal de la (a,a)-subsquare todo proviene de la correspondiente diagonal de la plaza principal. Del mismo modo, los números en la $x=m-1-y$ diagonal de la (a,m-1-a)-subsquare vino de la otra diagonal de la plaza principal.

Estamos próximos a buscar una manera de dividir los números de 1 a $n^2 = m^4$ de tal manera como para hacer todas las $m^2$ subsquares en los cuadrados mágicos con la misma suma. Esto no es posible para m, pero puede ser posible para m impar. Nosotros realmente no es necesario que tengan la misma suma, sólo que el m x m la matriz de sumas de dinero es en sí mismo un cuadrado mágico, con no distintas entradas -- esto nos puede ayudar en el caso de m. Una vez que hemos hecho esto, hemos resuelto el original cuadrado mágico.

1) Para cualquier m-punto subconjunto S de $[0,...,n-1]^2$, hay una permutación $\pi$ tal que $(\pi(a),\pi(b))$ no está en el mismo subsquare como $(\pi(c),\pi(d))$$(a,b),(c,d) \in S$?

2) Dada una permutación, hay una manera de completar el $m^2$ subsquares en los cuadrados mágicos con la misma suma usando los números de 1 a $m^4$?