Закрыть

Магический квадрат

Автор: Васин Алексей
Опубликовано 22.03.2008 в 22:52
Раздел: Теория чисел
Теги:

Что такое магический квадрат?

Магический квадрат это - квадратная $n \times n$ - таблица $\Vert a_{ij} \Vert$ целых чисел от 1 до $n^2$, удовлетворяющая следующим условиям:

$\displaystyle{\sum_{i=1}^{n} a_{ij} = \sum_{j=1}^{n} a_{ij}} =$

$\displaystyle{=\sum_{i=1}^{n} a_{ii}=\sum_{i=1}^{n} a_{i,n+1-i} = s}$ (1),

где $\displaystyle{s=n\frac{(n^2+1)}{2}}$. Иногда, рассматриваются также более общие магические квадраты, в которых не требуется, чтобы $1 \leq a_{ij}\leq n^2$.

Как построить магический квадрат?

Любое число a, $1 \leq a \leq n^2$, однозначно характеризуется парой вычетов $(\alpha, \beta)$ по модулю $n$ (цифрами по основанию $n$ числа $a-1$), т. е. точкой двумерного пространства $(\mathbb{Z}/n)^2$ над кольцом $\mathbb{Z}/2$ вычетов по модулю n. Поскольку координаты (i,j) клеток квадрата также можно считать элементами пространства $(\mathbb{Z}/n)^2$, отсюда следует, что любое распределение чисел от 1 до $n^2$ в квадратную $n*n$ title="n \times n$ - таблицу $\Vert a_{ij} \Vert$ задается некоторым отображением

$(\mathbb{Z}/n)^2 \to (\mathbb{Z}/n)^2$,

т. е. парой функций $\alpha = \alpha(i, j) \in \mathbb{Z}/n$, $\beta=\beta(i,j) \in \mathbb{Z}/n$ от $i,j \in \mathbb{Z}/n$. Задача состоит в исследовании таких пар, дающих магический квадрат. В общем виде это сделано только при дополнительном предположении линейности функций $\alpha$ и $\beta$. Оказалось, в частности, что магические квадраты с линейными функциями $\alpha$ и $\beta$ существуют только при нечетных n.

Уже в средние века был известен ряд алгоритмов построения магических квадратов нечетного порядка n. Каждый такой алгоритм характеризуется шестью вычетами $i_0,j_0,q,\overline{q},\overline{p}$ и описывается следующими правилами:

  1. число 1 вписывается в клетку $(i_0,j_0)$
  2. если число $a$ вписано в клетку $(i,j)$, то число $a+1$ вписывается в клетку $(i+p, j+q)$, если эта клетка еще свободна от чисел, и в клетку $i+\overline{p},j+\overline{q}$, если клетка $(i+p, j+q)$ занята.

Вычеты $i_0, j_0, q, \overline{q}, \overline{p}$ не могут быть произвольны, но должны удовлетворять определенным условиям, обеспечивающим не только выполнение условий (1), но и  выполнимость   алгоритма,   т. е.    пустоту   клетки
$i+\overline{p},j+\overline{q}$, если занята клетка $(i+p, j+q)$. Эти условия легко находятся, причем оказывается, что магический квадрат тогда и только тогда может быть построен алгоритмом такого вида, когда описывающие этот квадрат функции $\alpha, \beta$ линейны.

Небольшое добавление.

Известно много других алгоритмов построения магических квадратов (приводящих к квадратам с нелинейными функциями $\alpha, \beta$, но никакой общей их теории нет. Неизвестно даже общее число магических квадратов порядка n (при $n \leq 5$ для $n=3$ существует, с точностью до очевидных симметрии, только один магический квадрат, а для $n=4$ число магических квадратов равно 880).

Комментарии (0)

Комментировать могут только зарегистрированные пользователи

Подразделы
Новые статьи
Aрхив статей