Un cuadrado con entradas cuyas adyacencias nunca se repiten

Supongamos que tenemos un cuadrado y un alfabeto . Ponemos un elemento de en cada ubicación del cuadrado. Un elemento puede aparecer en más de una ubicación. La restricción es que un par de vecinos (este-oeste uno del otro o norte-sur uno del otro) solo puede aparecer en esa configuración una vez.Γ Γ a , $n \times n$$\Gamma$$\Gamma$$a,b$

Ejemplo de un cuadrado prohibido:

abc
def
gde

Como "de" aparece en la segunda y la tercera fila, las entradas del cuadrado no son aceptables. El mismo problema surgiría si, por ejemplo, a apareciera encima de d en cualquier lugar, excepto en la esquina superior izquierda.

Dado , el ancho del cuadrado como parámetro, ¿cuál es un límite inferior en el tamaño del alfabeto ?$n$$\Gamma$

Me encantaría (sugerencias) una prueba directa, pero también, ¿se ha estudiado este tipo de problema de relleno cuadrado? No puedo conectarlo a un cuadrado latino ni a un diseño de bloque. ¿Se correlaciona con algún objeto combinatorio ya nombrado?

(Nota: esto está relacionado con una pregunta mía anterior sobre evitar palabras parciales, pero esa pregunta solo requería evitarse de este a oeste, por así decirlo, mientras que aquí también necesito evitar las repeticiones de norte a sur).

Una versión extendida de mi comentario:

Sea un número primo. Luego podemos construir un cuadrado a partir de la tabla de multiplicación de enteros módulo . Por ejemplo, si , tenemosn × n p p = $p = n+1$$n \times n$$p$$p = 5$

1234
2413
3142
4321

Ahora cada par con ocurre exactamente una vez. Del mismo modo, cada par -above- con ocurre exactamente una vez.a ≠ b a b a ≠ $ab$$a \ne b$$a$$b$$a \ne b$

Por lo tanto, esta es una construcción válida; tamaño del alfabeto un cuadrado .n × $n$$n \times n$

Por otra parte, es óptimo. En un cuadrado hay pares horizontales, y cada uno de ellos debe ser diferente. Si tuviéramos un alfabeto de tamaño , solo podríamos construir diferentes pares horizontales.n ( n - 1 ) n - 1 ( n - 1 ) 2 < n ( n - 1 $n \times n$$n(n-1)$$n-1$$(n-1)^2 < n(n-1)$

EDITADO PARA AGREGAR : el artículo de Gilbert resulta tener una importancia histórica y resuelve completamente el problema que hice en mi pregunta. Por favor vea mi entrada de blog para más detalles.

RESPUESTA ORIGINAL

Resulta que el artículo que encontré de 1965, Cuadrados latinos de Gilbert que no contienen digramas repetidos , es bastante útil.

Usando permutaciones con diferencias distintas , construye cuadrados latinos de tamaño para cada par , de modo que ningún par adyacente se repita en el cuadrado, ni en filas ni en columnas. Entonces en mi pregunta, porque el parámetro de entrada es par, o simplemente puedo agregarle uno, construir el cuadrado latino de tamaño , y luego cortar una fila y una columna.$n$$n$$|\Gamma| \leq n+1$$n+1$

(Una permutación con diferencias distintas es una permutación en la que todas las diferencias entre elementos consecutivos son distintas. Entonces, por ejemplo, en tres elementos, (1 3 2) es una permutación con diferencias distintas, ya que , pero (1 2 3) no lo es, ya que .)$3-1 \neq 2-3$$2-1 = 3-2$

Más tarde generaliza esto de una manera que se relaciona con la respuesta de Jukka. Supongamos que queremos no solo apariencias únicas de pares , sino de , donde es un símbolo de "no me importa", y varía de 0 a . Es decir, para una determinada , habría como máximo una aparición de en las filas, y como máximo una en las columnas, del cuadrado. (Por cierto, esta es una propiedad que me interesa mucho). Según otro teorema de Gilbert, es posible construir un cuadrado latino con dicha propiedad si donde es primo.$ab$$a \lozenge^k b$$\lozenge$$k$$n-2$$k$$a \lozenge^k b$$n+1=p$$p$

Entonces la pregunta se convierte en: dado , ¿cuál es el menor número primo mayor que ? El teorema del número primo, etc., solo da límites asintóticos, pero hay algunos límites explícitos conocidos. El mejor que he encontrado se debe a Dusart, Estimaciones de algunas funciones sobre los períodos sin HR : para , hay al menos un primo en el intervalo . Por lo tanto, si queremos evitar la repetición de pares con símbolos de no importar entre ellos, asintóticamente, para suficientemente grande , .n x ≥ 396738 [ x , x + x / 25 ln 2 x ] n | Γ | ≤ n + n / 25 ln 2$n$$n$$x \geq 396738$$[x,x+ x/25 \ln^2 x]$$n$$|\Gamma| \leq n + n/25\ln^2 n$