어느새 부터 패턴은 안멋져

1 8 28 21 4 32 17 19 30 6 3 13 12 24 25 11 5 31 18 7 29 20 16 9 27 22 14 2 23 26 10 15

여기 보이는 이 숫자들은 숫자들이 무작위로 배열되어 있는 것 처럼 보입니다. 하지만 이 원형수열은 숫자가 딱 한 번씩만 사용되었고, 인접한 두 숫자의 합이 항상 완전 제곱수를 이룹니다. 예를들어 $32$로 이루어진 수열에서 $1$과 $8$을 더하면 $9$가 되고, 이는 $3$의 제곱입니다.

$$1+8=9=3^2$$

마찬가지로, $32$와 $17$을 더하면 $49$가 되는데, 이는 $7$의 제곱입니다.

$$32+17=49=7^2$$

이런 아름다운 패턴과 숨겨진 규칙들이 바로 수학의 매력인데요. $32$보다 크거나 작은 수에서도 가능할까요?

33에서도 가능할까?

우선 $33$에서도 이러한 패턴이 가능한지 알아보도록 하겠습니다. $1$부터 $33$까지 $33$개의 숫자를 원 위에 배열하는 경우의 수는 원순열을 이용하면

$$(33-1)!=32!=2.63\times 10^{35}$$

라는 것을 알 수 있습니다. 하지만 이 모든 원형 수열을 나열하면서 제곱수가 되는지 아닌지 판단하는 것은 매우 어렵기에 우리는 이 원형수열이 갖는 성질에 대해 한 번 생각해보겠습니다. 원형 수열은 이웃한 두 수의 합이 제곱수가 되는 성질을 갖고 있습니다. 따라서 모든 경우의 수를 다 찾는 것이 아니라 우선 1부터 33까지 숫자 중에 두 수의 합이 제곱수가 되는 조합만 시도해보면 됩니다. 이 모든 조합을 다 찾아보면 다음과 같습니다.

33	$2^2$	$3^2$	$4^2$	$5^2$	$6^2$	$7^2$	$8^2$
	$(1,3)$	$(1,8)$	$(1,15)$	$(1,24)$	$(3,33)$	$(16,33)$	$(31,33)$
		$(2,7)$	$(2,14)$	$(2,23)$	$(4,32)$	$(17,32)$
		$(3,6)$	$(3,13)$	$(3,22)$	$(5,31)$	$(18,31)$
		$(4,5)$	$(4,12)$	$(4,21)$	$(6,30)$	$(19,30)$
			$(5,11)$	$(5,20)$	$(7,29)$	$(20,29)$
			$(6,10)$	$(6,19)$	$(8,28)$	$(21,28)$
			$(7,9)$	$(7,18)$	$(9,27)$	$(22,27)$
				$(8,17)$	$(10,26)$	$(23,26)$
				$(9,16)$	$(11,25)$	$(24,25)$
				$(10,15)$	$(12,24)$
				$(11,14)$	$(13,23)$
				$(12,13)$	$(14,22)$
					$(15,21)$
					$(16,20)$
					$(17,19)$

다음으로 $1$부터 $32$까지 가능한 조합들은 $1$부터 $33$까지의 조합에서도 사용할 수 있으므로 $32$로 만든 기존의 배열과 크게 차이가 나지 않을 것입니다. 따라서 $32$에서 가능한 조합과 비교해보겠습니다.

32	$2^2$	$3^2$	$4^2$	$5^2$	$6^2$	$7^2$
	$(1,3)$	$(1,8)$	$(1,15)$	$(1,24)$	$(4,32)$	$(17,32)$
		$(2,7)$	$(2,14)$	$(2,23)$	$(5,31)$	$(18,31)$
		$(3,6)$	$(3,13)$	$(3,22)$	$(6,30)$	$(19,30)$
		$(4,5)$	$(4,12)$	$(4,21)$	$(7,29)$	$(20,29)$
			$(5,11)$	$(5,20)$	$(8,28)$	$(21,28)$
			$(6,10)$	$(6,19)$	$(9,27)$	$(22,27)$
			$(7,9)$	$(7,18)$	$(10,26)$	$(23,26)$
				$(8,17)$	$(11,25)$	$(24,25)$
				$(9,16)$	$(12,24)$
				$(10,15)$	$(13,23)$
				$(11,14)$	$(14,22)$
				$(12,13)$	$(15,21)$
					$(16,20)$
					$(17,19)$

