유대인 킬러 문제

방금 본 유닼님의 블로그에 재미난 글[1]이 있길래, 본인도 따라 함 포스팅해 본다. ㅎ

러시아에서 유대인 핍박의 역사는 나름 오래됐는데, 러시아 역사는 본인도 잘 모르지만, 아무래도 러시아 정교가 메이져인 국가에서 개종을 거부했기 때문인 듯 하다. 러시아에서 고생했던 유대인 이야기는 꽤 여기저기서 자주 듣게 된다.

일전에 언론인 Masha Gessen이 쓴 페렐만 전기[2]에도 유대인 출신인 페렐만을 국제 수학올림피아드 러시아 대표에서 떨어뜨리기 위해 빡시게 출제한다는 이야기가 나오는데, 아무리 어려운 문제를 내도 페렐만을 도저히 탈락시킬 수 없어서-_- 결국 러시아 대표로 출전했다는 이야기가 나온다. ㅋㅋㅋ

참고로, Masha Gessen씨는 푸틴을 까는 기사를 쓴 걸[3] 보면, 언론인으로서 나름 대단한 사람인 듯 하다. 러시아의 언론인 환경이 험악하다[4] (방사능 홍차 라든지-_-)는 사실을 감안하면, 간이 꽤 큰 사람인 듯-_-

Tanya Khovanova 선생의 블로그[5]는 가끔 보는 편인데, 러시아 출신인 줄은 몰랐다. 수학자 족보[6]를 보니 Gelfand 선생의 제자라고 한다. 언급된 유대인 문제[7]를 몇 개 봤는데, 현대의 관점에서는 풀이법이 잘 알려진 것도 있긴 하다. 유닼님의 글[1]에서는 MIT 문제와 비교하는 짤이 있던데, 본인은 처음봤지만 일전에 본 1869년 Harvard 입학시험문제[8]랑 난이도가 비슷한 듯 한데, 아무래도 MIT 입학 문제의 난이도가 당대에서는 나름 고난이도에 속한 듯 하다. 1970-80년대라는 사실을 감안해도 유대인 문제들은 당대에는 진짜로 킬러문제로서의 역할을 할 수 있었지 않을까 싶다.

.


[1] 킬러 문제 (udaqueness.blog)
[2] 내 백과사전 [서평] 세상이 가둔 천재 페렐만 2012년 9월 14일
[3] 뉴스페퍼민트 푸틴과 죽은 시인의 사회 2013년 11월 29일
[4] 내 백과사전 저널리스트를 향한 테러 2010년 12월 1일
[5] https://blog.tanyakhovanova.com
[6] Tanya Khovanova (genealogy.math.ndsu.nodak.edu)
[7] Tanya Khovanova, Alexey Radul, “Jewish Problems”, arXiv:1110.1556 [math.HO]
[8] 내 백과사전 1869년 Harvard 입학시험문제 2011년 4월 12일

콴타 매거진 선정 2018 수학/컴퓨터 과학 주요 사건들

콴타 매거진에서 2018년에 있었던 수학 및 컴퓨터 과학 주요 사건들을 되짚어보는 기사[1]를 봤는데, 자꾸 나이 어린 사람들의 업적을 강조하네. 사실 30세 필즈메달 수상자[2]도 나오고, 아티야 선생은 노망-_-났으니[3], 기사[1]대로 젋은이의 해가 맞긴 맞나 보다.

기사[1]에서 언급한 양자 컴퓨터 관련 사건은 무슨 말인지 모르겠으니 넘어가고-_- 내가 보기에는 Scholze 선생이 모치즈키의 증명에 딴지를 건 사건[4]이 좀 큰게 아닌가 싶다. 그 딴지가 아니더라도 지금까지의 모치즈키 선생의 행동이 증명으로 인정받기에는 부족함이 많다[5]는건 확실하다. 이거 어떻게 돌아가고 있는지 모르겠네…

기사[1]에서 세 번째로 언급하고 있는 이야기가 인공지능을 fooling하는 내용인데, 컴퓨터에게 주어진 이미지 내의 사물 인식을 시킬 때, 이미지 내에 코끼리 그림을 넣는 사소한 수정만으로 주변 사물 인식이 크게 실패한다는 이야기[6] 같다. 이런 연구도 있는 줄은 오늘 첨 알았네. ㅎㅎ 일전에 이야기한 1픽셀 fooling[7]이 생각나는 대목이다. 참고로 영문법에서 Elephant in the Room이란, 누구나 그 존재를 알고 있으나 모든 이가 그 존재를 무시하거나 언급을 꺼리는 상황을 가리키는 idiom임.

