2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Превращаем латинский квадрат в почти магический
Сообщение21.03.2006, 14:10 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение21.03.2006, 14:41 
Экс-модератор
Аватара пользователя


23/12/05
12046
Как построить этот латинский квадрат? Например вот так:
$\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 возможно получить различные суммы по диагоналям.

 Профиль  
                  
 
 
Сообщение21.03.2006, 14:52 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение21.03.2006, 15:11 


09/11/05
40
Начиная с 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 )

 Профиль  
                  
 
 
Сообщение21.03.2006, 16:29 
Заслуженный участник
Аватара пользователя


07/03/06
1898
Москва
Вот стоит только спросить что-либо о хорошо изученном и популярном…
Спасибо за ссылку (то, что для любого 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 и любого их произведения в любой степени – и только для них. Попробуйте это доказать.

 Профиль  
                  
 
 
Сообщение21.03.2006, 16:49 
Экс-модератор
Аватара пользователя


23/12/05
12046
sonte писал(а):
A.J.W. Hilton, On double diagonal and cross latin squares, J. London Math. Soc. (2), 6 (1973), 679-689.

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

 Профиль  
                  
 
 
Сообщение21.03.2006, 21:32 


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

 Профиль  
                  
 
 review
Сообщение21.03.2006, 21:35 
Модератор
Аватара пользователя


11/01/06
5660
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

 Профиль  
                  
 
 
Сообщение21.03.2006, 23:33 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение22.04.2006, 21:06 
Заслуженный участник
Аватара пользователя


07/03/06
1898
Москва
К сожалению, никто не заинтересовался решением этой простой задачки.
Итак, будем доказывать, что если составить таблицу Кэли по операции умножения остатков (исключая нуль) от деления по модулю простого числа $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$, т.е. ясно, что там тоже стоят квадратичные вычеты, на которые можно распространить теже самые рассуждения.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 10 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group