이웃한 두 수의 합이 제곱수인 순환 문제
최근 인터넷에서 화제가 된 흥미로운 수학 문제에 대해 해설해보고자 한다.
문제 소개
1부터 32까지의 정수를 한 번씩 이용해 원형으로 나열했을 때, 이웃한 두 수를 더하면 제곱수가 되는 배치를 찾는 문제이다.
해밀턴 순환으로서의 해석
이 문제는 본질적으로 해밀턴 순환(Hamilton cycle)을 찾는 문제다. 해밀턴 순환은 그래프의 모든 정점을 정확히 한 번씩 방문하고 시작점으로 돌아오는 경로를 의미한다.
해밀턴 경로와 순환의 차이
- 해밀턴 경로: 모든 점을 한 번씩 방문하는 경로
- 해밀턴 순환: 해밀턴 경로 중 시작점으로 돌아오는 경로
문제 해결 과정
1. 가능한 연결 분석
각 숫자별로 더했을 때 제곱수가 되는 경우를 찾아야 한다.
- 1의 경우: 3, 8, 15, 24와 연결 가능
- 2의 경우: 7, 14, 23과 연결 가능
- 32의 경우: 4, 17과 연결 가능
2. 프로그래밍을 통한 해결
사람이 직접 찾기에는 경우의 수가 너무 많으므로, 컴퓨터 프로그램을 통해 해결할 수 있다.
결과 분석
n=32일 때의 특징
- 유일한 해밀턴 순환이 존재
- 순환: 3-6-30-19-17-32-4-21-28-8-1-15-10-26-23-2-14-22-27-9-16-20-29-7-18-31-5-11-25-24-12-13
n이 다른 경우
- n=33: 유일한 해밀턴 순환 존재
- n=34: 11개의 서로 다른 해밀턴 순환 존재
- n<32: 해밀턴 순환 존재하지 않음