기사[1]에서 다섯 번째로 Goldfeld conjecture를 풀었다는 이야기가 나오는데, 뭔 문제인지는 잘 모르겠음..ㅠㅠ 타원 곡선의 분류 문제인 듯 함. 하바드 대학원생이 풀었다고 하는데, 대학원생이 40년짜리 오픈 문제 풀었으니 흔한 사건은 아닌 듯 하다. ㅎㅎㅎ

기사[1]에서 마지막으로 언급하는 이야기가 그 하루히 문제[8]-_-다. 본 블로그에서 나름 자세히 다루었으니 ㅋㅋㅋㅋ 참고하시라. ㅋㅋㅋ 콴타 매거진에서도 기사[9]로도 나와 있다.

.


[1] 콴타 매거진 The Year in Math and Computer Science December 21, 2018
[2] 내 백과사전 30세 필즈 메달 수상자 2018년 8월 2일
[3] 내 백과사전 Atiyah 선생의 리만 가설 증명? 2018년 9월 21일
[4] 콴타 매거진 Titans of Mathematics Clash Over Epic Proof of ABC Conjecture September 20, 2018
[5] 내 백과사전 모치즈키의 abc 추측 증명에 대한 논란 2017년 12월 22일
[6] Amir Rosenfeld, Richard Zemel, John K. Tsotsos, “The Elephant in the Room”, arXiv:1808.03305 [cs.CV]
[7] 내 백과사전 1픽셀로 deep neural network를 무력화 하기 2017년 10월 31일
[8] 내 백과사전 하루히 문제 : Superpermutation의 최소 길이 2018년 11월 2일
[9] 콴타 매거진 Mystery Math Whiz and Novelist Advance Permutation Problem November 5, 2018

약탈적 저널 : 오픈 액세스 운동의 부작용

대충 분위기 보니 내가 제일 늦게 안 듯 하지만-_- 여하간 오픈 액세스의 허점을 악용한 약탈적 저널 논란이 커지는 듯 하다. 이 사태를 정리한 기사[1,2,3]를 봤는데, 특히 수학계는 똥이 된 듯-_- 과거에 본인도 오픈 액세스 운동을 옹호하는 글[4]을 썼지만, 이제 오픈 액세스를 무조건적으로 옹호하기도 어렵게 된 것 같다.

이와는 별개로 중앙일보 최준호 기자가 감동근 교수에게 사실관계와 논리없이 소송 협박[5]을 일삼고 있으니 학계윤리 뿐만 아니라 기자윤리까지 땅에 떨어진 것 같다.

.


2019.1.15
동아사이언스 논문 무료 개방 운동 ‘플랜S’ 확산 2019년 01월 14일 03:00

.


[1] 뉴스톱 ‘상위 1% 연구자’ 논란의 이면 ‘오픈 액세스’ 운동 2018.12.13 00:10
[2] 뉴스톱 ‘사기 논문’과 ‘가짜 편집자’…약탈적 저널이 심각하다 2018.12.20 01:53
[3] 뉴스톱 아가왈과 경상대 수학자는 어떻게 ‘세계 1%’가 됐나 2018.12.26 07:05
[4] 내 백과사전 The Cost of Knowledge : Elsevier 보이콧 운동 2012년 4월 10일
[5] ‘세계 1% 연구자’를 둘러싼 논란 (brunch.co.kr/@dkam)

종이접기의 과학

매년 크리스마스 직전이 되면 이코노미스트지는 더블 이슈를 발행하고, 크리스마스 한 주는 쉰다. 이 크리스마스 더블 이슈에 가끔 잡다한 이야기들도 나오는데, 올해도 재미있는 기사[1]가 있어 포스팅해본다. ㅋ 기사[1]가 꽤 길지만 나름 재미있으니 일독을 권함. 본 포스팅에서 출처가 표시되지 않은 정보는 대부분 위키피디아와 이코노미스트지의 기사[1]가 출처다.

