Sotiri's Doku Squares

Since there are still no solutions, I guess there's no harm in posting mine.

The solution boils down to answering two questions about Doku Squares (which will be referred to as DSs from now on). Firstly, is there an upper bound on the maximum number of $n \times n$ DSs that are pairwise-friendly, and secondly, if there is, which values of $n$ (if any) actually achieve that upper bound?

The first question has a fairly simple answer.

Lemma 1 An upper bound on the number of $n \times n$ DSs that are pairwise-friendly is $n-1$ .

Proof We note that taking any DS and permuting its elements (that is, taking every instance of $i$ in the DS and replacing it with $j$ and vice versa) will not change the fact that it is a DS. This means that we can make the first row of any DS be whatever we want it to be (by permuting multiple times), and from this point forward, we will call DSs that have their first row in increasing order "happy." That is, if A is a happy DS, then $A_{1,1}=0,A_{1,2}=1,...,A_{1,n}=n-1$ .

We also note that these permutations preserve friendliness. This is because if we have (for example) the ordered pairs $(a,a),(a,b),(a,c),(b,a),(b,b),(b,c),(c,a),(c,b),(c,c)$ (which would be the ones generated by two friendly $3 \times 3$ DSs, applying a permutation such as $a \to c,c \to a,b \to b$ on one of them (say the first one) gives the ordered pairs $(c,a),(c,b),(c,c),(b,a),(b,b),(b,c),(a,a),(a,b),(a,c)$ , which is clearly the same set of ordered pairs, and so the permuted first DS is still friendly with the original second DS. This is important because it tells us that if we have a set of $n \times n$ DSs which are pairwise-friendly, we can make each of them happy and be sure that they are still all pairwise-friendly.

Let $N$ be a set of happy pairwise-friendly $n \times n$ DSs and let $A,B$ be members of $N$ . Looking at the first row of $A$ and $B$ , we find that $(A_{1,1},B_{1,1})=(0,0),...,(A_{n,n},B_{n,n})=(n-1,n-1)$ . Now let $A_{2,1} = a$ . $a$ , of course, cannot be $0$ , as $0$ is already present in the first column of $A$ . But now note that $B_{2,1}$ cannot be $a$ , as the ordered pair $(a,a)$ is already found by comparing the first rows of $A$ and $B$ . By extension, any two DSs in $N$ must have distinct elements in the cell $(2,1)$ , and this cell has $n-1$ possible values $1,2,...,n-1$ . Therefore, the set $N$ can't possibly have $n$ elements, and so $n-1$ is an upper bound on the maximum number of pairwise-friendly $n \times n$ DSs. $\square$

$\\$

Now that we've established that there is, in fact, an upper bound, we proceed to find values which achieve this upper bound. We will show that for all primes $p > 2$ , there is a set of $p-1$ pairwise-friendly $p \times p$ DSs.

Lemma 2 If $p>2$ is a prime, there exists a set of $p-1$ pairwise-friendly DSs.

Proof We will construct the set we want, thus proving its existence.

Consider a set $S$ of $p-1$ empty $p \times p$ arrays numbered from $1$ to $p-1$ . Let $S^t$ represent the array in the $t$ th position in the set.

We proceed by filling in all the elements of $S$ in the following manner: $\forall 1 \leq i,j \leq p,S^t_{(i,j)}=i \cdot t + j \pmod{p}$ . It is evident that the only numbers we can have in the array are the integers from 0 to p−1.

First, let's confirm that $\forall t,S^t$ is, in fact, a DS. It suffices to show that if $i \cdot t + j \equiv i' \cdot t + j' \pmod{p}$ and $i = i'$ , then $j = j'$ and vice versa. Essentially, if we have two of some value in the same row, then they are also in the same column (which means they are the same position).

$i \cdot t + j \equiv i' \cdot t + j' \pmod{p} \to t(i - i') \equiv j-j \pmod{p}$ . We remind ourselves that $t \neq 0$ . If we let either $j' - j$ or $i - i'$ be $0$ modulo $p$ (which means they equal 0 since they are less than $p$ in absolute value), then the other must also equal 0 (again, because they are less than $p$ , and the fact that p is prime guarantees that we won't have $t(i-i′) = p \neq 0$ ). Therefore, if the value of two positions in the same row/column are the same, they are the same position, and so all the $S^t$ are DSs.

Finally, we want to show that all the $S^t$ are pairwise-friendly. Consider $S^a$ and $S^{a'}$ with $a \neq a'$ . We want the following to be true: if $i \cdot a + j \equiv i' \cdot a + j' \pmod{p}$ and $i \cdot a' + j \equiv i' \cdot a' + j' \pmod{p}$ , then $i = i'$ and $j = j'$ . Essentially, if we pick two sets of corresponding positions in $S^a$ and $S^{a'}$ and they end up corresponding to the same ordered pair, they are the same corresponding positions.

$i \cdot a + j \equiv i' \cdot a + j' \pmod{p} \to a(i - i') \equiv j'-j \pmod{p}$ and $i \cdot a' + j \equiv i' \cdot a' + j' \pmod{p} \to a'(i - i') \equiv j'-j \pmod{p}$ . Then we have $a'(i - i') \equiv a(i - i') \pmod{p}$ by the transitive property of congruence. But we know that $a \neq a'$ and so $i - i' \equiv 0 \pmod{p} \to i = i'$ and then $j = j'$ (because once again all of $i, j, i', j', a, a' \leq p$ ). Thus, if two sets of corresponding positions make the same ordered pair, the two sets are the same.

This result proves that all the $S^t$ are, in fact, pairwise-friendly, and therefore, there is a set of $p-1$ pairwise-friendly $p \times p$ DSs. $\square$

$\\$

Therefore, for any prime $p > 2$ , we have that the maximum number of pairwise friendly $p \times p$ DSs is equal to $p -1$ , and so because $73$ is a prime, the answer is $73 - 1 = \fbox{72}$ .

$\\$

Further information: The Doku Squares in this problem are, in fact, well-known objects in mathematics called Latin Squares. "Friendly" Latin Squares are called "orthogonal." The result presented in this solution about all primes can actually be extended to all prime powers, but for a general composite number $n$ , the maximum number of $n \times n$ orthogonal Latin Squares is not known.