하루히 문제 : Superpermutation의 최소 길이

스즈미야 하루히의 우울‘이라는 들에게 대단히 유명한 애니메이션이 있다. 꽤 오래전에 방영된 작품이지만, 이것을 모르는 덕이 있다는 사실이 화제[1]가 될 정도인데, 여하간 해외에서도 Haruhism이라는 신조어가 생길 정도로 유명했었다. ㅎ

지금 검색해보니 방영시기가 2006년이네. 초 오래됐네 헐-_- 여하간 당시에 본인도 열심히 봤었는데, 로토스코핑으로 만든 전설의 그 라이브 장면하며, 악명 높은 엔들리스 에이트 등등 여러모로 확실히 epoch maker라는 사실은 부정할 수 없을 것 같다. (개인적으로는 새로운 스토리텔링 기법과 연출방법의 관점에서 엔들리스 에이트를 대단히 높게 평가함 ㅎ)

이 애니메이션은 TV 방영당시에는 원래 스토리 순서가 아니라 뒤죽박죽으로 재배열되어 방영되었는데, 각화의 마지막 차회 예고 코너에, 하루히가 ‘다음은 x편이야!’ 라고 외치면, 이 ‘아니야 x편이야!’ 라고 정정해주는 부분이 나온다. (오래돼서 워딩이 정확하지 않은데, 아무튼 그런 대사였음) 이 당시 하루히가 외친 숫자가 실제 스토리상의 사건전개 순서이고, 쿈이 외친 순서가 실제 방영순서가 된다. (DVD와 블루레이는 정상적인 순서로 발매되었다)

에피소드의 방영순서가 뒤죽박죽으로 재배열되어 있으므로, 보는 사람이 스토리의 순서를 맞춰야 하는 문제가 생긴다. 하루히 14개의 에피소드가 있을 때, 이를 나열하는 모든 경우의 수는 14! 가지가 되는데, 14! 가지의 모든 에피소드 방영순서를 포함하는 최단 시청순서를 묻는 질문을 생각할 수도 있다-_- 이런 걸 왜 생각하지-_-

좀 더 일반적으로, 주어진 n개의 문자에 대해 n! 가지 순열을 substring으로 모두 포함하는 최단 순열의 길이를 물을 수 있다. 이런 순열을 superpermutation이라고 한다. 예를 들어 n=3인 경우

123121321

은 123, 132, 213, 231, 312, 321을 모두 포함하고 있으므로 superpermutation이 된다. 물론 예상가능하겠지만, superpermutation의 최소 길이는 n이 커질 수록 극적으로 길어지는데, combinatorial explosion의 한 사례라 생각할 수 있을 것이다. 이 부분은 광기가 느껴지는-_- 일본과학미래관의 애니메이션 이야기[2]를 참고하기 바란다. ㅋㅋ

물론 가능한 모든 permutation을 줄줄이 이어붙여도 superpermutation이 되긴 하지만, 조건을 만족하는 최단길이를 추정하는 것은 어렵다. combinatorics 분야에서 나름 오래된 문제 같은데, 본인은 처음 봤다. ㅎㅎ 이 문제에 관해 유명한 하드 SF 작가인 Greg Egan 선생이 쓴 글[3]을 참고하시기 바란다. 그나저나 그렉 이건 선생의 ‘쿼런틴‘을 읽어보고 싶은데, 역서가 절판이라 구하기 어렵구만-_-

minimal superpermutation의 길이를 구하는 문제를 이와 같은 이유로 하루히 문제(Haruhi problem)라 부르고 있는 듯 하다.

간단한 논리로 lower bound가 n! + (n – 1)임을 쉽게 알 수 있는데, 일단 모든 permutation이 포함되어야 하므로 각 substring에 적어도 한 개의 문자가 있어야 하니 n!이고, 최초의 permutation은 n개의 문자를 포함하므로 n – 1개가 추가된다. 이 결과를 좀 더 improve하면 n! + (n – 1)! + (n – 2) 까지 올라갈 수 있다고 한다. 마운트 앨리슨 대학 소속의 Nathaniel Johnston 선생의 글[4]을 참고하기 바란다. 참고로 일전에 Look and Say Sequence 이야기를 하면서 Nathaniel Johnston 선생의 글을 소개한 적[5]이 있다.