눈금없는 자와 컴퍼스를 이용하여 평면도형을 구성해 내는 작도 문제는 유명한데, 평면상의 모든 점들에 도달할 수 없다는 사실이 증명되어 있다. 예를 들어, 단위 길이의 \sqrt[3]{2}배의 위치한 점에 작도만으로 도달할 수 없다. 그러나 정사각형의 종이접기로는 \sqrt[3]{2}에 도달이 가능한데, 나아가 후지타-하토리 공리에 의해 임의의 삼차방정식을 푸는 것도 가능하다. 하토리 코시로(羽鳥公士郎) 선생의 홈페이지[2]에 이 과정이 설명되어 있으니 참고 바란다.

이러한 유희적 종이접기는 서구권에서 일본식 명칭인 오리가미(Origami; 折り紙)라는 이름으로 널리 알려져 있다. 나름 매니아들이 꽤 있는 장르인 모양인데 International Meeting on Origami in Science, Mathematics and Education 이라는 학회도 있는 듯 하다.

이러한 오리가미를 교육쪽에 활용하려는 시도는 꽤나 일찍이 있어왔던 모양인데, 유아교육의 선구자이자 유치원 제도의 창시자인 Friedrich Fröbel도 종이접기를 통해 기하학 교육을 시도한 최초의 인물이라고 한다. 이코노미스트지 기사에 오리가미의 발전에 기여한 건축가, 교육가, 수학자, 과학자 등등 다양한 분야의 선구적 사람들의 이름이 등장한다.

Lillian Oppenheimer는 위키피디아에 따르면 미국 오리가미 대중화의 선구자로 소개되어 있다. 오리가미 센터(OrigamiUSA의 전신)를 설립하고, ‘origami’라는 단어를 대중화했다고 한다. 한편 레이저 물리학자인 Robert Lang이라는 사람이 오리가미로 꽤나 유명했던 모양인데, 이 사람 홈페이지[3]도 있다. 홈페이지[3]에 유튜브 영상이 몇 개 있는데, 나름 정정하게 사시는 듯. ㅎㅎㅎ

크리스마스 시즌을 맞아서 Erik Demaine이라는 사람이 단 한번의 가위질로 크리스마스 트리를 만드는 법을 만들었다고 하는 영상[4]을 봤다. 재생시간 1분 2초.

Erik Demaine이 누구인가 했는데, 위키피디아에 따르면 MIT 컴공과 교수라고 한다. 14살에 대학을 졸업하고 20살에 박사학위를 받았다고 하니, 엄청 천재인 듯-_- 근데 페북 비디오[4] 댓글에는 가위질이 1번이 아니라 3번이라고 딴지를 거는 댓글이 많다. ㅋㅋㅋㅋㅋ 실제로 접어보고 싶은 사람을 위해 이코노미스트지에서 인쇄용 pdf 파일[5]을 제공하고 있으니, 인쇄해서 실제로 접어보면 된다. 근데 나는 귀찮아서 안 해봤음-_-

여하간 이 ‘오리가미’가 실용적으로 도움이 된 극적인 사례가 바로 미우라 접기인데, 우주선의 솔라패널을 쏘아 올릴 때, 최대한 작은 사이즈로 접었다가 우주에서 펼치는 법에 응용된다고 한다. 미우라 접기가 어떤 방식으로 되는지 위키피디아에 gif 동영상이 있으니 보면 이해가 될 것이다. 마찬가지로 위에서 언급한 pdf 파일[5]에 미우라 접기도 들어 있다.

이러한 오리가미 테크닉은 물질을 최소 부피가 되도록 접는데 어디든 응용범위가 있는 것 같다. 예를 들어 인체의 동맥에 stent를 주입하여 혈관확장을 하는 시술의 경우에도 stent를 최소부피로 접어 넣는 과정에서 오리가미 테크닉이 활용된다고 한다. 오호~ 이런 응용법이!!

기사[1] 뒤쪽에 요시모토 입방체 이야기가 나오는데, 설명만으로는 이해가 어렵다. 유튜브에 요시모토 입방체의 영상[6]이 있으니 참고 바란다. 이런 퍼즐을 응용하여 교통수단에 엔진을 장착할 때 최소 공기저항이 되도록 설계할 수 있다고 한다. 이 덕분에 연간 수백만 달러의 연료비 절약이 가능하다고 하다고 한다. 어째서 그런 건지 짐작컨대 아마 공기저항이 적은 shape에 엔진을 끼워 넣어야 하는 문제를 해결하기 때문이 아닌가 싶다.

