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
    Did I get it right? The claim is that a latin square of this form cannot be pandiagonal, when $n$ is divisible by three? Your title suggests that this is the case, but your first sentence does not really claim anything!2012-07-20
  • 0
    The entries in an $n\times n$ Latin square are supposed to be taken from $1,2,\dots,n$, right? But the entries in the square above are bigger, so how is this a Latin square?2012-07-20
  • 0
    Try the following exercise. Experiment with different values of $a$ and $b$ (reducing all the entries modulo $n=3k$). Try to do it in such a way that 1) some entries on the first row are not divisible by 3, 2) some entries on the first column are not divisible by 3, 3) some entries on the diagonal are not divisible by 3, and last but not least 4) all the broken back-diagonals have entries not divisible by 3. Try it first with $n=6$. Trying things out like this is the way to enlightenment. You will not benefit anything from me spelling out a proof for you.2012-07-20
  • 0
    @Jyrki, the entries are supposed to be reduced modulo $n$, which equals $3k$? Fabulous! I would never have guessed that, and Danielle likes keeping secrets.2012-07-21
  • 0
    @Gerry: You're right,of course. I am just enjoying this game of guessing what the question really is. Sorry to get in the way of your effort to squeeze these bits from OP (particularly in light of me criticizing your recent answer in MO - not my best day).2012-07-21
  • 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