$1$부터 $32$까지의 수를 보면 다음과 같이 $46$개의 순서쌍이 사용가능합니다. 길이가 $32$인 원형 수열을 만들기 위해서는 $32$개인 순서쌍이 있으면 충분한데 사용할 수 있는 조합의 수가 $46$개라면 충분하기에 처음에 본 원형 수열을 잘 만들 수 있었던거죠. 이제 $33$을 추가하면 $(3,33)$, $(16,33)$, $(31,33)$도 제곱수를 만들 수 있으므로 가능한 조합의 개수가 $49$개로 증가하게 됩니다. 더군다나 $33$은 처음 추가되는 수이므로 $33$이 들어갈 수 있는 자리인 $3$, $16$, $31$주변을 우선적으로 탐색하면서 원형 수열을 찾아보면 기존의 길이가 $32$인 수열을 크게 바꾸지 않고 길이가 $33$인 수열을 만드는 것을 성공할 수 있습니다.

1 8 28 21 4 32 17 19 30 6 3 13 12 24 25 11 5 31 18 7 29 20 16 9 27 22 14 2 23 26 10 15.

1 8 28 21 4 32 17 19 30 6 3 13 12 24 25 11 5 20 29 7 18 31 33 16 9 27 22 14 2 23 26 10 15.

32보다 작게 만들 수 있을까?

그렇다면 이러한 원형배열은 더 작은 수에서도 가능할까요? 예를들어 $1$부터 $4$까지의 수만 이용하면 어떻게 될까요? $1$부터 $4$까지 중에 두 수의 합이 제곱수가 되는 조합은 $(1,3)$ 밖에 없습니다. 따라서 $1$부터 $4$를 원형으로 배열해서는 제곱수를 만들 수 없죠.

4	$2^2$
	$(1,3)$

그렇다면 $1$부터 $20$까지라면 어떻게 될까요?

20	$2^2$	$3^2$	$4^2$	$5^2$	$6^2$
	$(1,3)$	$(1,8)$	$(1,15)$	$(5,20)$	$(16,20)$
		$(2,7)$	$(2,14)$	$(6,19)$	$(17,19)$
		$(3,6)$	$(3,13)$	$(7,18)$
		$(4,5)$	$(4,12)$	$(8,17)$
			$(5,11)$	$(9,16)$
			$(6,10)$	$(10,15)$
			$(7,9)$	$(11,14)$
				$(12,13)$

가능한 순서쌍의 개수가 $22$개로 늘었고 필요한 최소 순서쌍 개수인 $20$개보다 많으므로 가능해보이기도 합니다. 하지만 이 모든걸 다 조합해 원형으로 배열하려면 이어질 수 있는 모든 조합을 모두 고려하여 계산을 풀어야만 합니다. 따라서 이 복잡한 문제를 풀기 쉽게 바꾸기 위해서는 한 가지 수학적 아이디어가 필요합니다. 바로 그래프 이론(Graph Theory)이죠. 이 문제를 이렇게 바꾸어보겠습니다. 각 숫자들을 점으로 두고 가능한 조합인 두 수를 선으로 이어보는 거죠. 이렇게 문제를 바꾸어 보면 원형수열을 만드는 문제는 한 점에서 출발하여 선을 통해 모든 점을 다 연결한 후 다시 시작점으로 돌아오는 문제로 바뀌게 됩니다. 바로 해밀턴 회로 문제죠. 문제를 바꾸었다고해서 바로 결론을 찾을 수는 없습니다. 왜냐하면 아직 해밀턴 회로의 필요충분조건이 알려져 있지 않기 때문입니다. 다른말로 아직 해결방법이 증명되지 않는 미해결 문제죠.

하지만 일반적인 풀이법은 없어도 이 문제와 같이 특수한 경우에 대해서는 몇 가지 힌트를 찾을 수 있습니다. 우선 해밀턴 회로는 모든 점을 지나고 다시 원래 그래프로 돌아오기 때문에 시작점이 의미가 없습니다. 어느 점에서 출발하든지 상관없죠. 따라서 저는 항상 $1$부터 출발해서 다시 $1$로 돌아오는 수열을 찾도록 하겠습니다. 다음으로 이웃한 두 수의 합이 제곱수가 되어야하므로 한 수를 기준으로 좌우에 각각 제곱수를 만들어야하므로 $2$개의 선을 이용해 점을 연결해야합니다. 쉽게말해 들어오는 선과 나가는 선이 필요하죠. 따라서 원형 수열이 존재하기 위해서는 한 점에 연결된 선의 개수 즉, 그래프의 차수는 최소 2가 되어야 합니다. $1$ 부터 차례대로 그래프를 그려보면서 그래프의 차수를 관찰해보면 $1$부터 $30$ 까지의 그래프들은 차수가 $2$보다 작은 점이 존재하므로 원형 수열을 찾을 필요도 없이 원형 수열이 없다는 것이 증명되었습니다.

