라틴 방진과 스도쿠
가로세로에 겹치지 않게 채웁니다
가로세로 4×4 판에 숫자 1, 2, 3, 4를 가로줄에도 세로줄에도 단 한 번씩만 겹치지 않게 채워 넣어 보세요.
신문에서 매일 푸는 스도쿠 퍼즐의 뿌리가 바로 18세기 오일러가 연구했던 「라틴 방진(Latin Square)」입니다. 단순한 숫자 퍼즐이 어떻게 과학 실험과 통신 암호의 핵심 설계도가 되었을까요?
이야기
1782년, 일흔다섯의 오일러가 문제를 하나 냅니다. 「여섯 부대에서 여섯 계급씩 뽑은 서른여섯 명의 장교를 6×6으로 세우되, 어느 줄에도 같은 부대와 같은 계급이 겹치지 않게 할 수 있는가.」 그는 안 된다고 짐작했고, 6뿐 아니라 10, 14, 18에서도 안 될 것이라 했습니다.
1900년 타리가 모든 경우를 손으로 다 따져 6은 정말 안 된다는 것을 밝혔습니다. 오일러가 맞았습니다.
그런데 1959년, 오일러가 틀렸습니다. 보스·슈리칸데·파커 세 사람이 10×10을 실제로 만들어 보인 것입니다. 사람들은 그들을 「오일러를 망친 자들」이라 불렀습니다. 오일러의 짐작이 깨지는 데 177년이 걸렸습니다.
스도쿠라는 이름은 훨씬 나중 일입니다. 1979년 미국 인디애나의 은퇴한 건축가 하워드 간스가 「넘버 플레이스」라는 이름으로 만든 것을 일본 잡지가 가져가 1984년에 새 이름을 붙였습니다.
이 표가 쓸모 있는 까닭은 모든 짝을 한 번씩만 만나게 하기 때문입니다. 그래서 농사 실험에서 밭을 나눌 때, 시험 문제를 배열할 때, 통신에서 오류를 잡을 때 지금도 쓰입니다.
실험을 공평하게 설계하는 법입니다. 농약 시험에서 밭의 위치와 시기가 결과에 섞이지 않도록 라틴 방진으로 배치합니다.
신약 임상시험에서 환자에게 약을 배정하는 순서, 공장의 조건별 시험 계획에도 그대로 쓰입니다.
계단 넷 — 같은 사실을 네 깊이로
4×4 스도쿠를 풀어 본다
빨강, 파랑, 노랑, 초록의 네 가지 색깔 바둑돌을 4×4 격자판에 가로세로 줄마다 색이 겹치지 않게 놓아 봅니다.
대각선으로 한 칸씩 밀어가며 놓는 규칙을 쓰면 쉽게 완성됩니다. 빈칸을 하나씩 채워가며 줄마다 딱 하나씩만 들어가는 조화를 눈으로 찾아보세요.
한 줄에 하나씩
크기가 하나 늘면 폭발적으로 늘어납니다.
경우의 수 세기
라틴 방진에 '3×3 작은 상자 안에도 1부터 9까지 겹치지 않는다'는 조건을 하나 더 보탠 것이 바로 스도쿠(Sudoku)입니다.
서로 다른 두 라틴 방진을 겹쳤을 때 만들어지는 순서쌍 가 단 하나도 중복되지 않고 모두 다르면 '직교 라틴 방진(Graeco-Latin Square)'이라 부릅니다. 오일러는 36명의 장교를 계급과 연대가 겹치지 않게 6×6으로 세우는 문제가 불가능함을 추측했습니다.
스도쿠는 몇 가지
3×3 상자 조건이 82 만 분의 1 로 줄였습니다.
직교 라틴 방진
크기 인 직교 라틴 방진 쌍은 을 제외한 모든 자연수에 대해 존재함이 1960년 보스, 파커, 슈리칸데에 의해 증명되었습니다 (오일러의 추측 반박).
라틴 방진은 대수학에서 준군(Quasigroup)의 곱셈표(Cayley Table)와 정확히 일치하며, 상호 직교 라틴 방진(MOLS)의 최대 개수는 유한 사영 평면(Finite Projective Plane)의 존재성과 동치입니다.
몇 개를 보여 줘야 하나
17 개면 가능한 경우가 있습니다.
실험 설계
라틴 방진의 진가는 통계학자 로널드 피셔의 실험 계획법(Design of Experiments)에서 폭발했습니다.
토양, 비료, 품종 등 여러 요인이 섞인 농업 실험이나 신약 임상시험에서 최소한의 시험 횟수로 교란 요인을 완벽히 통제하고 독립적 효과를 검증합니다. 오늘날 오류 정정 부호, 5G 무선 통신 주파수 분할, 양자 정보 암호화의 핵심 설계 기법으로 쓰입니다.
직교 라틴 방진
2 와 6 만 맞았습니다 — 10 은 1959년에 만들어졌습니다.
풀어 보기
라틴 방진의 원리. 가로세로 크기가 인 격자판의 각 행과 열에 부터 까지의 숫자가 정확히 한 번씩 들어가는 배열을 라틴 방진이라 한다.
(1) 크기가 3×3인 라틴 방진에서 첫 번째 행이 , 두 번째 행이 일 때, 세 번째 행을 완성하시오.
(2) 서로 다른 두 라틴 방진을 포갰을 때 생기는 순서쌍이 모두 서로 다르면 두 방진을 무엇이라 부르는가?
(3) 오일러가 36 장교 문제에서 존재하지 않는다고 추측했고 실제로 존재하지 않음이 증명된 직교 라틴 방진의 크기 의 값은 얼마인가?
(1) 세 번째 행은 입니다. (3) 36 장교 문제는 6×6 크기이므로 입니다.
답과 풀이 보기
(1) 입니다.
첫째 열에 1, 2 가 이미 있으므로 남은 것은 3 이고, 둘째 열에 2, 3 이 있으므로 1, 셋째 열에 3, 1 이 있으므로 2 입니다. 고를 것이 없습니다 — 앞의 두 줄이 셋째 줄을 완전히 정해 버립니다.
(2) 직교 라틴 방진(그레코-라틴 방진)이라 합니다.
두 방진을 포개어 만든 개의 순서쌍이 하나도 겹치지 않는 상태입니다.
(3) 입니다.
여섯 계급 · 여섯 부대에서 뽑은 36 명의 장교를 으로 세우되 각 줄에 계급도 부대도 겹치지 않게 — 이것이 오일러의 36 장교 문제입니다.
오일러는 1782 년에 불가능하다고 추측했고, 1901 년 타리가 가능한 배열을 모두 손으로 따져 증명했습니다.
그런데 오일러는 이 모두 불가능하다고 했습니다.
1959 년 보스·슈리칸데·파커가 을 실제로 만들어 보였습니다. 오일러가 177 년 동안 옳은 줄 알았던 추측이 딱 에서만 맞았습니다.
더 멀리
라틴 방진은 놀이 밖에서 더 많이 쓰입니다.
- 실험 설계 — 여러 조건을 고르게 배치해 공정하게 비교합니다
- 오류 정정 부호 — 통신에서 잡음을 이겨 내는 데 쓰입니다
- 스도쿠 만들기 — 답이 하나뿐이도록 힌트를 배치하는 것도 수학 문제입니다
이어지는 장
가로와 세로 각 줄에 같은 숫자가 한 번씩만 들어가도록 배열하는 라틴 방진의 대칭 구조는, 고대 중국의 전설적인 거북 등껍질 수열에서 시작되어 가로·세로·대각선의 합을 맞추는 제46장 마방진과 함께 수의 배치 속에 깃든 절묘한 균형미를 보여 줍니다.
영감을 받은 곳
레온하르트 오일러(Leonhard Euler)가 1779년 페테르부르크 학술원에 제출하고 1782년 발표한 논문 「어떤 새로운 종류의 마방진에 관한 연구」(유명한 '36명의 장교 문제')에서 체계화한 라틴 방진(Latin square)에서 왔습니다.