Eulerjev problem 36 častnikov : delo diplomskega seminarja

Kranjec, Katja (author), Vavpetič, Aleš (mentor)

Latinski kvadrat reda $n$ je tabela velikosti $n \times n$, sestavljena iz elementov množice moči $n$, v kateri je vsak od elementov zastopan v vsaki vrstici in v vsakem stolpcu. Dva latinska kvadrata reda $n$ sta ortogonalna, če njuna superpozicija tvori same različne urejene pare. Nastalemu kvadratu rečemo grško-latinski kvadrat reda $n$. Eulerjev problem $36$ častnikov, ki se sprašuje, ali je možno razporediti $36$ častnikov iz šestih različnih regimentov in šestih različnih činov, v formacijo $6 \times 6$, tako da je v vsaki vrsti in vsaki koloni zastopan vsak regiment in vsak čin, je potem enak vprašanju obstoja grško-latinskega kvadrata reda šest. Tega lahko prevedemo v vprašanje obstoja transverzalnega načrta $TD(4, 6)$, za katerega lažje dokažemo, da ne obstaja. Grško-latinske kvadrate lihih redov znamo enostavno konstruirati, prav tako poznamo kvadrata reda štiri in osem. Dejstvo, da iz dveh grško-latinskih kvadratov redov $n_1$ in $n_2$ dobimo grško-latinski kvadrat reda $n_1 \times n_2$, pa nam pomaga konstruirati še kvadrate višjih redov oblike $n \not\equiv 2\pmod{4}$. Euler je domneval, da grško-latinski kvadrati preostalih redov ne obstajajo, vendar je bila njegova domneva ovržena skoraj dvesto let kasneje. Dva načina konstrukcije takih kvadratov sta s pomočjo ortogonalnih tabel in Wilsonove konstrukcije.

• Language: Slovenian
• Keywords: ortogonalni latinski kvadrati, grško-latinski kvadrati, ortogonalne tabele, transverzalni načrti
• Work type: Final seminar paper
• Typology: 2.11 - Undergraduate Thesis
• Organization: FMF - Faculty of Mathematics and Physics
• Year: 2023
• PID: 20.500.12556/RUL-150831
• UDC: 519.1
• COBISS.SI-ID: 165831171
• Publication date in RUL: 24.09.2023

Secondary language

• Language: English
• Title: Euler’s 36 Officers Problem

Abstract

A Latin square of order $n$ is an $n \times n$ array of elements from a set of size $n$ in which each element occurs in every row and every column. Two Latin squares of order $n$ are orthogonal if their superposition yields unique ordered pairs. The resulting square is then called a Graeco-Latin square of order $n$. Euler’s $36$ Officers Problem which poses a question if it is possible to arrange $36$ officers of six different regiments and of six different ranks in a formation $6 \times 6$ where each row and each file contains one officer of each regiment and one of each rank, is equal to the question of existence of Graeco-Latin square of order six. In design theory this question translates to the question of existence of a transversal design $TD(4, 6)$ the non-existence of which is easier to prove. Graeco-Latin squares of odd orders are easy to construct as well as squares of orders four and eight. The fact that a Graeco-Latin square of order $n_1 \times n_2$ can be constructed from two Graeco-Latin squares of orders $n_1$ and $n_2$ helps us construct squares of higher orders $n$ where $n \not\equiv 2\pmod{4}$. Euler conjectured that there exist no Graeco-Latin squares of other orders which was disproven almost two hundred years later. Two ways of constructing such squares are using orthogonal tables and Wilson’s construction.

• Keywords: orthogonal latin squares, Graeco-Latin squares, orthogonal arrays, transversal designs