A square with entries whose adjacencies never repeat Suppose we have an $n \times n$ square, and an alphabet $\Gamma$.  We put an element of $\Gamma$ in each location of the square. An element can appear in more than one location.  The constraint is that a pair $a,b$ of neighbors (either east-west of each other, or north-south of each other) can only appear in that configuration once.

Example of a prohibited square:

a b c
d e f
g d e  

Since "de" appears on both the second and the third row, the entries of the square are not acceptable. The same problem would arise if, say, a appeared above d anywhere except the top left corner. 


  Given $n$, the width of the square as a parameter, what is a lower bound on the size of the alphabet $\Gamma$?


I would love (suggestions toward) a direct proof, but also, has this type of square-filling problem been studied?  I can't connect it to either a Latin square, or a block design.  Does this map onto any already-named combinatorial object?

(Note: this is related to a previous question of mine about avoiding partial words, but that question only required avoidance east-west, so to speak, whereas here I need to avoid north-south repetitions also.)
An extended version of my comment:

Let $p = n+1$ be a prime number. Then we can construct an $n \times n$ square from the multiplication table of integers modulo $p$. For example, if $p = 5$, we have

1234
2413
3142
4321


Now each pair $ab$ with $a \ne b$ occurs exactly once. Similarly, each pair $a$-above-$b$ with $a \ne b$ occurs exactly once.

Hence this is a valid construction; alphabet size $n$ and an $n \times n$ square.

Moreover, it is optimal. In an $n \times n$ square there are $n(n-1)$ horizontal pairs, and each of them must be different. If we had an alphabet of size $n-1$, we could only construct $(n-1)^2 &lt; n(n-1)$ different horizontal pairs.