마방진 뒷 이야기 16: 직교 라틴 방진 (Orthogonal Latin Square)

상당히 어렵게 느껴지는 용어이지요?
퍼즐러 갱이 생각해도 너무 수학적이고 현학적인 표현 같습니다.
덜컥 겁부터 나는 것이 사실입니다.

그러나 라틴 방진과 최석정의 9차 마방진을 정리하면서 직교 라틴 방진이 참 의미있는 개념인 것 같아서 나름 정리를 해 보았습니다.
(직교 라틴 방진(Orthogonal Latin Square), 그레코-라틴 방진(Graeco-Latin Square), 오일러 방진(Euler Square) 은 모두 같은 개념입니다.)

1. 직교 라틴 방진이란?
직교 라틴 방진을 이해하기 위해서는 먼저 라틴 방진을 이해해야 합니다.
라틴 방진이란 문자나 숫자를 쓰되 각 행이나 열에 딱 한번만 들어가도록 해서 만든 방진입니다.
예를 들어 4차 라틴 방진이라고 하면 1, 2, 3, 4나 아무런 기호 4가지를 가지고서 각 행과 열에 숫자나 기호가 중복됨이 없이 기입하여야 한다는 뜻입니다.
자세한 내용은 예전에 포스팅한 '마방진 뒷 이야기 14: 라틴 마방진 (Latin Magic Square)' 글을 참조하십시요.
한번 해보면 알겠지만 쉬운 듯 하면서도 어렵고, 어려운 듯 하면서도 쉽습니다.^^

직교 라틴 방진이란 라틴 방진 두개를 하나의 방진으로 포개놓았을 때 각 칸(셀)에 들어가는 숫자나 기호가 그 숫자나 기호가 만들어 낼 수 있는 모든 순서쌍을 나타낼 경우에 사용되는 말입니다.
즉, 만일 4차 라틴 방진이면서 숫자를 사용했다고 가정하면,
(1,1), (1, 2), (1, 3), (1, 4), (2, 1), (2, 2), (2, 3), (2, 4), (3, 1), (3, 2), (3, 3), (3, 4), (4, 1), (4, 2), (4, 3), (4, 4)와 같은 모든 경우의 수를 표현해 내고 있을 때 두개의 라틴 방진은 서로 직교한다고 표현합니다. 
즉, N차 라틴 방진의 경우 N^2(N의 제곱) 개의 순서쌍이 모두 나타날 경우에 서로 직교하는 것이지요.
그리고 이 두개의 라틴 방진을 가리켜 직교 라틴 방진이라고 합니다. 물론 두개의 라틴 방진을 포개어 놓았을 때의 방진을 가리키기도 합니다.

2. 36 장교 문제 (36 Officers Problem)
직교 라틴 방진 관련해서 매우 유명한 문제입니다.
수학계의 그 유명한 오일러가 출제한 문제입니다.
즉, 6개의 군부대에서 각각 6명씩의 장교를 차출합니다. 그런데 각 부대에서 소위부터 대령까지 계급이 모두 다른 6명의 장교를 차출합니다. 그리하여 총합 36명의 장교를 차출하여 연병장에 모았습니다. 그리고 이 장교들을 6열 종대로 세우려고 하는데 조건은 각 열 각 행에 모든 계급과 모든 출신 부대가 골고루 섞이도록 해야 하는 것입니다. 행이나 열에 계급이나 출신 부대가 같은 경우가 발생하면 미션 실패입니다.

자 여러분 시간나면 한번 풀어보시죠~~

그런데 시간 낭비할 필요가 없답니다.
이 문제에 대한 해법은 존재하지 않기 때문입니다.
이것은 이미 증명이 된 사항입니다.

이 문제가 지니는 의미는 바로 6차 직교 라틴 방진은 만들 수가 없다는 의미입니다.
오일러는 (4N+2)차 직교 라틴 방진을 풀지 못하고 나름대로 그 이유를 증명하지는 못한 상태에서 1782년에 4N+2차 직교 라틴 방진은 존재하지 않을 것이라는 추정(Conjecture)을 하게 됩니다.

이러한 추정이 있은 뒤 개스통 태리(Gaston Tarry)가 1901년에 6차 직교라틴방진은 존재하지 않는다는 사실을 증명하게 됩니다.
이 사실을 증명하기 위해서 개스통 태리는 모든 가능한 경우를 죄다 조사하는 방법을 택했습니다.

그리고 1958년에 보스 (Raj Chandra Bose) 와 Shrikhanle 가 두 개의 22차 직교라틴방진을 만들어 보임으로써 오일러의 추측이 틀렸다는 것이 판명됩니다.

1959년도에는 E. Parker 가 10차 직교 라틴 방진을 찾아냅니다.
오일러의 추측이 멋지게 빗나간 것이죠.
바로 아래의 직교 라틴 방진이 10차 직교 라틴 방진입니다.
겉으로 보기에는 평범해 보이지만 200여년간 풀리지 않던 10차 직교라틴방진입니다. 

