우리나라에 디시인사이드가 있다면 미국에는 4chan이 있습니다. 그 막장성은 국내에서도 짤방으로 접하신 분들이 많을 거라고 생각됩니다. 이러한 막장성과 별개로 정치, 비디오 게임, 총기(?), 성인물(!) 등등 그야말로 다양한 주제의 게시판들이 존재하며 미국 인터넷에 꽤 강력한 영향력을 보이는 사이트라고 볼 수 있습니다.
이번에 할 이야기는 2011년, 그 중 /sci/, 과학 및 수학 보드의 한 스레드로부터 시작하게 됩니다....
문제는 하루히인데 왜 사진에 있는건 슈타인즈 게이트인지 무시합시다.
어느 날, /sci/ 보드에 다음과 같은 질문이 올라오게 됩니다.
[만약14편의 하루히 애니메이션을 가능한 모든 순서로 보기 위해선, 최소 몇 편을 봐야할까? 단, 겹쳐있는 순서도 포함한다.]
이 문제만 봐서는 잘 이해가 안 되실수 있기에, 더욱 더 간단한 버전으로 이야기를 해보도록 하겠습니다. 만약 이 문제의 대상이 스타워즈 오리지널 3부작이었음 어땠을까요?
이 3편의 영화를 관람할 수 있는 순서의 가짓수는 총 6가지(123/132/213/231/312/321)입니다. 그래서 정말로 간단하게 생각한다면 총 18편의 영화를 봐야되겠죠? 하지만 위에서 말했듯이 겹쳐있는 순서도 포함하기 때문에 굳이 18편이나 볼 필요가 없습니다. 예를 들어, 123121321 의 순서로 9편만 관람을 하게 된다면, 위에서 확인한 모든 순서를 다 포함하는 것을 확인할 수 있습니다. 그러니까 대략 1일하고 15시간동안 스타워즈를 보는 것보단 19시간 정도만 걸려도 충분한다는 소리입니다.
아무튼 다시 본래 문제로 돌아가서, 이 문제는 대상이 하루히 애니메이션이었던 만큼 '하루히 문제'라는 이름이 붙여졌으며 어떻게보면 그냥 흘러가서 묻힐 수 있었던 이 스레드는 의외로 붐을 일으켜 꽤 다양한 답변들이 달리게 되었습니다. 물론 정말로 진지한 답변들만 달린건 아니었지만요..
이런 와중에, [익명의 지나가던 4chan 유저]가 답변을 달았습니다.
"내 생각엔 n편의 애니메이션에 대해서 대해서 적어도 n!+(n-1)!+(n-2)!+n-3번을 봐야한다는 걸 증명할 수 있을 것 같아. 답변을 여러개를 달아야 할 것 같은데. 혹시 내가 놓친 실수가 있는지 살펴봐줘."
이렇게 시작한 답변은, 자신이 증명에 사용한 기호 및 아이디어의 설명을 시작으로 차근차근 증명을 시작하였고, 5개의 답변을 통해 자신의 증명을 마무리하였습니다. 이후에 다른 사람들도 이를 읽어보았지만, 뚜렷한 실수를 발견하지 못하기에 이에 수긍했고 다 만족하여 자기 할 일을 하러 돌아갔습니다. 그렇게 이 스레드는 사람들에게 잊혀지게 됩니다.
그런데.....
2. 문제의 진실
사실 이 문제는 수학의 한 분야인 조합론에서 다루는 Superpermutation에 관한 문제입니다. (초순열이라고 번역할 수 있겠지만, 실제로 한국에서 이러한 용어를 사용하는지는 모르기에 영어로 계속 쓰도록 하겠습니다.)
Superpermutation이란 'n개의 문자'를 포함한 문자열을 전부 다 포함하는 문자열을 의미합니다. 이 'n개의 문자'를 앞에서 이야기한 애니메이션을 보는 순서로 치환하기만 하면 둘이 서로 같은 문제라는 것을 알 수 있습니다.
Superpermutation은 Daniel A. Ashlock 와 Jenett Tillotson라는 두 수학자에 의해 처음으로 그 개념이 나왔으며, 이를 소개한 논문에서 직접 자신들이 예상한 Superpermutation 길이의 최솟값들을 제시했습니다.
그런데 이 Superpermutation의 가장 큰 문제는, 문자의 갯수가 조금만 많아져도 그 길이가 기하급수적으로 증가한다는 사실이었습니다.
다시 한번 스타워즈로 돌아가서 이를 확인해봅시다. 만약 프리퀼 3부작까지 포함해서 6편을 본다면 어떨까요?
하도 보는 순서에 대한 훈수가 많아서 그냥 다 보기로 했습니다.
이 때는 다음과 같은 순서로 보는 것이 최선이라고 알려져있습니다... 심호흡 하시고.....
이러한 순서로 대략 872편의 스타워즈를 대략 82일을 걸려서 관람하시면 더 이상 스타워즈 팬들한테 스타워즈를 어떤 순서로 봐야하는지 훈수질을 안당하셔도 된다는 소리입니다.
그런데 이 872이라는 숫자가 굉장히 Superpermutation에 있어서 굉장히 중요한 숫자였습니다. 왜냐하면 앞에서 이야기한 Daniel A. Ashlock 와 Jenett Tillotson이 n=6일 때 제시한 최소 길이였던 873보다 더 적었기 때문입니다! 이에 대해 많은 수학자들이 충격을 금치 못했고, 이제 Superpermutation의 길이의 더 적은 최솟값을 표현할 길을 찾아야 했습니다....
3. 뜻 밖의 발견
Robin Houston은 앞에서 확인한 n=6일때의 Superpermutation의 길이가 이전에 알려져있는 값보다 더 짧다는 사실을 처음으로 알린 사람입니다. 자신이 이러한 발견을 한 만큼, Superpermutation의 길이의 최솟값을 더 정확히 표현할 수 있는 방법에 대해서도 몰두하기 시작했습니다.
이후 4년의 시간이 흐르고 나서, 2018년 10월의 어느 날, 인터넷을 돌아다니던 그는 이상한 페이지를 하나 발견합니다.
A curious situation. The best known lower bound for the minimal length of superpermutations was proved by an anonymous user of a wiki mainly devoted to anime. https://t.co/z3wVAcUJl1
이 페이지는 그동안 4chan의 /sci/ 게시판에 있었던 일들을 정리해놓은 위키 페이지였습니다. 이 위키에 앞에서 익명의 지나가던 유저가 적어놓은 증명도 포함되어 있었던 것이죠.
이를 읽어본 Robin Houston은 경악을 금치 못했습니다. 왜냐하면 그 동안 골머리를 썩던 문제가 7년전에 이미 너무 깔끔하게 증명이 되있었던 것이죠. 이후 그는 여러 사람들의 도움을 통해 원래의 스레드까지 확인할 수 있었으며, 동료 학자들과 협력을 통해 이 증명을 보다 더 깔끔하게 다듬어 논문을 작성하기로 결정합니다.
이렇게 [익명의 4chan 유저]를 공저자로 한 논문은 출판을 목적으로 지금도 열심히 작업중입니다.
물론 나중에 다른 발견을 통해 4chan의 유저가 제시한 값보다 더 적은 최솟값을 찾을 수도 있습니다. 실제로 이에 대한 논문을 작성중인 Robin Houston도 이를 더 개량할 수 있을 지 모른다는 의견을 제시하기도 했구요 하지만 그동안 수학자들을 골머리 썩였던 문제가 애니덕분에 증명되었다는 사실,
그리고 이 증명이 세상에 빛을 보는데까지 7년이라는 시간이 걸린 것을 보면이런 일이 또 생길 수 있을까 싶습니다.
P.S.
그래서 결국 하루히 문제의 답은 무엇이냐구요? 일단 지금까지의 결과를 통해 확인해보면 대략 [930억편]을 봐야되고, 한 애니메이션당 24분이 걸린다고 가정했을 때, 대략 [430만년]이 걸립니다.
참고로 인류가 처음으로 불을 사용하게 된게 대략 100만년 전 일입니다.
* 노틸러스님에 의해서 자유 게시판으로부터 게시물 복사되었습니다 (2019-04-09 15:36)
* 관리사유 : 좋은 글 감사드립니다.
통합규정 1.3 이용안내 인용
"Pgr은 '명문화된 삭제규정'이 반드시 필요하지 않은 분을 환영합니다.
법 없이도 사는 사람, 남에게 상처를 주지 않으면서 같이 이야기 나눌 수 있는 분이면 좋겠습니다."
(수정됨) 대단하군요. 수알못이지만 슬쩍 보니 치환군의 성질을 이용한 증명인가요? 누가 쉽게 이것도 내용을 비유적으로라도 풀이해주면 좋겠네요. 그리고 인류의 계통이 최초로 불을 사용한 것으로 추측되는 연대는 최소한 150만년 이전으로 알고 있습니다.(발견된 유적이 저러하니 아마도 최초사용추정연대는 더 올라가겠죠.) 이미 90년대부터 교양과학 서적들에서 그렇게 기술되었던 것이 기억나네요. 재미있게 읽었습니다. 세상에는 정말 대단한 사람들이 많아요.