그렇다면 왠지 induction으로 lower bound가 \sum_{k=1}^{n}k! 일 듯한 느낌적 느낌이 든다-_- 나름 오래된 추측인 듯한데, 2014년에 반례가 나온 것 같다.[6] n = 6일 때 1! + … + 6! = 873인데, 다음은 길이가 872인 n = 6의 superpermutation 이라고 한다.[6,7]

12345612345162345126345123645132645136245136425136452136451234651234156234152634
15236415234615234165234125634125364125346125341625341265341235641235461235416235
41263541236541326543126453162435162431562431652431625431624531642531462531426531
42563142536142531645231465231456231452631452361452316453216453126435126431526431
25643215642315462315426315423615423165423156421356421536241536214536215436215346
21354621345621346521346251346215364215634216534216354216345216342516342156432516
43256143256413256431265432165432615342613542613452613425613426513426153246513246
53124635124631524631254632154632514632541632546132546312456321456324156324516324
56132456312465321465324165324615326415326145326154326514362514365214356214352614
35216435214635214365124361524361254361245361243561243651423561423516423514623514
263514236514326541362541365241356241352641352461352416352413654213654123

헐… Johnston 선생의 글[7]의 앞부분에 vector space의 dimension 이야기가 나오는데, 본 블로그에서 했던 이야기[8]다. 역시나 induction은 함부로 쓸게 못 된다-_-

조금 기준을 완화하여 minimal superpermutation의 lower bound가 n! + (n – 1)! + (n – 2)! + (n – 3)이라는 부분이 현재까지 증명된 최선의 결과인데, 이 결과를 증명한 사람은 어느 익명의 애니메이션 덕-_-으로 추정된다고 한다. the verge에 관련기사[9]가 있다. 최초에 누군가가 4chan에 쓴 증명[10]의 개략적 내용을 누가 어느 위키 사이트[11]에 써 놓았는데, Robin Houston이라는 수학자가 논문으로 이를 정리하여 OEIS 서버에 업로드 했으니 확인할 수 있다.[12] Houston 선생의 블로그[13]에서도 관련 이야기가 있다.

왜 알려진 최상의 결과를 improve하는 증명을 익명으로 4chan에 작성하는 건지, 지나가던 오타쿠의 심리는 도통 모를 일이다-_-

.


2018.11.6
Mystery Math Whiz and Novelist Advance Permutation Problem (hacker news)

.


2018.11.19
The Haruhi Problem – 덕후의 위대함 (pgr21.com)

.


2019.2.4
스즈미야 하루히의 증명 (udaqueness.blog)

.


[1] ‘나가토 유키를 잘 모르는 세대가 나왔다’면서 일웹에서 화제, 하지만? (alonestar.egloos.com)
[2] 내 백과사전 Combinatorial explosion을 설명하는 애니메이션 2012년 9월 21일
[3] Superpermutations (gregegan.net)
[4] The Minimal Superpermutation Problem (njohnston.ca)
[5] 내 백과사전 읽고 말하기 수열과 콘웨이 상수의 증명 2014년 9월 16일
[6] Robin Houston, “Tackling the Minimal Superpermutation Problem”, arXiv:1408.5108 [math.CO]
[7] “Obvious” Does Not Imply “True”: The Minimal Superpermutation Conjecture is False (njohnston.ca)
[8] 내 백과사전 잘못된 수학적 믿음 2010년 6월 7일
[9] the verge An anonymous 4chan post could help solve a 25-year-old math mystery Oct 24, 2018, 4:33pm EDT
[10] https://warosu.org/sci/thread/S3751105#p3751197
[11] The Haruhi Problem (mathsci.wikia.com)
[12] Anomymous 4chan poster; Houston, Robin; Pantone, Jay; Vatter, Vince (October 25, 2018). “A lower bound on the length of the shortest superpattern” (PDF). OEIS. Retrieved 27 October 2018.
[13] Superpermutations: lower bound (bosker.wordpress.com)