다시봐도 좋은 양질의 글들을 모아놓는 게시판입니다.
Date 2018/11/08 00:24:58
Name 플라스틱
Link #1 https://www.iflscience.com/editors-blog/an-anonymous-online-anime-fan-just-solved-a-problem-thats-been-eluding-mathematicians-for-decades/
Subject The Haruhi Problem - 덕후의 위대함 (수정됨)
1. 모든 것의 시작

4chan.md.jpg

우리나라에 디시인사이드가 있다면 미국에는 4chan이 있습니다. 그 막장성은 국내에서도 짤방으로 접하신 분들이 많을 거라고 생각됩니다.
이러한 막장성과 별개로 정치, 비디오 게임, 총기(?), 성인물(!) 등등 그야말로 다양한 주제의 게시판들이 존재하며 미국 인터넷에 꽤 강력한 영향력을 보이는 사이트라고 볼 수 있습니다.

이번에 할 이야기는 2011년, 그 중 /sci/, 과학 및 수학 보드의 한 스레드로부터 시작하게 됩니다....

Problem.md.jpg
문제는 하루히인데 왜 사진에 있는건 슈타인즈 게이트인지 무시합시다.

어느 날, /sci/ 보드에 다음과 같은 질문이 올라오게 됩니다.

[만약14편의 하루히 애니메이션을 가능한 모든 순서로 보기 위해선, 최소 몇 편을 봐야할까? 단, 겹쳐있는 순서도 포함한다.]

이 문제만 봐서는 잘 이해가 안 되실수 있기에, 더욱 더 간단한 버전으로 이야기를 해보도록 하겠습니다.
만약 이 문제의 대상이 스타워즈 오리지널 3부작이었음 어땠을까요?

starwars1.md.png

이 3편의 영화를 관람할 수 있는 순서의 가짓수는 총 6가지(123/132/213/231/312/321)입니다.
그래서 정말로 간단하게 생각한다면 총 18편의 영화를 봐야되겠죠?
하지만 위에서 말했듯이 겹쳐있는 순서도 포함하기 때문에 굳이 18편이나 볼 필요가 없습니다.
예를 들어, 123121321 의 순서로 9편만 관람을 하게 된다면, 위에서 확인한 모든 순서를 다 포함하는 것을 확인할 수 있습니다.
그러니까 대략 1일하고 15시간동안 스타워즈를 보는 것보단 19시간 정도만 걸려도 충분한다는 소리입니다.

아무튼 다시 본래 문제로 돌아가서, 이 문제는 대상이 하루히 애니메이션이었던 만큼 '하루히 문제'라는 이름이 붙여졌으며
어떻게보면 그냥 흘러가서 묻힐 수 있었던 이 스레드는 의외로 붐을 일으켜 꽤 다양한 답변들이 달리게 되었습니다.
물론 정말로 진지한 답변들만 달린건 아니었지만요..

이런 와중에, [익명의 지나가던 4chan 유저]가 답변을 달았습니다.

legend.png

"내 생각엔 n편의 애니메이션에 대해서 대해서 적어도 n!+(n-1)!+(n-2)!+n-3번을 봐야한다는 걸 증명할 수 있을 것 같아.
답변을 여러개를 달아야 할 것 같은데. 혹시 내가 놓친 실수가 있는지 살펴봐줘."

이렇게 시작한 답변은, 자신이 증명에 사용한 기호 및 아이디어의 설명을 시작으로 차근차근 증명을 시작하였고,
5개의 답변을 통해 자신의 증명을 마무리하였습니다.
이후에 다른 사람들도 이를 읽어보았지만, 뚜렷한 실수를 발견하지 못하기에 이에 수긍했고 다 만족하여 자기 할 일을 하러 돌아갔습니다.
그렇게 이 스레드는 사람들에게 잊혀지게 됩니다.

그런데.....

2. 문제의 진실


사실 이 문제는 수학의 한 분야인 조합론에서 다루는 Superpermutation에 관한 문제입니다.
(초순열이라고 번역할 수 있겠지만, 실제로 한국에서 이러한 용어를 사용하는지는 모르기에 영어로 계속 쓰도록 하겠습니다.)

Superpermutation이란 'n개의 문자'를 포함한 문자열을 전부 다 포함하는 문자열을 의미합니다.
이 'n개의 문자'를 앞에서 이야기한 애니메이션을 보는 순서로 치환하기만 하면 둘이 서로 같은 문제라는 것을 알 수 있습니다.

Superpermutation은 Daniel A. Ashlock 와 Jenett Tillotson라는 두 수학자에 의해 처음으로 그 개념이 나왔으며,
이를 소개한 논문에서 직접 자신들이 예상한 Superpermutation 길이의 최솟값들을 제시했습니다.

