그레코-라틴 방진

 

라틴방진(latin square)

라틴방진은 행, 열 각각에 $1$부터 $n$까지의 숫자가 겹치지 않게 배열되어 있는 것, 즉 순열(permutation)로 이루어진 것이다. 스도쿠 게임을 생각하면 쉽게 이해할 수 있다. 스도쿠는 9차 라틴방진을 만드는데 9개로 나뉜 작은 방진에도 1~9까지 숫자를 넣어야 하는 조건이 강화된 라틴방진이다.

 

직교라틴방진(orthogonal latin square) 

라틴방진 중에서 이러한 배열 두 쌍을 결합시켰을 때에도 겹치는 숫자쌍이 없는 두 쌍의 라틴방진을 직교라틴방진이라 한다.

오일러는 직교라틴방진을 연구할 때 그리스문자와 로마문자를 써서 나타냈다. 직교라틴방진을 그레코-라틴방진(Graeco-Latin square) 또는 오일러 방진으로 부르기도 한다. 아래는 3차, 4차, 5차의 크레코-라틴방진이다.

이제까지 많은 이의 호기심을 자극하는 다음 문제를 해결하기 위해 연구에 참여하게 되었다. 이 연구로 새로운 해석 분야인 조합론이 열리게 되는 듯하다. 문제는 6개의 서로 다른 연대에서 뽑은 36명의 장교를 배열하여 각 라인(수평 및 수직 모두)에 서로 다른 계급과 연대의 6명의 장교가 있도록 정사각형에 배치하는 것이다. — 레온하르트 오일러

오일러의 추측과 반증

오일러는 이 문제를 풀 수 없었지만, 차수인 $n$이 홀수이거나 $4$의 배수인 그리스-라틴방진을 만드는 방법을 보였다. 오일러는 2차 방진이 존재하지 않고 6차 방진을 찾을 수 없었으므로 $n ≡ 2(mod 4)$인 $n$차 직교라틴방진은 존재하지 않을 것이라고 추측했다. 1901년 가스톤(Gaston Tarry)은 일일이 찾아보는 소진법으로 6차 방진이 존재하지 않음을 증명했다.

오일러의 추측은 1950년대 후반까지 해결되지 않았지만, 이 문제는 조합론에서 중요한 작업으로 이어졌다. 1959년 보세(R.C. Bose)와 슬릭 한데(S. S. Shrikhande)는 수학적 통찰로 22차의 몇 가지 반례를 찾았다. 그런 다음 파커(E. T. Parker)는 레밍턴 랜드(Remington Rand)의 UNIVAC 부서에서 근무하는 동안 군용 컴퓨터인 UNIVAC 1206에서 1시간 동안 컴퓨터 검색을 사용하여 10차의 직교라틴방진을 발견했다. 이는 디지털 컴퓨터로 해결한 최초의 조합 문제이다.

1959년 4월 Parker, Bose, Shrikhande는 모든 $n≥10$에 대해 오일러의 추측이 거짓임을 보여주는 논문을 발표했다. 그레코-라틴 방진은 $n = 2, 6$을 제외한 모든 차수 $n > 1$에 대해 존재한다. 1959년 마틴 가드너(Martin Gardner)는 '사이언티픽 아메리칸' 11월 호에  결과를 발표했다. 앞표지에 아래 그림과 같은 10차 직교라틴방진을 넣었다.

더 흥미로운 이야기가 이어지지만 몹시 귀찮아서 여기까지만 옮겨둔다.

활용

아래 그림은 배경색, 전경색, 텍스트와 글꼴이 모두 직교라틴방진을 이루고 있는 배열이다.

• 배경색: black, maroon, teal, navy, silver
• 전경색: white, red, lime, blue, yellow 
• 텍스트: fjords, jawbox, phlegm, qiviut, zincky
• 글꼴: serif, sans-serif, slab-serif, cursive, monospaced.

https://en.wikipedia.org/wiki/Mutually_orthogonal_Latin_squares

Mutually orthogonal Latin squares - Wikipedia