그런데 이제 한가지 문제가 남습니다. 바로 $31$이죠. $31$은 모든 점의 차수가 $2$보다 크거나 같은 최소의 수입니다. 따라서 이 경우에는 문제를 쉽게 해결할 수 없죠.

31

우선 31에서 원형수열이 존재할지, 존재하지 않을지 바로 찾을 수 있는 방법은 없습니다. 해밀턴 회로의 존재성은 미해결 문제죠. 그리고 너무나 유명한 NP문제입니다. 처음에 시도해보야할 경우의 수가 원순열의 경우의 수인 $(n-1)!$가지인 것을 보아도 컴퓨터를 갈아넣어야할 문제라는 것을 알 수 있죠. 그래도 그래프 이론을 이용해 문제를 조금 단순화할 수는 있습니다. 우선 $31$로 만든 그래프를 다시 보도록 하겠습니다.

앞서 말했듯이 원형수열을 만들기 위해서는 최소 $2$개의 선이 필요합니다. 이 점을 초점으로하여 그래프를 다시 관찰하면 선이 $2$개인 점들이 있습니다. 이 점들은 다른 수의 조합을 사용할 수 없고 반드시 이어진 점들만 연결해서 원형수열을 만들어야 하죠. 이 선을 빨간색으로 표시하겠습니다. 그 후에 $31$을 보겠습니다. $31$은 $5$와 $18$에만 연결되어 있습니다. 그러므로 $5-31-18$이외에 다른 조합은 불가능합니다. 같은 방법으로 $18$을 보면 $31-18-7$만 가능합니다. 이 두 수열을 이어보면 $5-31-18-7$이죠. $7$은 차수가 $4$이므로 이제 다른 점으로 연결될 수 있어보이지만 $29$가 반드시 $7$과 $20$을 이어서 $7-29-20$이라는 수열을 만들어야하므로 결과적으로 $7$을 연결해야할 선 $2$개가 정해지게 됩니다. 이 내용을 정리하면 빨간선이 $2$개 연결된 점들은 반드시 이어지는 수열이 존재하고 이 점들은 수열을 잇는 처음점과 끝점을 제외하면 굳이 조사할 필요가 없어집니다. 따라서 빨간선이 $2$개 연결된 점을 제거하고 시점과 종점을 빨간색으로 이으면 다음과 같이 그래프를 간소화할 수 있습니다. 이 때 주의할 점은 $5$와 $22$처럼 시점과 종점을 이은 선은 반드시 연결되어야할 점이므로 빨간색으로 표시하겠습니다. 이렇게 간소화한 그래프에서 보면 $2$의 차수 즉, 연결된 점의 개수가 다시 $2$가 되므로 반드시 지나야하는 선인 빨간색으로 표시하고 빨간색 점이 $2$개가 되는 선을 제거하는 작업을 반복해 최종적으로 노드가 13개인 그래프로 간소화시킬 수 있습니다.

이제 이 그래프의 한 점에서 출발하여 다시 원래점으로 돌아오는 그래프를 찾는 문제는 처음보았던 $31$개를 모두 잇는 것보다는 간단합니다. 그래도 이 그래프에서 바로 세기에는 어지럽기 때문에 점을 적절히 이동해보겠습니다. 그래프의 점을 이동하는 것은 이동 전후에 그래프의 정점과 간선, 그리고 그들 사이의 연결 관계가 변하지 않기 때문에 동형이며 복잡한 그래프를 더 간단한 형태로 바꿀 수 있습니다. 이렇게 그래프를 바꾼 후 남은 작업은 직접 다 해보는 것입니다. 이 그래프에서 저는 처음과 같이 $1$부터 출발할 것입니다. (그래프를 자세히 보면 $1$, $4$, $15$에서는 반드시 지나야할 빨간 간선이 없고, 모두 차수가 $3$이므로 이 세 점 중 하나에서 출발하는게 합리적입니다.)

