Головоломка «36 офицеров»
Эту головоломку, согласно легенде, предложила знаменитому математику Леонарду Эйлеру императрица Екатерина Великая.
«Среди 36 офицеров поровну уланов, драгунов, гусаров, кирасиров, кавалергардов и гренадеров и, кроме того, поровну генералов, полковников, майоров, капитанов, поручиков и подпоручиков, причем полк каждого из родов войск представлен офицерами всех шести рангов. Можно ли выстроить этих офицеров в каре 6×6 так, чтобы в любой колонне и любой шеренге встречались офицеры всех полков и всех рангов?»
Чтобы не путаться в непривычных воинских званиях, сформулируем попроще:
«Необходимо разместить 36 офицеров шести различных полков и шести различных воинских званий в квадрат так, чтобы в каждой колонне и в каждом ряду был ровно один офицер каждого полка и каждого воинского звания».
Попробуйте и вы придумать такую расстановку. Начните сначала, например, с квадрата 3×3, 4×4. Говорят, головоломка также легко решается, когда есть пять званий и пять полков, или семь званий и семь полков. Решения можете посмотреть ниже в статье.
Задача была сформулирована в 1779 году в мемуаре «Исследование магического квадрата нового типа» Петербургской Академии наук. Мемуар начинался с задачи «О 36 офицерах».
Академик Эйлер бился с этой задачей долго. Он сумел решить её для 25 офицеров. Но после безуспешных поисков решения для случая с 36 офицерами Эйлер пришёл к выводу, что «такое расположение невозможно, хотя мы и не можем дать строгого доказательства этого». Таким образом, возникла ещё одна математическая гипотеза.
В дальнейшем этой задачей занимались тысячи математиков. Только в 1959 году было доказано, что эта задача решается для любых квадратных чисел, больших, чем 2×2. Любых, кроме тридцати шести. (Математики использовали компьютеры, чтобы доказать, что решения существуют для любого количества полков и рангов больше двух, за исключением случая шести).
Латинские квадраты
Задача Эйлера о 36 офицерах положила начало изучению так называемых «латинских квадратов».
«Латинским квадратом» n-го порядка называется квадратная таблица n×n клеток, заполненная n различными элементами некоторого множества, причём в каждой строке и в каждом столбце каждый элемент встречается в точности один раз.
Леонард Эйлер использовал буквы латинского алфавита, откуда «латинские квадраты» и получили своё название (точнее, использовались греко-латинские квадраты).
Два латинских квадрата одного и того же порядка называются ортогональными, если при наложении их друг на друга все получившиеся пары букв оказываются различными. Их начал изучать Эйлер.
Задача Эйлера о 36 офицерах тоже требует «ортогонального латинского квадрата», в котором два набора свойств, таких как звания и полки, одновременно удовлетворяют правилам латинского квадрата.
Посмотрите, например, на решение задачи для случая 5×5, сформулированного для наглядности в шахматных фигурах. Таблица 5×5 может быть заполнена шахматными фигурами пяти разных рангов и пяти разных цветов.
А вот обобщение головоломки «36 офицеров» для рангов 1–7 (шахматные фигуры) и полков (цвета) — случаи 2 и 6 не имеют решений.
Квадраты, похожие на латинские, были упомянуты Жаком Озанамом ещё в 1725 году. В книге, представляющей собой сборник задач по математике и физике, приведена следующая задача: «Необходимо разместить 16 игральных карт из тузов, королей, дам и валетов всех четырёх мастей в виде квадрата так, чтобы все масти и карты всех достоинств встречались в каждой строке и в каждом столбце ровно один раз».
Эта задача имеет 6912 решений. Если дополнительно потребовать, чтобы и диагонали квадрата удовлетворяли тому же условию, то число решений уменьшится в 6 раз и станет равным 1152.
В 1920–1930 годы стали интенсивно изучаться неассоциативные алгебраические структуры. Это привело к созданию теории квазигрупп, тесно связанной с изучением латинских квадратов, так как между латинскими квадратами и таблицами Кэли квазигрупп существует взаимно-однозначное соответствие.
Новая эра этой головоломки началась в 2016 году, когда в Кембриджском университета пришли к неожиданной идее, что записи в латинских квадратах можно сделать квантовыми (квантовые латинские квадраты).
Латинские квадраты находят широкое применение в алгебре, комбинаторике, статистике, криптографии, теории игр и теории кодирования. Но, пожалуй, наиболее известным большинству применением латинских квадратов является игра судоку.
Список литературы
- Баврин И. И., Фрибус Е. А. Старинные задачи: Кн. для учащихся. — М.: Просвещение, 1994. — 128 с.
- Малых А. Е., Каленкова А. С. Исследование Л. Эйлером магических квадратов // Сб. док. всеросс. науч.-практ. конф. молодых учёных с междунар. участием «Математика и междисциплинарные исследования — 2016» (г. Пермь, 16−19 мая 2016). — Пермь, ПГНИУ, 2016. — С. 30−34.
- Euler L. Recherches sur une nouvelle espece de quarres maqicues. — Verh. Zeeuwsch. Genootsch. Wetensch. Vlissengen., 1782. — Vol. 9. — P. 85–239.
- Малых А. Е. О создании Эйлером комбинаторной теории латинских квадратов // ИМИ. — М.: Наука, 1983. — Вып. XXVII. — С. 102–123.
- Tarry G. Le problème des 36 officiers // C.R. Assoc. France Av. Sci. — 1900. — V.29. — N.2. — P. 170–203.
- Bose R. C., Nair K. R. On complete sets of Latin squares // Sankhya. — 1941. — V.5. — Part 4. — P. 361–382.