다시봐도 좋은 양질의 글들을 모아놓는 게시판입니다.
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)
* 관리사유 : 좋은 글 감사드립니다.



츄지Heart
클릭하면 해당 댓글의 단축주소가 복사됩니다.
18/11/08 00:31
저는 하루히를 책으로만 읽겠습니다... ㅠㅠ
cluefake
클릭하면 해당 댓글의 단축주소가 복사됩니다.
18/11/08 00:31
에..음..
덕후는 위대하다!..?
나와 같다면
클릭하면 해당 댓글의 단축주소가 복사됩니다.
18/11/08 00:40
역시 덕후질은 괜히 머리 쓴다고 까불지 말고 얌전히 돈이나 내면서 즐겨야..
emonade
클릭하면 해당 댓글의 단축주소가 복사됩니다.
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권 엔들리스 에이트인가 뭔가 하는것이더냐
eunviho
클릭하면 해당 댓글의 단축주소가 복사됩니다.
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
덕후는 위대하군요
norrell
클릭하면 해당 댓글의 단축주소가 복사됩니다.
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가 아니라는거군요. 이해했습니다. 친절한 설명에 감사 드립니다.
목록 삭게로! 맨위로
번호 제목 이름 날짜 조회
3017 조심스럽게....한번 올려보겠습니다 [63] 태양연어15008 18/11/16 15008
3016 고기가 먹고 싶었던 제국 - 아즈텍 [70] Farce11792 18/11/14 11792
3015 The Haruhi Problem - 덕후의 위대함 [30] 플라스틱6976 18/11/08 6976
3014 술 한잔. [16] ohfree4452 18/11/06 4452
3013 진순신, 그리고 <이야기 중국사> [18] 신불해4975 18/11/02 4975
3012 [기타] 진지글)인싸가 게임업계를 망치고 있다! [248] 아이즈원39290 18/11/27 39290
3011 Case Study : 포드 핀토(Ford Pinto)에 관련한 세 가지 입장 [13] Danial3944 18/10/31 3944
3010 이름부터가 북쪽의 땅 - 노르웨이 [36] 이치죠 호타루7523 18/10/27 7523
3009 TMI - Too Much Information 에 관하여 [69] 앚원다이스키7795 18/10/24 7795
3008 메흐메드 알리가 이집트를 근대화 시키다 - "그래서 지금 행복합니까?" [37] 신불해7524 18/10/18 7524
3007 고기의 모든 것, 구이학개론 2부 #1 (들어가며 - 구이의 역사) [34] BibGourmand3938 18/10/15 3938
3006 어머니, 저는 당신을 배려하지 않습니다. [93] EPerShare12038 18/10/11 12038
3005 나를 나로 만들어줬던 강점이 나의 한계가 되는 순간 나는 무엇을 해야할까 [16] Lighthouse7556 18/10/06 7556
3004 고려 말, 요동의 정세는 어떤 상황이었을까? [25] 신불해7850 18/10/05 7850
3003 너..혼밥하는 찐따구나? [125] 현직백수15509 18/10/04 15509
3002 미국 시골 치과의사의 치과 이야기 [35] 쭈니9046 18/10/03 9046
3001 긴 역사, 그리고 그 길이에 걸맞는 건축의 보물단지 - 체코 [21] 이치죠 호타루6241 18/09/29 6241
3000 청산리 전역 이야기 [37] 류지나8372 18/09/26 8372
2999 D&D2의 추억 한조각 [43] Aquaris7689 18/09/22 7689
2998 (삼국지) 형주 공방전 (1) [92] 글곰8330 18/09/20 8330
2997 어느 햄버거집의 마지막 손님 [51] 지니팅커벨여행12827 18/09/18 12827
2996 유럽이라고 다 잘 사는 건 아니라만 - 몰도바 [48] 이치죠 호타루17563 18/09/09 17563
2995 수학적 아름다움은 물리학을 어떻게 이끌었는가? [104] cheme16732 18/09/06 16732
목록 이전 다음
댓글

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