이제 $1$에서 출발했을 때 선택할 수 있는 경로는 $3$, $15$, $24$뿐 입니다. 저는 이 중에 $3$으로 이동해보겠습니다. $3$으로 이동하면 $3$에서는 $6$과 $12$ 중 하나를 골라 이동해야합니다. 하지만 생각해보면 반드시 빨간 선인 $12$로 이동해야만 합니다. 왜냐하면 $3$에서는 반드시 $2$개의 선이 연결되어 원형수열을 만들어야 하는데 이미 한개의 선이 연결되었으므로 만약 $6$으로 이동한다면 나중에 $3$과 $12$이 연결되면서 차수가 $3$이상이 되기 때문이죠. 따라서 $12$로 이동한 후 다시 선택의 갈림길에 섭니다. 이제 같은 방법으로 둘 중 하나의 선을 연결하면서 하나씩 시도해보면 빨간선을 우선적으로 이동하면서 해밀턴 그래프를 완성하지 못한다는 것을 알 수 있습니다. $1$이란 점에서 $3$을 선택하는 것과 $24$를 연결하는 것은 본질적으로 같은 선택이고 $15$를 잇는 방법도 결과적으로 $15$를 지나서 다시 $1$로 가는 경우가 지금 보이는 경우에 포함되어 있으므로 이런 방식으로 모든 경우를 조사하면 해밀턴 회로가 없음을 보일 수 있습니다.

33보다 큰 수는 가능할까?

그렇다면 이제 한가지 질문만이 남았습니다. $31$이하의 수에서는 원형수열이 없고, $32$와 $33$은 원형 수열이 존재한다는 것은 알았는데 $34$이상에서는 어떻게 될까요? 앞서 보았듯 이 문제는 해밀턴 회로 문제로 모든 경우를 다 세는 방법밖에 없습니다. 그런데 그 전에 해야할 추측이 있습니다. 과연 $32$보다 큰 수에는 반드시 원형수열이 있을까요? $33$에서는 운좋게 원형 수열을 찾았지만 그 보다 큰 수에는 원형수열이 있다고 확신할 수는 없습니다. 그리고 원형수열이 있다면 찾으면 되지만 반대로 없다면 앞서 본 경우처럼 모든 경우에 대해 없다는 것을 증명해야합니다. 따라서 수학에서 문제를 풀기 전에는 항상 이러한 존재성에 대한 질문을 던지죠. 답도 없는 문제에 답을 찾을 수는 없으니까요. 우선 저는 32보다 큰 수에는 반드시 이러한 원형 수열이 존재할 것이라 추측합니다. 그 근거는 순서쌍 개수의 증가 때문입니다. 앞서 보았듯이 $32$에서 $33$으로 변할 때 순서쌍은 $3$개 증가했습니다. 그렇다면 $33$에서 $34$로 변할 때 순서쌍은 몇개가 늘어날까요?

34	$2^2$	$3^2$	$4^2$	$5^2$	$6^2$	$7^2$	$8^2$
	$(1,3)$	$(1,8)$	$(1,15)$	$(1,24)$	$(2,34)$	$(15,34)$	$(30,34)$
		$(2,7)$	$(2,14)$	$(2,23)$	$(3,33)$	$(16,33)$	$(31,33)$
		$(3,6)$	$(3,13)$	$(3,22)$	$(4,32)$	$(17,32)$
		$(4,5)$	$(4,12)$	$(4,21)$	$(5,31)$	$(18,31)$
			$(5,11)$	$(5,20)$	$(6,30)$	$(19,30)$
			$(6,10)$	$(6,19)$	$(7,29)$	$(20,29)$
			$(7,9)$	$(7,18)$	$(8,28)$	$(21,28)$
				$(8,17)$	$(9,27)$	$(22,27)$
				$(9,16)$	$(10,26)$	$(23,26)$
				$(10,15)$	$(11,25)$	$(24,25)$
				$(11,14)$	$(12,24)$
				$(12,13)$	$(13,23)$
					$(14,22)$
					$(15,21)$
					$(16,20)$
					$(17,19)$

$(2,34)$, $(15,34)$, $(30,34)$ $3$가지가 늘어납니다. 원형수열은 앞서말했듯 숫자의 개수만큼 순서쌍 조합이 필요합니다. 따라서 $34$ 원형수열은 $33$ 원형수열보다 길이는 $1$밖에 증가하지 않았으나 조합의 개수는 $3$개가 증가했으니 나쁘지않죠. 물론 $34$를 원형수열에 배치하기 위해서는 $34$가 포함된 조합이 최소한 $2$개 필요하므로 $3$개라면 마냥 적당하지는 않지만요. 쨋든 저는 $34$도 원형 수열이 존재할거라는 강력한 믿음을 가지고 $33$에서 했었던 것과 마찬가지로 가능한 조합과 이전 수열에서 본 형태를 이용해 찾아보려했습니다.