그런데 이 Superpermutation의 가장 큰 문제는, 문자의 갯수가 조금만 많아져도 그 길이가 기하급수적으로 증가한다는 사실이었습니다.

다시 한번 스타워즈로 돌아가서 이를 확인해봅시다. 만약 프리퀼 3부작까지 포함해서 6편을 본다면 어떨까요?

starwars2.md.png
하도 보는 순서에 대한 훈수가 많아서 그냥 다 보기로 했습니다.

이 때는 다음과 같은 순서로 보는 것이 최선이라고 알려져있습니다... 심호흡 하시고.....



1234561234516234512634512364513264513624513642513645213645123465123415
6234152634152364152346152341652341256341253641253461253416253412653412
3564123546123541623541263541236541326543126453162435162431562431652431
6254316245316425314625314265314256314253614253164523146523145623145263
1452361452316453216453126435126431526431256432156423154623154263154236
1542316542315642135642153624153621453621543621534621354621345621346521
3462513462153642156342165342163542163452163425163421564325164325614325
6413256431265432165432615342613542613452613425613426513426153246513246
5312463512463152463125463215463251463254163254613254631245632145632415
6324516324561324563124653214653241653246153264153261453261543265143625
1436521435621435261435216435214635214365124361524361254361245361243561
2436514235614235164235146235142635142365143265413625413652413562413526
41352461352416352413654213654123

이러한 순서로 대략 872편의 스타워즈를 대략 82일을 걸려서 관람하시면
더 이상 스타워즈 팬들한테 스타워즈를 어떤 순서로 봐야하는지 훈수질을 안당하셔도 된다는 소리입니다.

그런데 이 872이라는 숫자가 굉장히 Superpermutation에 있어서 굉장히 중요한 숫자였습니다.
왜냐하면 앞에서 이야기한 Daniel A. Ashlock 와 Jenett Tillotson이 n=6일 때 제시한 최소 길이였던 873보다 더 적었기 때문입니다!
이에 대해 많은 수학자들이 충격을 금치 못했고, 이제 Superpermutation의 길이의 더 적은 최솟값을 표현할 길을 찾아야 했습니다....

3. 뜻 밖의 발견

Robin Houston은 앞에서 확인한 n=6일때의 Superpermutation의 길이가 이전에 알려져있는 값보다 더 짧다는 사실을 처음으로 알린 사람입니다.
자신이 이러한 발견을 한 만큼, Superpermutation의 길이의 최솟값을 더 정확히 표현할 수 있는 방법에 대해서도 몰두하기 시작했습니다.

이후 4년의 시간이 흐르고 나서, 2018년 10월의 어느 날, 인터넷을 돌아다니던 그는 이상한 페이지를 하나 발견합니다.




이 페이지는 그동안 4chan의 /sci/ 게시판에 있었던 일들을 정리해놓은 위키 페이지였습니다. 이 위키에 앞에서 익명의 지나가던 유저가 적어놓은 증명도 포함되어 있었던 것이죠.

이를 읽어본 Robin Houston은 경악을 금치 못했습니다. 왜냐하면 그 동안 골머리를 썩던 문제가 7년전에 이미 너무 깔끔하게 증명이 되있었던 것이죠.
이후 그는 여러 사람들의 도움을 통해 원래의 스레드까지 확인할 수 있었으며, 동료 학자들과 협력을 통해 이 증명을 보다 더 깔끔하게 다듬어 논문을 작성하기로 결정합니다.

paper.md.png

이렇게 [익명의 4chan 유저]를 공저자로 한 논문은 출판을 목적으로 지금도 열심히 작업중입니다.

물론 나중에 다른 발견을 통해 4chan의 유저가 제시한 값보다 더 적은 최솟값을 찾을 수도 있습니다.
실제로 이에 대한 논문을 작성중인 Robin Houston도 이를 더 개량할 수 있을 지 모른다는 의견을 제시하기도 했구요
하지만 그동안 수학자들을 골머리 썩였던 문제가 애니덕분에 증명되었다는 사실,
그리고 이 증명이 세상에 빛을 보는데까지 7년이라는 시간이 걸린 것을 보면이런 일이 또 생길 수 있을까 싶습니다.

P.S.
그래서 결국 하루히 문제의 답은 무엇이냐구요?
일단 지금까지의 결과를 통해 확인해보면 대략 [930억편]을 봐야되고, 한 애니메이션당 24분이 걸린다고 가정했을 때, 대략 [430만년]이 걸립니다.
참고로 인류가 처음으로 불을 사용하게 된게 대략 100만년 전 일입니다.



