20. Магические квадраты

Покажем теперь примеры решения комбинаторных проблем. Начнем с той самой задачи, которую несколько тысяч лет тому назад решили китайские математики.

РасположитЬ числа 1, 2, 3, 4, 5, 6, 7, 8, 9 В виде квадрата так, чтобы сумма чисел по каждому столбцу, строке и диагонали была одной и той же.

Методом прямого перебора решить эту задачу невозможно — 9 чисел можНО расположить в виде квадрата 362 880 способами. Поэтому проведем Математический Анализ задачи. Выясним сначала, какой должна Быть иСкомая сумма. Так как

1+2+3+4+5+6+7+8+9=45,

То в каждой из 3 строк сумма чисел должна равняться 15. Это значительно уменьшает необходимый перебор — выбрать 3 слагаемых из данных чисел так, чтобы их сумма равНЯлась 15, можно лишь 8 способами: (9, 2, 4), (9, 5, 1), (8, 6, 1), (8, 5, 2), (8, 4, 3), (7, 6, 2), (7, 5, 3) (6, 5, 4). А число строк, столбцов и диагоналей в квадрате тоже равно 8. Значит, каждая из написанных комбинаций должна ровно один раз войти в искомый квадрат. Далее замечаем, что только число 5 входит в Эти Тройки 4 раза. Поэтому оно и должно стоять в центре таблицы на пересечении центральных строки, столбца и двух диагоналей. Числа 8, 2, 6 и 4, входящие в тройки по 3 раза, должны занять углы — они стоят на пересечении строки, СТолбца И ДИагонали. Оставшиеся числа 1, 3, 7, 9 занимают места сверху, снизу, слева и СпраВa от центра. Диагональные тройки (8, 5, 2) и (6, 5, 4) можно расположить 8 различными способами (у нас 2 диагонали, на каждой из которых можно еще переставлять крайние элементы). После выбора положения чисел 8, 2, 6, 4 положение остальных чисел одНОзначно определено. Мы не только нашли одни магический квадрат 3-го порядка, но и описали все такие квадраты иЗ чИсел 1, 2, 3, 4, 5, 6, 7, 8, 9.

Эта задача, разумеется, очень проста. Гораздо труднее найти все магические квадраты 4-го порядка. Один Из магических квадратов 4-го порядка можно получить из обычного квадрата

ЕслИ на каждой его большой диагонали помеНЯть местамИ числа, симметричНЫе относительно цеНТра квадрата, т. е. числа 1 и 16, 6 и 11, 4 и 13, 7 и 10. В результате получим

В том, что получеННый квадрат 4-го порядка магичЕСкИЙ, читатель легко убедится самостоятельно.

Еще более замечателЬнЫм является магический квадрат 4-го порядка, найденный в индИЙской надписи XI или XII вв. н. э.:

Этот квадрат сохраняет свойство быть магическим и после ТОго, как его строки одна за другой перемещаются сверху вниз (сначала первая под четвертой, затем вторая под бывшей первой и т. д.) или столбцы аналогично перемеЩаются слева направо. Иными словами, если сделать ковер из таких квадратов, то, вырезав его любую часть из 4 строк и 4 столбцов, получаем снова магичесКИ квадрат.

Всего существует 880 типов магических квадратов 4-го порядка.

Существуют методы построения магических квадратов и более высокого порядка. Такими построениями занимались один из основателей теориИ чисел П. Ферма, ВыДающийся английский математик А. Кели, известный современный математик О. Веблен. Удалось построить, например, магические квадраты, которые после удаления нескольких крайних полос снова дают магические Квадраты, магические кубы, в которых все квадратные грани параллельные паре боковых граней, ПРедставляют магиЧеские квадраты с одной и той же суммой и т. д.

< Предыдущая		Следующая >