여하튼 뭐든 쓸데없어 보이는 것도 잘 연구하면 쓸데있다는 교훈이…-_-

.


[1] 이코노미스트 Origami spreads its wings Dec 18th 2018
[2] Origami Construction (origami.ousaan.com)
[3] https://langorigami.com
[4] How to make a paper Christmas tree in just one cut (facebook video 1분 2초)
[5] https://infographics.economist.com/2018/xmas/Origami.pdf (pdf 1.78MB)
[6] Yoshimoto Cube Puzzle | BeatTheBush (youtube 3분 40초)

단편영화 : 대안수학 Alternative Math

유튜브[1]를 보니 단편영화가 올라와 있던데, 쪼금 재미있음. ㅋ 원래는 vimeo 영상[2]인 듯 하다. 페북 페이지[3]도 있다. 이런저런 상도 많이 받은 듯. 재생시간 9분 6초.

vimeo[2]로 봐도 되긴 한데, 한글 자막이 없는 듯 하다. 유튜브[1]에는 고맙게도 한글 자막이 있으니 편하게 볼 수 있다.

아무래도 일전에 트럼프 행정부에서 일어난 ‘대안적 사실‘ 소동[4]을 비꼬는 영화 같다. 이런 주제로 영화를 만들 줄은 꿈에도 몰랐네. ㅎ

유튜브[1] 댓글 중에 ‘javascript’라는 말에 빵 터졌다. ㅋㅋㅋㅋㅋ 와 진짜 깬다. ㅋㅋㅋㅋ

.


[1] 대안 수학 (Alternative Math) | 단편 영화 (youtube 9분 6초)
[2] Alternative Math (vimeo 9분 6초)
[3] https://www.facebook.com/alternativemath/
[4] 내 백과사전 트럼프가 리만 가설을 증명한다면? 2017년 2월 7일

Microsoft Mathematics 4.0

지인이 알려줘서 알게 된 사실인데, 윈도우즈 OS용 sage도 배포되고 있었다. 헐… 초 몰랐다. 예전에는 윈도우즈 용이 없어서 윈도우즈에서는 sage를 간접적으로만 쓸 수 있었는데, 나름 활용성이 높아지지 않을까 싶다. 근데 본인은 이제 maple에 너무 익숙해져서 바꾸기 힘들다-_-

마찬가지로 지인이 알려줘서 알게 된 사실인데-_- 마이크로소프트에서도 윈도우즈 OS 플랫폼의 계산기를 만들어 배포하고 있는 줄 처음 알았다. 이름하여 Microsoft Mathematics인데, 가장 최근 버전이 2011년에 배포된 버전 4.0이다. 물론 freeware이다. 꽤 오래된 소프트웨어 인 듯 한데, 왜 여태 몰랐지??? ㅋ

마이크로소프트 홈페이지[1]에서 다운로드 가능하다.

나름 symbolic calculation도 가능해서 (x+y)^{12}의 전개나 \sqrt{7-4\sqrt{3}}-(2-\sqrt{3}) 같은 것도 계산해준다. 간단한 3차원 그래프도 그려주고 마우스로 회전도 가능하다. 오오!! 본인이 어릴 때는 mathematica에 이 기능이 없어서, 이것 때문에 maple에 매료되었었다. ㅎㅎ 행렬 계산이나 간단한 통계처리도 가능하다.

위키피디아의 CAS항목을 보니, 아마 사용자 프로그래밍이 안돼서 완전히 CAS로서 대접은 못 받는 듯 하지만, 여하간 가벼운 계산은 거진 대부분 될 듯 하다.

근데 일전에 본 하트의 방정식[2]을 그려보니 너무 복잡해서 못그리겠다-_-고 에러메세지가 나온다. 이런 걸 무료소프트웨어로 그리려면 sage나 일전에 이야기한 surfer[3] 같은 걸 써야할 것 같다. 아무래도 이걸로 실전적 계산은 좀 힘들듯 하다. 프로그램이 꽤 가벼운데, 학교 선생님들이 간단한 계산들을 손으로 하기 귀찮을 때 유용할 듯. ㅎㅎ 간단한 계산은 geogebra도 유용하지만 약간 용도는 다르니, 섞어 쓰는 것도 나쁘지 않을 듯 하다.

