라틴 방진(Latin square)

네 사람이 네 요일 동안 네 가지 당번(청소, 설거지, 장보기, 빨래)을 돌아가며 맡는다고 합시다. 누구도 같은 당번을 두 번 하지 않고, 어느 요일에도 같은 당번이 두 사람에게 겹치지 않게 하려면 사람을 가로줄, 요일을 세로줄로 둔 4 × 4 표에 당번을 채우면 됩니다. 이렇게 n × n 칸에 n가지 기호를 채우되 모든 가로줄과 세로줄에 기호마다 꼭 한 번씩 나오게 한 표를 라틴 방진이라 합니다. 각 가로줄과 세로줄은 n가지 기호의 순열⁠(permutation)⁠입니다. 이름은 1782년 레온하르트 오일러가 기호로 라틴 문자를 쓴 데서 왔습니다.

직접 채워 보세요. 크기는 이고, 칸을 누르면 기호가 1, 2, …, n, 빈칸 순으로 바뀝니다. 비우기 돌려 채우기 섞기

라틴 방진은 어떤 크기든 반드시 있습니다. 가장 쉬운 방법이 '돌려 채우기'로, i행 j열(0부터 셉니다)에 $(i + j) \bmod n$, 곧 i + j를 n으로 나눈 나머지⁠(remainder)⁠에 해당하는 기호를 넣는 것입니다(모듈러 연산⁠(modular arithmetic)⁠). 한 줄을 내려갈 때마다 윗줄을 한 칸씩 밀어 쓰는 셈이라 가로줄과 세로줄마다 기호가 한 번씩 돕니다. 이것은 n시간짜리 시계의 덧셈표이기도 합니다. 일반적으로 어떤 군이든 그 곱셈표는 라틴 방진입니다. ab = ac이면 b = c라서 한 줄에 같은 값이 두 번 나올 수 없기 때문입니다. '섞기'는 돌려 채운 표의 가로줄끼리, 세로줄끼리, 기호끼리 순서를 무작위로 바꿉니다. 이런 바꾸기는 라틴 방진을 라틴 방진으로 보냅니다.

