» Магические квадраты
|
Хорошо известно, что для построения некоторых магических квадратов можно использовать латинские квадраты [1]. Латинские квадраты, как и магические квадраты, изучал известный математик Леонард Эйлер.
Определение 2 ([3]). Согласно Эйлеру латинский квадрат – это квадратная таблица c n2 клетками, составленная из n различных элементов, ни один из которых не появляется дважды ни в какой строке и ни в каком столбце.
Пример 4.1.
1 |
3 |
2 |
3 |
2 |
1 |
2 |
1 |
3 |
Легко проверить, что данный квадрат является латинским и магическим с магической суммой равной 6.
Допустим, что латинский квадрат порядка n задан на первых n натуральных числах. Легко понять, что сумма элементов, стоящих в строках и столбцах такого квадрата одна и та же и она равна n(n+1)/2. Любой латинский квадрат является полумагическим квадратом.
Чтобы такой квадрат оказался магическим, мы можем потребовать выполнения следующего условия: на обеих диагоналях этого латинского квадрата все числа должны быть различными, то есть на этих диагоналях должны стоять числа от 1 до n в некотором порядке ([1]).
В примере 4.1 это условие выполняется для первой (главной) диагонали (слева направо, сверху вниз, там стоят числа 1, 2, 3) и не выполняется для второй диагонали (там стоят числа 2, 2, 2).
Таким образом, наше условие является достаточным, но не необходимым.
Для дальнейшего изложения нам понадобиться понятие квазигруппы. Напомним, понятие отображения является базисным в математике и точно не определяется.
Пусть S, T некоторые множества; функцией или отображением f из множества S в множество T называется правило, которое каждому элементу s множества S ставит в соответствие некоторый элемент t из множества T.
Взаимнооднозначное отображение f: T 
T на конечном множестве T называется подстановкой.
Пример 4. 2. Отображение f:
1 2 3,
2 3 1
то есть f(1)=2, f(2) =3, f(3)=1, является подстановкой множества {1,2,3}, а отображение g: 1 2 3
1 1 2
подстановкой не является. Отметим, отображение f имеет обратное отображение f -1 : 1 2 3
3 1 2
то есть, f -1 (1) = 3, f -1 (2) = 1, f -1 (3)=2. Для отображения g обратное отображение не существует.
Если Q есть множество, то множество всех упорядоченных пар множества Q называется прямым произведением множества Q на себя, или второй степенью множества Q, и обозначается так Q
Q.
Пример. Если Q = {1, 2, 3}, то Q
Q = {(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3)}.
Любое отображение f множества Q
Q в множество Q называется бинарной операцией.
Множество Q с определенной на нем бинарной операцией f называется группоидом и обозначается (Q,f).
Пример 4.3. Пример группоида:
|
В этом случае, например, f(2,3) = 1. Обычно используют другие символы бинарных операций, например, +. Тогда выражение f(2,3) = 1 запишется так 2+3 = 1.
Таблица из примера 4.3 называется таблицей Кэли группоида.
Определение 3. Группоид (Q,+) называется квазигруппой, если для любой пары элементов a, b из множества Q уравнения x + a = b и a + y = b имеют единственное решение.
Пример. Группоид из примера 4.3 есть квазигруппа.
Можно доказать что “внутренность” таблицы “умножения” квазигруппы есть латинский квадрат. “Внутренность” таблицы “умножения” квазигруппы из примера 4.3 имеет вид:
1 |
3 |
2 |
3 |
2 |
1 |
2 |
1 |
3 |
Напомним [1, 3], группой называется квазигруппа (Q, ∙), в которой для всех элементов x, y, z выполняется тождество x ∙ (y∙z) = (x∙y) ∙z (тождество ассоциативности). Группа (Q, ∙) называется коммутативной или абелевой, если в ней выполняется тождество коммутативности: x∙y = y∙x.
Любая группа обладает элементом 1 таким, что для всех x
Q выполняется соотношение 1∙x = x∙1 = x.
Пример. Множество вычетов по модулю n образует коммутативную (абелеву) группу относительно сложения вычетов, обозначим ее Zn. В таблице приведена группа вычетов по модулю 3, то есть группа Z3.
|
Отметим, вообще говоря, множество вычетов по модулю n относительно умножения вычетов, группы не образует, а образует только группоид, в котором выполняется тождество ассоциативности, то есть оно образует полугруппу.
∙ |
0 |
1 |
2 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
2 |
2 |
0 |
2 |
1 |
∙ |
0 |
1 |
2 |
3 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
2 |
3 |
2 |
0 |
2 |
0 |
2 |
3 |
0 |
3 |
2 |
1 |
Латинский квадрат ||aij|| называется полудиагональным слева, если все элементыстоящие на первой диагонали различны, то есть различны элементы а11, a22, . . . , ann , латинский квадрат называется полудиагональным справа, если различны все элементы стоящие на второй диагонали, то есть различны элементы а1n, a2(n-1), . . . , an1.
Полудиагональный слева и справа латинский квадрат называется диагональным латинским квадратом. Очевидно, любой диагональный латинский квадрат является магическим ([1]).
Мы будем использовать операции сложения и умножения на множестве вычетов по модулю n для построения диагональных латинских квадратов.
Утверждение 1. Если вычет s взаимно прост с модулем n, то есть НОД(s, n) = 1, то s∙(Zn ) является подстановкой множества Zn , то есть s∙(Zn )= Zn.
Доказательство. Допустим противное, что существуют различные числа a, b
Zn такие что s∙ a= s ∙b (mod n). Тогда по свойствам вычетов s∙a − s ∙b = 0 (mod n), s∙(a − b) = 0 (mod n). Так как НОД(s, n) = 1, то (a − b) = 0 (mod n). Следовательно, a = b (mod n). Получили противоречие.
Известно ([4]), для вычета s, такого что НОД(s, n) = 1, существует такой элемент t, что s∙t =1 (mod n). Элемент s называется обратимым элементом, а элемент t называется обратным элементом к элементу s. Будем обозначать элемент t таким образом: s-1.
Утверждение 2. Группоид (Zn, ▫) такой, что x▫y = s∙x + t∙y, где операция “+” − операция сложения по модулю n, операция “∙” есть операция умножения по модулю n, элементы s и t являются обратимыми элементами, является квазигруппой.
Доказательство. Найдем решение уравнения a ▫ x = b. Переходя к операции + получаем: s ∙ a + t ∙ x = b, t ∙ x = b − s ∙ a. Умножая обе части последнего равенства на элемент d, такой, что d∙t=1, далее получаем d ∙ (t ∙ x) = d ∙ (b − s ∙ a), (d ∙ t) ∙ x = d ∙ (b − s ∙ a), 1 ∙ x = d ∙ (b − s ∙ a), x = d ∙ (b − s ∙ a). Таким образом, решение существует и оно единственно.
Найдем решение уравнения y ▫ a = b. Переходя к операции + , получаем: s ∙ y + t ∙ a = b, s ∙ y = b − t ∙ a. Умножая обе части последнего равенства на элемент c, такой, что c ∙ s = 1, далее получаем c ∙ (s ∙ y) = c ∙ (b − t ∙ a), (c ∙ s) ∙ y = c ∙ (b − t ∙ a), 1 ∙ y = c ∙ (b − t ∙ a), 1 ∙ y = c ∙ (b − t ∙ a). Таким образом, решение существует и оно единственно и в этом случае.
Найдем условие, при выполнении которого на левой диагонали квазигруппы (Zn, ▫) все элементы различны.
Утверждение 3. В квазигруппе (Zn, ▫) такой, что x▫y = s∙x + t∙y для всех x, y 
Zn на левой диагонали квазигруппы (Zn, ▫) все элементы различны если элемент (s+t ) является обратимым.
Доказательство. Мы имеем x▫x = s∙x + t∙x = (s + t)∙x для всех x
Zn. По Утверждению 1 на главной диагонали все элементы будут различны, если умножение множества вычетов по модулю n на элемент (s + t) будет подстановкой этого множества, то есть если НОД((s + t), n) = 1.
Утверждение 4. В квазигруппе (Zn, ▫) такой, что x▫y = s∙x + t∙y для всех x, y 
Zn на правой диагонали все элементы различны, если элемент (s−t) является обратимым.
Доказательство. Допустим что множество Zn состоит из элементов 0, 1, ... , (n-1). Пронумеруем элементы стоящие на правой диагонали элементами из множества Zn в их естественном порядке. Тогда на правой диагонали будут стоять элементы: а0(n-1), a1(n-2), . . . , ai(n-1-i), . . . , a(n-1)0 . Таким образом, любой элемент на правой диагонали можно представить как произведение i▫(n−1−i), где i
{0, 1, ... , (n-1)}.
Подставляя в выражение x▫y = s∙x + t∙y вместо x символ i, вместо переменной y символ (n−1−i) далее имеем i▫(n−1−i) = s ∙i + t∙(n−1−i) = s ∙i + t∙n− t∙1− t∙i = s ∙i − t∙i + t∙n− t∙1 = (s − t)∙i + t∙(n− 1).
Ясно, что отображение, сопоставляющее каждому элементу i элемент (s − t)∙i + t∙(n − 1) является подстановкой только в случае, когда элемент (s − t) является обратимым элементом множества вычетов по модулю n, то есть если НОД((s − t), n) = 1.
Теорема 1. Квазигруппа (Zn, ▫), где x▫y = s∙x + t∙y для всех x, y 
Zn ,
(Zn , +) является группой вычетов по модулю n, будет диагональной квазигруппой, если НОД((s + t), n) = 1 и НОД((s − t), n) = 1.
Доказательство следует из Утверждений 3 и 4.
Квазигруппа из Теоремы 1 является тотально анти-коммутативной ([5]).
Пример. Приведем пример диагональной квазигруппы (Z5, 
) вида x
y = 1∙x + 3∙y, “внутренность” которой является латинским магическим квадратом порядка 5.
∙ |
0 |
1 |
2 |
3 |
4 |
0 |
0 |
2 |
4 |
1 |
3 |
1 |
1 |
3 |
0 |
2 |
4 |
2 |
2 |
4 |
1 |
3 |
0 |
3 |
3 |
0 |
2 |
4 |
1 |
4 |
4 |
1 |
3 |
0 |
2 |
