1
$\begingroup$

I would like to prove the claim that pandiagonal latin squares, which are of form

                  0        a          2a         3a         ...  (n-1)a                   b        b+a        b+2a       b+3a       ...   b+ (n-1)a                   .        .          .                   .        .          .                   .        .          .                   (n-1)b   (n-1)b +a  (n-1)b +2a (n-1)b +3a  ...  (n-1)(b+a) 

for some $a,b\in (0,1...n-1)$ cannot exist when the order is divisible by 3.

I think we should be able to show this if we can show that the pandiagonal latin square of order $n$ can only exist iff it is possible to break the cells of a $n \times n$ grid into $n$ disjoint superdiagonals. Then we would show that an $n\times n$ array cannot have a superdiagonal if $n$ is a multiple of $2$ or $3$. I am, however, not able to coherently figure out either part of this proof. Could someone perhaps show me the steps of both parts?

A superdiagonal on an $n \times n$ grid is a collection of $n$ cells within the grid that contains exactly one representative from each row and column as well as exactly one representative from each broken left diagonal and broken right diagonal.

EDIT: Jyrki, could you please explain how the claim follows from #1?

  • 0
    @Jyrki, your criticism led me to find an answer I like better than what I had before. And I'm just jealous that you were able to figure out what OP wanted here, when I couldn't.2012-07-21

1 Answers 1

2

[Edit: replacing the old set of hints with a detailed answer]

Combining things from the question as well as its title and another recent question by the same use tells me that the question is the following. When $n$ is divisible by three, show that no combination of parameters, $a,b\in R=\mathbb{Z}/n\mathbb{Z}$ in a general recipe $L(i,j)=ai+bj, i,j \in R$ for constructing latin squares, gives rise to a latin square with the extra property (=pandiagonality) that the entries on each broken diagonal parallel to either main or back diagonal are all distinct.

The first thing we observe that $a$ cannot be divisible by three or, more precisely, it cannot belong to the ideal $3R$. For if it were, then all the entries on the first row would also be in the ideal $3R$. Consequently some numbers, for example $1$, would not appear at all on the first row, and the construction would not yield a latin square at all.

Similarly, the parameter $b$ cannot be divisible by three, as then the first column would only contain numbers divisible by three.

So both $a$ and $b$ are congruent to either $1$ or $2$ modulo $3$. We split this into two cases. If $a\equiv b \pmod 3$ (i.e. both congruent to one or both congruent to two), then $a-b$ is divisible by three. When we move one position to the right and one up in the shown diagram, we always add $a-b$ (modulo $n$) to the entry. This means that the entries along an ascending broken diagonal are all congruent to each other modulo three. Again some entries will be missing as the entries are limited to a coset of the ideal $3R$.

The remaining case is that one of $a,b$ is congruent to $1$ modulo $3$ and the other is congruent to $2$ modulo $3$. In that case their sum $a+b$ will be divisible by three. When we move one position to the right and one down on the table, we add $b+a$ (modulo $n$) to the entry. This means that the entries along a descending broken diagonal are all congruent to each other modulo three, and we run into a similar contradiction as earlier.

To summarize: The solution relies on the special property of number three that for all integers $a,b$ the product $ab(a-b)(a+b)$ will be divisible by three, so in one of the four critical directions (horizontal, vertical, descending/ascending diagonal) the entries will always congruent to each other modulo $3$.

  • 0
    @Danielle, try (with for example $n=6$ or $n=9$) what happens with the first row, when $a$ is divisible by $3$.2012-07-21