Eulerjev problem 36 častnikov : delo diplomskega seminarja

Kranjec, Katja (avtor), 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.

• Jezik: Slovenski jezik
• Ključne besede: ortogonalni latinski kvadrati, grško-latinski kvadrati, ortogonalne tabele, transverzalni načrti
• Vrsta gradiva: Delo diplomskega seminarja/zaključno seminarsko delo/naloga
• Tipologija: 2.11 - Diplomsko delo
• Organizacija: FMF - Fakulteta za matematiko in fiziko
• Leto izida: 2023
• PID: 20.500.12556/RUL-150831
• UDK: 519.1
• COBISS.SI-ID: 165831171
• Datum objave v RUL: 24.09.2023

Sekundarni jezik

• Jezik: Angleški jezik
• Naslov: Euler’s 36 Officers Problem

Izvleček

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.

• Ključne besede: orthogonal latin squares, Graeco-Latin squares, orthogonal arrays, transversal designs