Um quadrado com entradas cujas adjacências nunca se repetem

Suponha que temos um quadrado, e um alfabeto Γ . Colocamos um elemento de Γ em cada local do quadrado. Um elemento pode aparecer em mais de um local. A restrição é que um par a , b de vizinhos (leste-oeste um do outro ou norte-sul um do outro) só pode aparecer nessa configuração uma vez.$n \times n$$\Gamma$$\Gamma$$a,b$

Exemplo de um quadrado proibido:

abc
def
gde

Como "de" aparece na segunda e na terceira linha, as entradas do quadrado não são aceitáveis. O mesmo problema surgiria se, digamos, um aparecesse acima de d em qualquer lugar, exceto no canto superior esquerdo.

Dado , a largura do quadrado como parâmetro, qual é o limite inferior do tamanho do alfabeto Γ ?$n$$\Gamma$

Eu adoraria (sugestões para) uma prova direta, mas também, esse tipo de problema de preenchimento de quadrados foi estudado? Não consigo conectá-lo a um quadrado latino ou a um design de bloco. Esse mapa é mapeado para qualquer objeto combinatório já nomeado?

(Nota: isso está relacionado a uma pergunta anterior sobre evitar palavras parciais, mas essa pergunta exigia apenas evitação leste-oeste, por assim dizer, enquanto aqui também preciso evitar repetições norte-sul.)

Uma versão estendida do meu comentário:

Seja um número primo. Então, podemos construir um n × n praça da tabela de multiplicação de inteiros módulo p . Por exemplo, se p = 5 , temos$p = n+1$$n \times n$$p$$p = 5$

1234
2413
3142
4321

Agora, cada par com a ≠ b ocorre exatamente uma vez. Da mesma forma, cada par a- acima de b com a ≠ b ocorre exatamente uma vez.$ab$$a \ne b$$a$$b$$a \ne b$

$n$$n \times n$

$n \times n$$n(n-1)$$n-1$$(n-1)^2 < n(n-1)$

EDITADO PARA ADICIONAR : O artigo de Gilbert tem importância histórica e resolve completamente o problema que fiz na minha pergunta. Por favor, veja a minha entrada no blog para mais detalhes.

RESPOSTA ORIGINAL

Acontece que o artigo que encontrei em 1965, os Quadrados Latinos de Gilbert que Não Contêm Digramas Repetidos , é bastante útil.

$n$$n$$|\Gamma| \leq n+1$$n+1$

$3-1 \neq 2-3$$2-1 = 3-2$

$ab$$a \lozenge^k b$$\lozenge$$k$$n-2$$k$$a \lozenge^k b$$n+1=p$$p$

$n$$n$$x \geq 396738$$[x,x+ x/25 \ln^2 x]$$n$$|\Gamma| \leq n + n/25\ln^2 n$