그러나 이 문제는 해밀턴 회로 문제이기에 제가 손으로 푸는 것은 한계가 있었고, 그래서 컴퓨터의 도움을 빌려 조건을 만족하는 수열을 찾아보았습니다. 그리고 그 결과 조건을 만족하는 원형 수열을 찾아냈습니다. $34$에서도 원형 수열이 존재했으며 심지어 이러한 수열은 하나가 아니었습니다. 그리고 이러한 패턴은 더 큰 수들에서도 계속 발견되었습니다. 잠시 감상하시죠.

아름다우신가요? 파이썬 코드를 이용해 조건을 만족하는 수열을 찾아보면 1초도 걸리지 않아 $31$에서는 원형 수열이 존재하지 않는다는 것을 알아낼 수 있고 길이가 $42$일 때는 $1,000$개 이상, 길이가 $44$일때는 $10,000$개 이상의 원형 수열이 가능하다는 사실을 알 수 있습니다. 더 큰 수에서는 너무 컴퓨팅 시간이 오래걸려 백트래킹과 최소 차수 휴리스틱을 활용해 존재하는지를 찾아 본 결과 아직 몇몇 자연수에 대해서는 원형 수열을 찾지 못한 것도 있지만 영상을 만드는 지금도 계속 비어있는 칸을 채워나가고 있으며 제가 이 문제를 처음 시작할 때 목표로 했던 길이가 $100$인 원형 수열도 찾아낼 수 있었습니다.

더하여 원형수열의 길이가 $100$일 때 사용할 수 있는 순서쌍의 개수는 $271$개, 길이가 $1000$일 때 사용할 수 있는 순서쌍의 개수는 $8711$개로 필요한 순서쌍의 개수보다 더 많은 조합이 가능합니다. 그리고 길이가 $100$일 때 그래프의 최소차수는 $4$, 길이가 $1000$인 그래프의 최소차수는 $12$로 계속 증가하고 있습니다. 저는 이러한 추세를 통해 길이가 길어져도 원형수열이 반드시 존재할 것이라 추측합니다.

하지만 앞선 결과에서 원형수열이 존재한다는 확신이 들어도 이는 추측일 뿐 반드시 존재한다고 생각하면 안됩니다. 해밀턴 회로에 대한 많은 정보를 담고 있는 오레의 정리에 따라 이 그래프를 분석해도 임의의 두점의 차수의 합이 길이보다 커지기에는 많이 부족하므로 반드시 해밀턴 회로가 있다고 확정할 수 없습니다. 왜냐하면 앞서 말했듯 해밀턴 회로의 존재성은 아직 필요충분 조건이 발견되지 않았고, 저는 이 문제를 해결할 능력이 부족하기 때문이죠.

에필로그

사실 이 문제는 제 가장 친한 친구한테 2년 전에 받은 사진 한장에 대한 질문으로 출발했습니다. 유튜브를 하니 이 주제로 한 번 영상을 만들어보라는 거였죠. 그런데 단순히 사진 하나 틀어놓고 아름답죠. 이러기에는 뭔가 부족해보였고, 이 문제를 보면서 ‘다른 수는 안되나?’ 하는 의문이 들었던 것에 대한 해결책을 찾으려 했습니다. 하지만 그때는 손으로만 문제를 풀다보니 한계를 느껴 포기했었지만 그러다 최근에 코딩을 배우게 되어 다시 원형 수열을 찾아보고자 도전해보았고 완벽하지는 않지만 이정도면 대본을 작성할 수 있을 것 같아 영상을 제작해보았습니다. 32에서만 원형수열이 존재했다면 신기했겠지만 오히려 다른 수에서도 원형수열을 찾다보니 처음만큼 신기한 것 같지는 않습니다. 이러한 다양한 패턴이 필연적으로 존재할 수 밖에 없고, 존재해야만 하는 것 처럼 느껴지죠. 오히려 이런 패턴을 보면서 아름답고 신기하다는 매력보다는 설계도 없는 레고 조각을 맞추어 나만의 비행기를 만드는 것과 같이 비밀을 하나씩 파헤치면서 보는게 진정한 수학의 매력이 아닐까 싶습니다. 제 부족한 지식으로는 여기가 한계였지만 이 영상을 보시는 여러분들은 저보다 더 뛰어나신 분들이 많으니 제가 찾은 결과를 바탕으로 더 나은 결과를 내주셨으면 좋겠습니다.