Тридцать шесть проблем офицеров

Тридцать шесть проблем офицеров

Леонард Пауэль Эйлер (1707-1783), Гастон Тарри (1843-1913)

Рассмотрим шесть армейских полков, каждый из которых состоит из шести офицеров разных рангов.. В 1779 году Леонард Эйлер спросил, возможно ли организовать эти 36 офицеров в 6 х 6 квадратной матрицы так, что один офицер от каждой из шести полков появляется в каждой строке и по одному от каждой из шести рядах появляется в каждом столбце. На языке математики, эта задача эквивалентна нахождению двух взаимно ортогональных латинских квадратов порядка шести. Эйлер правильно предугадал, что не было никакого решения, и французский математик Гастон Тарри доказал это в 1901 году. В течение веков проблема привела к значительной работе в комбинаторике, области математики, касавшейся выбора и расположения объектов. Латинские квадраты также играют роль в исправляющих ошибку кодексах и коммуникациях.

Латинский квадрат состоит из n наборов чисел, от 1 до N, расположенных таким образом, что ни одна строка или столбец не содержит одинаковых два числа. Числа латинских квадратов, начиная с n=1: 1, 2, 12, 576,161,280, 812,851,200, 61,479,419,904,000, 108,776,032,459,082,956,800, и так далее.

Пара латинских квадратов называется ортогональным, если п2 пары формируется путем сопоставления двух различных матриц. (Противопоставление относится к сочетанию двух чисел в виде упорядоченной пары). Например, два ортогональных латинских квадратов порядка 3:

Эйлер предложил что, если n=4k+2, где k целое число, тогда никакая пара ортогональных n x n латинские квадраты не существует. Эта гипотеза не была решена более века, до 1959 года, когда математики Бозе, Шихэйнд и Паркер из 22 x 22 ортогональных латинских квадрата. Сегодня, мы знаем, что пара ортогональных n x n латинские квадраты существует для каждого положительного целого числа n кроме n = 2 и n = 6.

Дата добавления: 2015-09-29