.


[1] Microsoft Mathematics 4.0 (microsoft.com)
[2] 내 백과사전 하트의 방정식 2011년 1월 26일
[3] 내 백과사전 SURFER : 삼차원 음함수를 그래프 그리는 프로그램 2015년 2월 6일

Missing square puzzle의 응용

Missing square puzzle이라는 굉장히 유명한 퍼즐이 있는데, 눈으로 감지하기 어려운 미세한 면적의 차이를 이용한 트릭을 응용한 퍼즐이다. 이 퍼즐 자체는 심오한 이론이 있는 것도 아니고, 너무 유명해서 별로 할 이야기가 없을 줄 알았는데, 그게 아니었다. ㅋㅋ

池田洋介라는 마술사의 페이스북[1]을 팔로잉 하고 있는데, 가끔 재미있는 영상을 올려 놓는다. 예전에 그의 open/close 문자 트릭[2] 때문에 알게 된 사람인데, 지금보니 홈페이지[3]도 있네. 수학 참고서[4]도 쓰는 걸 보면 나름 수학적 배경지식이 있는 사람인 듯 하다. 그의 페이스북에서 Missing square puzzle을 응용한 영상[5]을 봤는데, 나름 독창적인 듯 하여 나도 블로그에 올려본다. ㅎㅎ 재생시간 3분 34초

당연히 수학적으로는 별거 없지만, 독창성이나 창의성이라는 관점에서 놀라운 작품이 아닌가 싶다. 어릴 적에는 이런거 초 개무시했는데-_- 늙어서 보니 뭔가 대단하다. ㅋㅋㅋ 술먹고 봐서 그런가. ㅋㅋ

.


[1] https://www.facebook.com/IkedaYosuke630
[2] Revolutionary Sign Board (youtube 1분)
[3] https://www.yosuke-ikeda.com/
[4] 数学I・A入門問題精講 単行本(ソフトカバー) (amazon.co.jp)
[5] Square Puzzle by Yosuke Ikeda (facebook video 3분 34초)

3D 프로그래밍에서 사원수 제거?

몰랐는데 3D 그래픽 프로그래밍에서 Quaternion이 상당히 많이 쓰인다고 한다. 헐. 이런 쓸데없어 보이는 게 실용적 용도가 있으리라고는 꿈에도 몰랐네-_-

아시다시피 Quaternion은 복소수를 확장한 수집합인데, 공간상의 회전을 구현할 때 3D 게임그래픽 엔진에 널리 쓰이는 것 같다. 아마 3D 그래픽 프로그래머들은 많이 배우시는 듯.

해커뉴스[1]에서 3D엔진에서 사원수를 제거하자는 취지의 글[2]이 올라와 있던데, 이미 3D 그래픽 프로그래머들 사이에서 나름 논란적인 주제[3]인 것 같다. 사실 복소수도 현실과의 거리감이 있는 수라는 느낌이 드는데, 복소수를 확장한 number system의 괴이한 operation을 공부해서 프로그래밍하는 것에 거부감을 느끼는 것도 무리는 아닐 듯 하다. ㅎ

글[2]을 대충 봤는데, bivector를 써서 수학적으로 사원수를 회피하는 방법을 구현하는 것 같다. bivector는 처음 봤네. ㅎㅎㅎ 유명한 개념은 아닌 듯 하다.

사이트[2] 주인이 유튜브 영상[4]도 만들었으니, 그 정성은 인정해줄만 하다. ㅎㅎ 개인적으로는 지식을 학습할 때 영상을 보는 건 핵심을 알기가 답답해서, 글로 읽는 것을 더 선호함.

근데 bivector를 공부할 정도면 그냥 quaternian을 공부해도 무리는 없지 않을까 싶다-_- 어차피 수학적 난해함에 거부감이 있어 quaternian을 거부하면, bivector의 vector calculus도 거부감은 똑같을 것 같다. ㅎㅎㅎ

.


[1] Let’s remove Quaternions from every 3D Engine (hacker news)
[2] Let’s remove Quaternions from every 3D Engine (marctenbosch.com)
[3] Do We Really Need Quaternions? (gamedev.net)
[4] Let’s remove Quaternions from every 3D Engine (Intro to Rotors from Geometric Algebra) (youtube 15분 27초)

하루히 문제 : 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)

.


[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)