* 노틸러스님에 의해서 자유 게시판으로부터 게시물 복사되었습니다 (2019-04-09 15:36)
* 관리사유 : 좋은 글 감사드립니다.

통합규정 1.3 이용안내 인용

"Pgr에는 "명문화된 삭제규정"이 반드시 필요한 사람은 안왔으면 좋겠습니다.
법 없이도 사는 사람, 남에게 상처 안주면서 같이 이야기 나눌수 있는 분이면 좋겠습니다."
츄지Heart
18/11/08 00:31
수정 아이콘
저는 하루히를 책으로만 읽겠습니다... ㅠㅠ
cluefake
18/11/08 00:31
수정 아이콘
에..음..
덕후는 위대하다!..?
나와 같다면
18/11/08 00:40
수정 아이콘
역시 덕후질은 괜히 머리 쓴다고 까불지 말고 얌전히 돈이나 내면서 즐겨야..
18/11/08 00:41
수정 아이콘
워.. 수알못이지만 흥미롭네요. 잘 읽었습니다 흐흐
데로롱
18/11/08 00:48
수정 아이콘
덕후의 위대함이란..
킬고어
18/11/08 00:55
수정 아이콘
(수정됨) 대단하군요. 수알못이지만 슬쩍 보니 치환군의 성질을 이용한 증명인가요? 누가 쉽게 이것도 내용을 비유적으로라도 풀이해주면 좋겠네요. 그리고 인류의 계통이 최초로 불을 사용한 것으로 추측되는 연대는 최소한 150만년 이전으로 알고 있습니다.(발견된 유적이 저러하니 아마도 최초사용추정연대는 더 올라가겠죠.) 이미 90년대부터 교양과학 서적들에서 그렇게 기술되었던 것이 기억나네요. 재미있게 읽었습니다. 세상에는 정말 대단한 사람들이 많아요.

http://www.vop.co.kr/A00000489324.html
코우사카 호노카
18/11/08 00:59
수정 아이콘
이게 하루히 5권 엔들리스 에이트인가 뭔가 하는것이더냐
18/11/08 01:29
수정 아이콘
굉장히 흥미롭네요~
불대가리
18/11/08 01:32
수정 아이콘
수포자 인생 20년차도 쉬이 읽히는 글이네요
필력에 추천드립니다
마스터충달
18/11/08 01:44
수정 아이콘
덕후는 세상의 발전에 기여합니다
세오유즈키
18/11/08 01:45
수정 아이콘
좋은 글 감사합니다.덕분에 오늘도 재밌는 글을 보네요.
프로피씨아
18/11/08 02:21
수정 아이콘
분명 저 익명도 수학이나 물리 전공자일텐데...

나중에 알아도 난감하겠네요 자기란걸 증명할 방법이 없으니
만년유망주
18/11/08 03:10
수정 아이콘
아 이런거 너무 좋아요 크크크
morncafe
18/11/08 03:56
수정 아이콘
'Good will hunting' 의 리얼 버전인가요? :)
브리니
18/11/08 04:19
수정 아이콘
혹시 큰그림 그린 휴스턴 본인 아닌가요? 애니보다가 이 아이디어를 만들었다 하기엔 부끄러워서? 하하
맥핑키
18/11/08 04:38
수정 아이콘
결국 덕후는 덕후들이 모인 곳에서 단지 덕질을 일삼았는데
위키의 집단지성과 정리벽 덕분에 세상에 나온거네요. 위키의 어시스트지만 사실상 0.9 골이라는 거죠?
18/11/08 05:37
수정 아이콘
덕후는 위대하군요
18/11/08 06:21
수정 아이콘
진짜 세상에 숨겨진 기인들 많아요.
Jedi Woon
18/11/08 07:06
수정 아이콘
덕질도 재능있는자가 더 덕스런 덕질을 할 수 있는거네요.....
아니면 원래 재능있는자가 덕질을 하는건가?
지바고
18/11/08 07:53
수정 아이콘
역시 덕후는 위대하네요...
근데 논문에서 this proof was inspired....영감을 얻은건가요? 아니면 증명이미 다 된걸 정리만 한건가요 크크 저자는 inspired라고 했지만...summerized 일지도.
홍승식
18/11/08 09:14
수정 아이콘
무슨말인지 모르니 가만히 있어야 겠다 (개구리콘)
노이즈캔슬링
18/11/08 09:34
수정 아이콘
무슨말인지 잘 모르겠지만 대단한건 알겠네요.

