PGR21.com
다시봐도 좋은 양질의 글들을 모아놓는 게시판입니다.
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
수정 아이콘
이거 재미있네요 크크
목록 삭게로! 맨위로
번호 제목 이름 날짜 조회
3421 실천해보니 좋았던 직장내 소소한 습관들 [42] visco2552 22/01/16 2552
3420 [성경이야기]야곱의 거짓말 [21] BK_Zju5386 20/12/10 5386
3419 난 뭘 벌어먹고 살 것인가 [77] 깃털달린뱀4973 22/01/15 4973
3418 [기타] 나는 어떻게 무공을 만들었는가 (1) - 디아블로2 레저렉션 [54] 험블1955 22/01/13 1955
3417 내가 겪었던 좋은 사람들 [25] 착한아이1965 22/01/13 1965
3416 연대는 사라지고 억울함만 남았다. 우리에게 무엇이 남을까? [185] 노익장2330 22/01/12 2330
3415 2021 플래너 모아보기 [26] 메모네이드1642 22/01/12 1642
3414 [NBA] 클레이 탐슨의 가슴엔 '불꽃'이 있다 [19] 라울리스타2251 22/01/10 2251
3413 [팝송] 제가 생각하는 2021 최고의 앨범 Best 15 [16] 김치찌개1953 22/01/09 1953
3412 코로나 때문에 집에서 홈술 해먹는것도 나름 재밌네요.jpg [25] insane1871 22/01/08 1871
3411 우량주식 장투가 말도 안 되게 어려운 이유 (사실상 거의 불가능한 이유) [84] 사업드래군2582 22/01/04 2582
3410 결혼 10년차를 앞두고 써보는 소소한 결혼 팁들 [62] Hammuzzi6945 22/01/02 6945
3409 대한민국 방산 무기 수출 현황 [48] 가라한6285 22/01/02 6285
3408 나도 신년 분위기 좀 느끼고싶다아아아! [10] 깃털달린뱀2890 22/01/02 2890
3407 중년 아저씨의 베이킹 도전기 (2021년 결산) (스압주의) [34] 쉬군6657 21/12/31 6657
3406 게임 좋아하는 아이와 공부 (feat 자랑글) [35] 담담3871 21/12/30 3871
3405 허수는 존재하는가? [91] cheme5756 21/12/27 5756
3404 고양이 자랑글 (사진 대용량) [31] 건방진고양이2676 21/12/30 2676
3403 마법소녀물의 역사 (1) 70년대의 마법소녀 [8] 라쇼3253 21/12/26 3253
3402 경제복잡도지수, 그리고 국가경쟁력 [27] cheme4332 21/12/21 4332
3401 등산 그리고 일출 이야기(사진 많음 주의) [36] yeomyung1389 21/12/21 1389
3400 [역사] 삼성 반도체는 오락실이 있어 가능했다?! / 오락실의 역사 [13] Fig.13065 21/12/21 3065
3399 [NBA] 현대 농구의 역사적인 오늘 [27] 라울리스타4058 21/12/15 4058
목록 이전 다음
댓글

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