마방진이라고 들어보셨죠? 가로, 세로, 대각선 어느 방향으로 더해도 합이 같아지도록 숫자를 배열한 정사각형이요. 그런데 이걸 육각형 벌집 모양으로 확장한 '마법 육각형(magic hexagon)'이라는 것도 있거든요. 최근 한 수학 블로그에서 이 마법 육각형에 관한 오래된 질문에 답을 내놨어요. 결론부터 말하면, 조건을 살짝만 넓히면 어떤 크기의 마법 육각형이든 존재한다는 거예요. 오랫동안 '사실상 하나뿐'이라고 알려져 있던 대상이라 꽤 의미 있는 결과인데요, 차근차근 풀어볼게요.
마법 육각형이 뭐냐면
마법 육각형은 육각형 칸들을 벌집처럼 붙여서 큰 육각형을 만들고, 거기에 연속된 정수를 하나씩 채운 거예요. 조건은 세 방향(가로줄, 왼쪽 대각선줄, 오른쪽 대각선줄)의 모든 줄 합이 똑같아야 한다는 것. 한 변에 칸이 n개 있으면 '차수 n'이라고 부르고, 전체 칸 수는 3n²−3n+1개가 돼요. 차수 3이면 19칸이죠.
그런데 여기에 유명한 고전 결과가 있어요. 1부터 시작하는 연속된 자연수로 채우는 '정규' 마법 육각형은 차수 1(칸 하나짜리, 자명한 경우)과 차수 3, 딱 둘만 존재한다는 거예요. 차수 3짜리는 1부터 19까지의 수로 모든 줄의 합이 38이 되는데, 배치를 뒤집거나 돌린 걸 같은 것으로 치면 이게 유일해요. 왜 다른 크기는 안 되냐면, 전체 합을 줄 개수로 나눴을 때 각 줄의 합이 정수로 딱 떨어져야 하는데, 차수 1과 3을 빼면 이 나눗셈이 절대 맞아떨어지지 않거든요. 증명이 초등적인 정수론 수준이라 더 매력적인 문제예요.
그럼 질문을 바꿔보면요
수학자들이 잘하는 게 바로 이 지점이에요. '1부터 시작해야 한다'는 조건을 풀어서, 아무 정수부터 시작하는 연속된 정수를 허용하면 어떨까? 그러면 이야기가 달라져요. 실제로 3부터 시작하는 차수 4짜리 마법 육각형처럼, 개별 크기에 대한 사례들이 컴퓨터 탐색으로 하나둘 발견돼 왔거든요. 하지만 '그렇다면 모든 차수에 대해 존재하느냐'는 일반적인 질문은 열려 있었어요. 크기가 커질수록 칸 수가 제곱으로 늘어나니까, 무작정 컴퓨터로 뒤지는 방식으로는 답할 수 없는 문제였죠.
이번 글이 내놓은 답이 바로 그 일반화예요. 어떤 차수 n을 가져와도, 적절한 시작 수를 고르면 연속된 정수로 채워지는 마법 육각형이 존재한다는 걸 보였다는 거예요. 이런 존재성 증명은 보통 두 단계로 이뤄져요. 먼저 줄 합이 정수가 되도록 시작 수가 만족해야 할 조건을 정수론으로 좁히고, 그다음 그 조건을 만족하는 실제 배치를 만들어내는 구성법을 제시하는 식이죠. 몇몇 사례가 있다는 것과 모든 크기에서 된다는 건 수학적으로 완전히 다른 차원의 이야기라서, 이 결과로 마법 육각형의 존재 문제는 사실상 마침표를 찍은 셈이에요.
개발자한테도 재미있는 놀잇감이에요
이게 개발이랑 무슨 상관이냐 싶으실 수 있는데, 사실 마법 육각형은 훌륭한 프로그래밍 연습 문제거든요. 조건을 만족하는 배치를 찾는 건 전형적인 제약 충족 문제(constraint satisfaction problem)라서, 백트래킹으로 직접 짜볼 수도 있고 SAT 솔버나 정수계획법 같은 도구에 문제를 던져보는 연습도 할 수 있어요. 가지치기를 얼마나 영리하게 하느냐에 따라 탐색 시간이 몇 시간에서 몇 초로 줄어드는 경험은 알고리즘 감각을 키우는 데 정말 좋아요. 주말 토이 프로젝트로 차수 4짜리를 찾는 프로그램을 짜보시면, 스도쿠 솔버와는 또 다른 재미를 느끼실 거예요.
정리하면, 문제의 조건 하나를 살짝 바꿨더니 '거의 존재하지 않던' 대상이 '모든 크기에서 존재하는' 대상으로 바뀌었다는 이야기예요. 막힌 문제를 만났을 때 조건 자체를 의심해보는 태도, 개발할 때도 통하는 지혜 아닐까요? 여러분이라면 마법 육각형 탐색 프로그램을 어떤 방식으로 짜보시겠어요?
🔗 출처: Hacker News