Приветствую Вас, уважаемые Читатели! Сегодня хочу поговорить еще об одном важном математическом объекте, к изучению которого приложил руку Леонард Эйлер. Речь пойдет о латинских квадратах, тесно связанных с комбинаторикой и теорией шифрования. Поехали!
Итак, латинским квадратом n-ного порядка называется таблица, заполненная таким образом n элементами некоторого множества М, что в каждой строке и каждом столбце элементы этого множества встречаются только раз. В настоящее время принято в качестве множества М применять натуральные числа, но сначала Леонард Эйлер использовал для этого латинские буквы. Вот пример латинского квадрата 3-го порядка.
Латинские квадраты впервые описал в 1200 году арабский математик Ахмад аль-Буни, но главная заслуга принадлежит, естественно, Эйлеру. Например, он сформулировал знаменитую задачу о 36 офицерах:
Cреди 36 офицеров поровну уланов, драгунов, гусаров, кирасиров, кавалергардов, гренадеров и, кроме того, поровну генералов, полковников, майоров, капитанов, поручиков и подпоручиков, причем каждый род войск представлен офицерами шести рангов. Можно ли выстроить этих офицеров в каре так, чтобы в любой колонке и любой шеренге встречались офицеры всех рангов всех родов войск?
Эта задача эквивалентна построению двух ортогональных латинских квадратов порядка 6. Эйлер предположил, но не смог доказать, что такие квадраты построить нельзя, и только через 118 лет француз Г. Тарри, проанализировав все такие квадраты (кстати, 9408 штук), показал невозможность решения этой задачи. Вы представляете, только для 2-го и 6-го порядка это невозможно! Вот уж где чудо!
Эйлер, к слову, так же считал, что пару ортогональных квадратов порядка 10 и 22 так же невозможно построить. Лишь через 177 лет уже с помощью ЭВМ эта гипотеза была опровергнута. Максимальным успехом на данный момент является нахождение 5 попарно ортогональных квадратов 12-го порядка.
Точная формула количества латинских квадратов порядка n неизвестна. Подсчитаны только точные значения до 11-го порядка. Для него, кстати, имеется 776966836171770144107444346734230682311065600000 латинских квадратов.
Латинские квадраты находят широкое применение в алгебре, комбинаторике, статистике, криптографии, теории кодов и многих других областях, но наиболее известным всем Вам применением латинских квадратов является игра судоку!
Фактически, в судоку требуется дополнить произвольную таблицу до латинского квадрата 9-го порядка, обладающего дополнительным свойством: каждый из его подквадратов 3-го порядка содержат по одному разу цифры от 1 до 9.
Читайте также:
- Итоги 2020 года в цифрах