그나저나 본문의 오리지널 3부작이 저렇게 1,2,3편은 아니지 않나요?? (이게 제가 할수 있는 유일한 말...)
18/11/08 09:41
수정 아이콘
흥미로운 글이네요.
어찌보면 일회성에 가까운 커뮤니티의 글이지만, 때로는 이런 좋은 데이터로 나타날 수 도 있는 것이군요.
대단한 것 같습니다.
아이지스
18/11/08 10:48
수정 아이콘
잉여력이 해냈어요
-안군-
18/11/08 11:05
수정 아이콘
장'잉'정신이 이걸 또...
홍준표
18/11/08 13:32
수정 아이콘
저 문제를 좀 더 어렵게 하자면, 14편중 엔드리스 에이트 여덟편의 순서는 고려하지 않는다 이런 느낌이면 되겠군요.
세종머앟괴꺼솟
18/11/08 22:50
수정 아이콘
와개꿀잼크
MagnaDea
18/11/08 22:57
수정 아이콘
n이 6일때 n! + (n-1)! + (n-2)! + n - 3의 값은 867이니 저 논문이 맞다면 써주신 것 보다 더 나은 순서가 존재한다는 거군요.
Quantum21
18/11/08 23:28
수정 아이콘
그공식은 최소한 얼마만큼은 되야한다는 하한만 주는 것이지 그게 정확한 한계라는걸 의미하는게 아닙니다.
게다가 공식에 5를 넣으면 152 가 나옵니다만 5일때는 153이 진짜 최소값이라는건 이미 증명되어있죠! 그러니까 867보다 큰값중에 진짜 최소가 있을거라 추측됩니다.
MagnaDea
18/11/09 00:19
수정 아이콘
아. lower boundary 이지 lowest value가 아니라는거군요. 이해했습니다. 친절한 설명에 감사 드립니다.
세츠나
19/04/22 15:35
수정 아이콘
이거 재미있네요 크크
목록 삭게로! 맨위로
번호 제목 이름 날짜 조회
3042 그까짓 거 아빠가 사 줄게! [183] 글곰15403 19/01/24 15403
3041 나는 군대를 다녀왔으니 홍역은 걱정이 없다구!!! [114] 여왕의심복8776 19/01/23 8776
3040 하버드에서 나누었던 인상적인 대화 [53] 은때까치13235 19/01/20 13235
3039 [역사] 비운의 소련 외교관 막심 리트비노프 [19] aurelius4321 19/01/18 4321
3038 조지 워싱턴의 급박한 열흘 [32] OrBef8662 19/01/12 8662
3037 7살 어린 여직원에게 고백 받은 썰.txt [132] 위버멘쉬27470 19/01/12 27470
3036 나는 물수건이 싫었다. [21] 혜우-惠雨9103 19/01/04 9103
3035 십진법을 쓰는 인간들을 구경하러 온 이진법 세계 인간의 충고 [56] 2210935 19/01/01 10935
3034 [기타] 가히 역대급 명승부가 나온 카트라이더 리그(데이터주의) [51] 신불해8758 19/01/20 8758
3033 [LOL] 과 스타크래프트 E스포츠 프로의 종류 [65] 갓포티비6923 18/12/19 6923
3032 [히어로즈] Heroes, You're Fired. [76] 은하관제10434 18/12/14 10434
3031 삼행시 잘 짖는... 아니 잘 짓는 방법 [61] 228072 18/12/22 8072
3030 1592년 4월 부산 - 충렬공(忠烈公) [5] 눈시BB3754 18/12/19 3754
3029 자기 부라리 차이면 어떻게 아픈거야? [28] 졸린 꿈7773 18/12/12 7773
3028 귀소본X [16] 야누수4807 18/12/11 4807
3027 마미손과 회복탄력성 [49] 2216008 18/12/06 16008
3026 교통공학 이야기 - 5. 자율주행에 관한 쓸데없는 잡설들 몇가지 [76] 루트에리노6300 18/12/06 6300
3025 [여행]일본여행 올해 1년 12달간 12번갔던 후기 모아서 올려봅니다(다소 스압) [43] St.Johan7554 18/12/05 7554
3024 목숨 걸고 전쟁하던 옛 시대의 지휘관들 [54] 신불해13025 18/11/28 13025
3023 최초의 여신과 고자 아들이 로마제국에 취직한 이야기 - 키벨레와 아티스 [20] Farce6455 18/11/27 6455
3022 [기타] 원효대사 144Hz 해골물 [94] anddddna21301 18/12/04 21301
3021 [기타] [워3][RTS] '운영'에 대한 고찰 [31] 이치죠 호타루6525 18/12/01 6525
3020 정사 삼국지보다 재미있는 '배송지' 평 [51] 신불해14024 18/11/24 14024
목록 이전 다음
댓글

+ : 최근 6시간내에 달린 댓글
+ : 최근 12시간내에 달린 댓글
맨 위로