라틴방진(Latin Square)은 마방진의 일종으로 N차 정사각 행렬 중 가로/세로로 N개의 숫자나 객채를 하나씩 배열한 방진을 말한다. 라틴방진이라는 이름은 레오나르트 오일러(1707~1783)의 논문에서 라틴 문자를 사용한 정사각 방진에서 유래한다.
역사
라틴방진은 최석정의 구수략에 9×9 직교 라틴방진 형태로 나와있는데, 이는 오일러의 논문보다 무려 67년이나 더 전에 기록된 것이다. [1]
이후 레온하르트 오일러는 1782년에 6개의 군부대에서 각각 서로 계급이 다른 6명의 장교를 6×6 정사각배열로 배치했을 때 같은 행/열에 계급이랑 부대가 모두 다르게 배치하는 36장교 문제를 제시하면서 답이 존재하지 않을 것이라고 추측했고, 결국 1901년 개스톤 테리가 6×6 직교 라틴방진이 존재하지 않음을 보이면서 해결되었다. 그러나 오일러가 n=4N+2에서 직교 라틴방진이 존재하지 않을 것이라고 추측한 것과는 달리 n=10, 14 등 더 큰 수에 대해서는 직교 라틴방진이 존재함이 밝혀졌다.
라틴방진의 직교
두 라틴방진의 행렬 A=(aij), B=(bij)에 대해서 aij=k인 i,j를 모을 때 {bij}가 1부터 n까지 하나씩 들어가 있게 되는 경우 두 라틴방진 A와 B는 직교(orthogonal)한다고 말한다.
직교 라틴방진과 마방진
서로 직교하는 n차 라틴방진 A, B에 대해서 좌표행렬 ((aij,bij)는 (1,1)부터 (n,n)까지의 격자점 n2개가 하나씩 모인 형태가 되고, 다라서 행렬 ((n-1)aij+bij)은 1부터 n2까지의 원소로 구성된 준마방진이 된다. 아래는 3×3 직교 라틴방진 둘로 마방진을 만드는 과정을 표현한 것이다.
1 | 3 | 2 | × | 2 | 3 | 1 | → | 2 | 9 | 4 |
3 | 2 | 1 | 1 | 2 | 3 | 7 | 5 | 3 | ||
2 | 1 | 3 | 3 | 1 | 2 | 6 | 1 | 8 |
최석정의 구수략에서
최석정의 구수략에 나타난 직교 라틴방진. 위쪽의 수로 이루어진 방진과 아래쪽의 수로 이루어진 라틴 방진이 서로 직교한다. [2]
5 1 |
6 3 |
4 2 |
8 7 |
9 9 |
7 8 |
2 4 |
3 6 |
1 5 |
4 3 |
5 2 |
6 1 |
7 9 |
8 8 |
9 7 |
1 6 |
2 5 |
3 4 |
6 2 |
4 1 |
5 3 |
9 8 |
7 7 |
8 9 |
3 5 |
1 4 |
2 6 |
2 7 |
3 9 |
1 8 |
5 4 |
6 6 |
4 5 |
8 1 |
9 3 |
7 2 |
1 9 |
2 8 |
3 7 |
4 6 |
5 5 |
6 4 |
7 3 |
8 2 |
9 1 |
3 8 |
1 7 |
2 9 |
6 5 |
4 4 |
5 6 |
9 2 |
7 1 |
8 3 |
8 4 |
9 6 |
7 5 |
2 1 |
3 3 |
1 2 |
5 7 |
6 9 |
4 8 |
7 6 |
8 5 |
9 4 |
1 3 |
2 2 |
3 1 |
4 9 |
5 8 |
6 7 |
9 5 |
7 4 |
8 6 |
3 2 |
1 1 |
2 3 |
6 8 |
4 7 |
5 9 |
참조
각주
- ↑ Colbourn, Chalres J., Dinitz, Jeffrey H.. 《Handbook of Combinatorial Designs》, 2판 (en), CRC Press. ISBN 9781420010541
- ↑ 참조 : #