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

- квадратная [img: http://localhost:8080/file/031401-1.jpg] -таблица [img: http://localhost:8080/file/031401-2.jpg] целых чисел от 1 до n2, удовлетворяющая следующим условиям: [img: http://localhost:8080/file/031401-3.jpg] где s=n(n2+1)/2. Рассматриваются также более общие М. к., в к-рых не требуется, чтобы [img: http://localhost:8080/file/031401-4.jpg] Любое число а, [img: http://localhost:8080/file/031401-5.jpg] однозначно характеризуется парой вычетов (a, b)по модулю п(цифрами по основанию пчисла а-1), т. е. точкой двумерного пространства [img: http://localhost:8080/file/031401-6.jpg] над кольцом [img: http://localhost:8080/file/031401-7.jpg] вычетов по модулю п. Поскольку координаты (i, j) клеток квадрата также можно считать элементами пространства [img: http://localhost:8080/file/031401-8.jpg] отсюда следует, что любое распределение чисел от 1 до n2 в квадратную [img: http://localhost:8080/file/031401-9.jpg] -таблицу [img: http://localhost:8080/file/031401-10.jpg] задается нек-рым отображением [img: http://localhost:8080/file/031401-11.jpg] т. е. парой функций [img: http://localhost:8080/file/031401-12.jpg] от [img: http://localhost:8080/file/031401-13.jpg] Задача состоит в исследовании таких пар, дающих М. к. В общем виде это сделано (см. [1]) только при дополнительном предположении линейности функций a и b. Оказалось, в частности, что М. к. с линейными функциями a и b существуют только при нечетных п. Уже в средние века был известен ряд алгоритмов построения М. к. нечетного порядка п. Каждый такой алгоритм характеризуется шестью вычетами [img: http://localhost:8080/file/031401-14.jpg] [img: http://localhost:8080/file/031401-15.jpg] и описывается следующими правилами: 1) число 1 вписывается в клетку (i0, j0); 2) если число авписана в клетку (i, j), то число a+1 вписывается в клетку (i+p, j+q), если эта клетка еще свободна от чисел, и в клетку [img: http://localhost:8080/file/031401-16.jpg] если клетка (i+p, j+q) занята. Вычеты [img: http://localhost:8080/file/031401-17.jpg] не могут быть произвольны, но должны удовлетворять определенным условиям, обеспечивающим не только выполнение условий (*), но и выполнимость алгоритма, т. е. пустоту клетки [img: http://localhost:8080/file/031401-18.jpg] если занята клетка (i+p, j+q). Эти условия легко находятся (см. [1] с. 41), причем оказывается, что М. к. тогда и только тогда может быть построен алгоритмом такого вида, когда описывающие этот квадрат функции а, Р линейны. Известно много других алгоритмов построения М. к. (приводящих к квадратам с нелинейными функциями а, Р), но никакой общей их теории нет (1982). Неизвестно даже общее число М. к. порядка n(при [img: http://localhost:8080/file/031401-19.jpg] для n=3 существует, с точностью до очевидных симметрии, только один М. к., а для n=4 число М. к. равно 880). Исследовались также М. к., обладающие дополнительными свойствами симметрии, Лишь опять в очень специальных ситуациях (напр., при [img: http://localhost:8080/file/031401-20.jpg] см. [2]).