위 그림을 보면 가로 세로 모두 동일한 바탕색을 지니는 것이 발견되지 않습니다. 아울러 안의 조그만 네모의 색깔이 동일한 것도 없습니다. 10*10 = 100. 100가지의 모든 경우가 가로 세로 겹치지 않으면서 골고루 존재합니다. 

아울러 1960년에 Bose와 Shrikhanle 와 Parker 는 2차와 6차를 제외한 4N +2 차 직교라틴방진이 존재한다는 논문을 발표함으로써 오일러의 추정이 틀렸음을 증명합니다.
즉, 14차, 18차 그리고 그 이상의 4N+2차 직교라틴 방진이 존재한다는 것을 증명한 것입니다. 

물론 그럼에도 불구하고 6차 직교 라틴 방진은 여전히 존재하지 않는 것으로 나타났습니다.

3. 직교라틴방진의 의의
직교라틴 방진이 중요한 이유는 바로 직교라틴 방진을 통해서 N차 마방진을 만들어 낼 수가 있기 때문입니다.

먼저 3차 직교라틴 방진으로부터 3차 마방진을 생성하는 것을 보여드리겠습니다. 

왼쪽 두개의 방진은 모두 각각 라틴 방진입니다.
이 두 개의 라틴 방진은 서로 직교합니다. 즉 직교 라틴 방진인 것이죠.
이 직교라틴방진을 하나의 방진에 표현해 보면 맨 우측의 방진이 됩니다.
파란색은 첫번째 라틴 방진을, 빨간색은 두번째 라틴 방진을 의미합니다.
이 직교라틴 방진을 가지고서 단순한 변환 작업을 하면 3차 마방진이 생성됩니다.

위에서 보듯이 3차 직교 라틴 방진에서 3(A-1)+B를 하면 3차 마방진이 생성됩니다.
(파란색 A는 직교라틴 방진에서 첫번째 파란색 숫자를, B는 두번째 빨간색 숫자를 의미합니다.)

다음은 4차 직교라틴 방진으로부터 4차 마방진을 생성하는 것을 보여드리겠습니다.
기본적인 흐름은 위의 3차 직교라틴 방진과 동일합니다.

다만 아래의 표에서 볼 수 있듯이 변환 작업을 할 때 곱해 주는 수만 차이가 있습니다.

5차 직교라틴 방진으로부터 5차 마방진을 생성하는 것을 보여드리겠습니다.

위에서 보면 차수가 올라갈 때마다 마방진을 생성하는 산식에서 숫자가 각 차수에 맞게 올라가고 있음을 여러분은 눈치챘을 것입니다.

그런데 위의 직교라틴 방진의 원본 라틴 방진을 보면 모두 라틴 마방진인 것임을 알 수 있습니다.
즉 가로 세로뿐 아니라 대각선 방향에서도 동일한 숫자가 나타나지 않는 라틴 방진, 즉 라틴 마방진인 것입니다.
이것을 수학적으로 Self-Orthogonal Latin Square 라고 하더군요. 또 어디에서는 Latin Diagonal Square 라고도 합디다.

그런데 퍼즐러 갱이 시도해 본 결과 모든 직교 라틴 방진에서 마방진이 모두 생성이 되는 것은 아니었습니다. 직교라틴방진으로 하나의 마방진을 만들때 가로 세로의 합은 모두 동일하지만 대각선에서 유독 다른 숫자가 나오는 방진이 형성되는 경우가 많더군요.

어떤 직교라틴방진을 이용해야 정식 마방진이 형성되는지 퍼즐러 갱 아직 모릅니다. 혹시 아시는 분 있으시면 쪼메 알려주시지요.

4. 최석정의 9차 직교 라틴 방진
우리의 자랑스러운 선조이신 최석정은 9차 직교 라틴 방진을 구수략이라는 책자에 실었습니다. 그리고 본인이 직접 새로 만들었다는 표현도 가미했습니다.
물론 그 9차 직교라틴방진으로 완전 순수 진짜 9차 마방진을 형성할 수 있는 것은 당근에 말밥이구요.
이 내용에 대해서는 예전 포스트인 '마방진 뒷 이야기 15: 최석정의 마방진' 글을 참조하시지요.

중요한 점은 오일러의 36 장교 문제가 나오기 훨씬 이전에 직교라틴방진 개념을 이해하고 있었다는 점입니다.

오늘도 해피 퍼즐링~~

(관련 포스트)
- 라틴 방진: 마방진 뒷 이야기 14: 라틴 마방진 (Latin Magic Square)
- 최석정 마방진: 마방진 뒷 이야기 15: 최석정의 마방진

 

*아래 화면은 퍼즐러갱이 개설한 유튜브 '퍼즐러갱TV'의 초기화면입니다. 아래 그림을 클릭/터치하여 퍼즐러갱TV를 감상해 보시지요(구독과 좋아요는 저에게 큰 힘을 줍니다)!!