라틴 방진의 수는 빠르게 늘어납니다. 1 × 1부터 차례로 1, 2, 12, 576, 161,280개이고, 9 × 9는 약 5.5 × 10²⁷개입니다. 몇 칸을 미리 채워 두고 나머지를 채우는 문제는 어려울 수 있습니다. 1984년 찰스 콜번은 부분적으로 채운 라틴 방진을 완성할 수 있는지 판단하는 문제가 NP-완전⁠(NP-complete)⁠, 곧 답을 확인하기는 쉽지만 찾는 빠른 방법은 알려져 있지 않은 문제들 가운데 가장 어려운 부류임을 보였습니다(P 대 NP 문제⁠(P versus NP problem)⁠). 반면 몇 개의 가로줄을 빈칸 없이 채워 두었다면(각 세로줄에 겹침이 없게) 남은 줄은 언제나 채울 수 있습니다. 다음 줄은 칸마다 '그 세로줄에 아직 안 나온 기호'를 하나씩 서로 다르게 고르는 일이고, 홀의 정리⁠(Hall's theorem)⁠가 그런 고르기가 늘 가능함을 보장합니다.

36명의 장교. 오일러가 1782년 논문에서 던진 문제는 이렇습니다. 여섯 연대에서 여섯 계급(대령, 중령, 소령, 대위, 중위, 소위)의 장교를 한 명씩, 모두 36명을 6 × 6으로 세우되 가로줄과 세로줄마다 연대도 계급도 겹치지 않게 할 수 있을까? 연대만 보면 라틴 방진이고 계급만 보아도 라틴 방진이며, 두 표를 겹치면 (연대, 계급)의 36가지 짝이 모두 꼭 한 번씩 나와야 합니다(같은 연대, 같은 계급의 장교는 한 명뿐이니까요). 이런 두 라틴 방진을 서로 직교한다고 합니다. 아래는 연대를 색, 계급을 글자로 적은 표입니다. 연대는 돌려 채우기 $L = (i + j) \bmod n$이고, 계급은 $M = (i + kj) \bmod n$입니다. n = , k = .

규칙은 이렇습니다. 계급 표가 라틴 방진이려면 한 가로줄의 값 $kj \bmod n$이 모두 달라야 하니 k와 n이 서로소여야 합니다. 두 칸 (i, j)와 (i′, j′)의 짝이 같다면 $\Delta i + \Delta j \equiv 0$과 $\Delta i + k\Delta j \equiv 0$에서 $(k-1)\Delta j \equiv 0 \pmod n$이 나오므로, 짝이 모두 다르려면 k − 1과 n이 서로소여야 합니다. k = 0이면 짝은 모두 다르지만 계급 표의 가로줄이 한 계급으로만 채워져 라틴 방진이 아닙니다. n이 홀수이면 k = 2가 두 조건을 다 채우고, n이 소수⁠(prime number)⁠이면 2부터 n − 1까지 어느 k든 됩니다. 그러나 n이 짝수이면 k와 k − 1 가운데 하나는 짝수라서 이 방법은 언제나 실패합니다. 방법이 실패한다고 답이 없는 것은 아닙니다. 4 × 4와 8 × 8에서는 원소⁠(element)⁠가 4개, 8개인 유한체(보통의 수처럼 덧셈, 뺄셈, 곱셈, 0이 아닌 수로의 나눗셈이 다 되는 유한한 수 체계⁠(number system)⁠)로 같은 식을 계산하면 직교하는 짝이 만들어집니다.

오일러는 6 × 6에는 직교하는 짝이 없다고 짐작했고, 더 나아가 4로 나눈 나머지가 2인 모든 n(6, 10, 14, …)에서 없다고 추측했습니다. 앞의 것은 1900–1901년 프랑스의 아마추어 수학자 가스통 타리가 6 × 6 라틴 방진을 종류별로 모두 따져 옳음을 확인했습니다. 뒤의 것은 틀렸습니다. 1959년 인도의 R. C. 보스와 S. S. 슈리칸데가 22 × 22에서, 미국의 E. T. 파커가 10 × 10에서 직교 짝을 찾아 추측을 깼고, 1960년 세 사람은 2와 6을 뺀 모든 n에 직교 짝이 있음을 함께 증명했습니다. 신문은 이들을 '오일러를 망친 사람들'이라 불렀습니다.

최석정의 9 × 9 방진. 오일러보다 반세기 넘게 앞선 1700년 무렵, 조선의 영의정 최석정은 산학서 『구수략』에 9 × 9 칸마다 두 수를 겹쳐 적은 방진을 실었습니다. 앞자리만 보아도, 뒷자리만 보아도 라틴 방진이고, 두 자리를 겹치면 81가지 짝이 모두 한 번씩 나옵니다. 9 × 9 직교 라틴 방진⁠(orthogonal Latin squares)⁠으로는 알려진 가장 이른 예로 꼽히며, 최석정의 페이지에서 그 구조를 직접 만져 볼 수 있습니다(조선의 산학). 직교하는 두 방진은 곧바로 마방진⁠(magic square)⁠에 가까운 표가 됩니다. 기호를 1부터 n까지로 적고 짝 (a, b)를 수 $n(a - 1) + b$로 바꾸면, 짝이 모두 다르니 1부터 n²까지의 수가 한 번씩 들어갑니다. 또 한 줄에 a와 b가 각각 1부터 n까지 한 번씩 나오니 가로줄과 세로줄의 합이 모두 같아집니다. 대각선의 합까지 같게 하려면 대각선에서도 기호가 겹치지 않는 방진을 골라야 합니다.

밭에서의 실험. 1920년대 영국 로담스테드 농업 시험장의 로널드 피셔는 라틴 방진을 실험 설계에 들였습니다(골턴 연구소와 로담스테드). 비료 다섯 가지를 비교하려고 밭을 5 × 5 구획으로 나누면, 흙의 비옥도가 북쪽에서 남쪽으로도, 동쪽에서 서쪽으로도 달라질 수 있습니다. 비료를 라틴 방진대로 배치하면 모든 비료가 모든 가로줄과 세로줄에 한 번씩 놓입니다. 그래서 비옥도가 '가로줄의 몫 + 세로줄의 몫'처럼 두 방향의 효과를 더한 꼴로 달라지는 한, 그 차이가 모든 비료에 고르게 나뉘어 비료의 효과와 뒤섞이지 않습니다(교란 변수⁠, confounding variable⁠). 피셔는 여기에 한 가지를 더 요구했습니다. 가능한 라틴 방진들 가운데 하나를 무작위로 골라 쓰라는 것입니다. 그래야 예상하지 못한 치우침까지 우연에 맡겨 끊고, 결과가 우연인지 따지는 확률⁠(probability)⁠의 근거를 얻습니다(무작위 대조 시험⁠(randomized controlled trial)⁠). 오늘날에도 순서의 영향이 있는 시험, 예컨대 참가자마다 네 가지 약을 서로 다른 순서로 먹게 하는 교차 시험에 라틴 방진이 쓰입니다.

스도쿠⁠(sudoku)⁠. 완성된 스도쿠는 9 × 9 라틴 방진에 '굵은 선으로 나뉜 3 × 3 상자마다 1부터 9가 한 번씩'이라는 조건을 더한 것입니다. 1979년 미국의 퍼즐 잡지에 하워드 갠스가 '넘버 플레이스'라는 이름으로 처음 실었고, 1984년 일본의 퍼즐 회사 니콜리가 '스도쿠'라는 이름을 붙여 널리 퍼뜨렸습니다. 서로 다른 완성된 스도쿠는 6,670,903,752,021,072,936,960개입니다(2005년 베르트람 펠겐하우어와 프레이저 자비스의 계산). 답이 하나뿐인 문제에는 처음 주어진 수가 적어도 17개 있어야 한다는 것은 2012년 게리 맥과이어 등이 컴퓨터로 모든 16개짜리 경우를 따져 확인했습니다.

이어지는 곳. 서로 직교하는 라틴 방진을 n − 1개까지 모을 수 있는 것은 차수 n인 유한 사영 평면⁠(projective plane)⁠, 곧 점과 직선이 유한 개이고 어느 두 점도 한 직선으로, 어느 두 직선도 한 점에서 만나며 직선마다 점이 n + 1개인 기하⁠(geometry)⁠가 있을 때와 꼭 같습니다(사영기하⁠(projective geometry)⁠). n이 소수의 거듭제곱이면 그런 평면이 있고, 1989년 클레먼트 램과 동료들은 컴퓨터 탐색으로 차수 10인 사영 평면이 없음을 보였습니다. 직교하는 두 라틴 방진의 칸마다 (행, 열, 첫째 기호, 둘째 기호)를 적으면, 어느 두 줄도 해밍 거리⁠(Hamming distance)⁠가 3 이상인 부호어⁠(codeword)⁠ n²개가 되어 오류 하나를 고칠 수 있는 오류 정정 부호⁠(error-correcting code)⁠가 됩니다. 그래프로 보면 n × n 라틴 방진은 가로줄 n개와 세로줄 n개를 꼭짓점⁠(vertex)⁠으로 하는 완전 이분 그래프의 변을 n가지 색으로 칠하되, 한 꼭짓점에서 만나는 변끼리는 색이 겹치지 않게 칠한 것과 같습니다(r행 c열의 기호가 변 rc의 색). 모든 짝이 한 번씩이라는 조건은 전단사⁠(bijective)⁠로, 칸과 짝의 개수를 맞추는 셈은 비둘기집 원리⁠(pigeonhole principle)⁠로 이어집니다.