Превращаем латинский квадрат в почти магический

[juna]

Известно, что латинским квадратом называется квадрат NxN клеток, в котором написаны числа 1, 2, …N, притом так, что в каждой строке и каждом столбце встречаются все эти числа по одному разу. Ясно тогда, что сумма всех чисел любого столбца и любой строки равна $\frac {(N+1)N}{2}$.
Вопрос: для каких N сумма чисел обеих диагоналей также равна $\frac {(N+1)N}{2}$, т.е. латинский квадрат превращается в почти магический.

[photon]

Как построить этот латинский квадрат? Например вот так:
$\begin{array}{*{20}c} 1 & 2 & \cdots & {} & {} & N \\ N & 1 & 2 & \cdots & {} & {N - 1} \\ {N - 1} & N & 1 & \cdots & {} & {N - 2} \\ {} & {} & {} & \vdots & {} & {} \\ {} & {} & {} & {} & {} & {} \\ 2 & 3 & \cdots & {N - 1} & N & 1 \\ \end{array} $
Затем можно произвольным образом переставлять местами строки либо колонки, а также поворачивать весь квадрат.
Очевидно, что при начальной расстановке цифр, как это сделал я, при любом N сумма элементов главной диагонали равна N, а не $\frac{N(N+1)}{2}$. Тогда наверное правильно поставить вопрос: "При каких N возможно получить квадрат, удовлетворяющий заданному условию?" В начальной постановке вопрос некорректен: при одних и тех же значениях N возможно получить различные суммы по диагоналям.

[juna]

Да, конечно, именно это и имелось ввиду. Т.е. при каких N среди всех возможных латинских квадратов для этого N можно найти латинский квадрат удовлетворяющий условию.

[sonte]

Начиная с N=4 всегда существует диагональный латинский квадрат (то есть на каждой из двух диагоналей все числа различны):
A.J.W. Hilton, On double diagonal and cross latin squares, J. London Math. Soc. (2), 6 (1973), 679-689.
(Найдено в http://flying-bear.livejournal.com/6722 ... 97#t578197 )

[juna]

Вот стоит только спросить что-либо о хорошо изученном и популярном…
Спасибо за ссылку (то, что для любого N>3 можно построить диагональный латинский квадрат для меня приятная неожиданность – вот только по ссылке сам алгоритм построения не указан).
У меня эта идея появилась вне связи с латинскими квадратами. Поэтому я хотел привести здесь алгоритм построения латинских квадратов указанного свойства для специального N=4k, где 4k+1 – простое число. Алгоритм прост – составляете таблицу Кэли (исключая нуль) по операции умножения по модулю этого простого числа – данная таблица и есть латинский квадрат с указанным свойством. Например, для N=4 имеем:
1 2 3 4
2 4 1 3
3 1 4 2
4 3 2 1
В отличие от диагонального латинского квадрата:
1 3 4 2
4 2 1 3
2 4 3 1
3 1 2 4
у представленного по диагоналям могут стоять не все числа, но сумма также равна указанной. Утверждается, что так будет для каждого простого числа вида 4k+1 и любого их произведения в любой степени – и только для них. Попробуйте это доказать.

[photon]

sonte писал(а):

A.J.W. Hilton, On double diagonal and cross latin squares, J. London Math. Soc. (2), 6 (1973), 679-689.

А у Вас есть доступ к этой работе? Я на сайте LMS нашел только выпуски с 55-го тома (1997 г)

[sonte]

Нет, у меня этой статьи нет.
Помнится, через scholar.google можно найти какую-то более позднюю статью других авторов с изложением этой конструкции.

[maxal]

MR0319787 (47 #8328)
Hilton, A. J. W.
On double diagonal and cross latin squares.
J. London Math. Soc. (2) 6 (1973), 679--689.
05B15

References: 0 Reference Citations: 0 Review Citations: 3

A Latin square of order $n$ is said to be double diagonal if both its main diagonal (cells $(1,1),(2,2),\cdots,(n,n)$) and off diagonal (cells $(1,n),(2,n-1),\cdots,(n,1)$) are transversals. The author's main result is the first construction of a double diagonal Latin square of every order (except, of course, 2 and 3). In order to construct a double diagonal Latin square of every order the author introduces the idea of a cross Latin square. A cross Latin square of even order is a Latin square in which the same entry occurs in every cell on the main diagonal and the same entry occurs in every cell on the off diagonal. For Latin squares of odd order this definition is altered to the requirements that the same entry occurs in every cell on one of the diagonals and that all but two of the entries on the other diagonal be the same. The author constructs a cross Latin square of every order for use in his construction of double diagonal Latin squares. As a consequence of these constructions, the author obtains a lower bound for the number of cross and double diagonal Latin squares: at least $((2k)!(2k-1)!\cdots 2·1)^2$ cross Latin squares of orders $4k+1,4k+2,4k+3,4k+4 (k\geq 1)$, at least $((2k-1)!(2k-2)!\cdots 2·1)^2$ double diagonal Latin squares of order $4k+1$ or $4k+3 (k\geq 3)$, and at least $((2k)!(2k-1)!\cdots 2·1)^2$ double diagonal Latin squares of order $4k+2$ or $4k+4 (k\geq 2)$.

Reviewed by Charles C. Lindner

[juna]

Несмотря на то, что информация эта ценная – нижние ограничения на количество диагональных латинских квадратов разных видов, идея автора о «перекрестных латинских квадратах» - но сам алгоритм приходится додумывать самому – а ведь он, как следует из вышеприведенной ссылки – нетривиальный. Пока не видно как из перекрестного
1 2 3 4
2 1 4 3
3 4 1 2
4 3 2 1
алгоритмически получить диагональный.
Господа! Обратите внимание и на мою задачку, она много проще, но не лишена занимательной красоты.

[juna]

К сожалению, никто не заинтересовался решением этой простой задачки.
Итак, будем доказывать, что если составить таблицу Кэли по операции умножения остатков (исключая нуль) от деления по модулю простого числа $p=4k+1$, то сумма элементов обеих диагоналей равна $\frac {p(p-1)}{2}$.
1. Поскольку число $p$ простое, то в каждой строке и каждом столбце стоят все различные числа от 1 до (p-1).
2. На главной диагонали стоят все вычеты, сравнимые с $x^2$, где $x$ пробегает числа от 1 до (p-1), т.е. там стоят все квадратичные вычеты по модулю p. Поскольку квадратичных вычетов ровно $\frac {(p-1)}{2}$, а $x^2\equiv {(p-x)}^2 mod {p}$, то на главной диагонали удвоенное количество квадратичных вычетов. Если $a$ - квадратичный вычет простого числа $p=4k+1$, то и $p-a$ - квадратичный вычет, т.е. в свою очередь квадратичные вычеты можно сгруппировать по парам, так чтобы их сумма равнялась $p-a+a=p$. Таким образом, сумма чисел главной диагонали - это $\frac {2(p-a+a)(p-1)}{2*2}=\frac {p(p-1)}{2}$
3. Во второй диагонали находятся произведения $x(p-x)=xp-x^2$, т.е. ясно, что там тоже стоят квадратичные вычеты, на которые можно распространить теже самые рассуждения.