이에 착안해 2011년 9월 13일 4chan의 한 유저가 과학과 수학을 다루는 /sci/ 게시판에 다음과 같은 질문을 던졌다. “「스즈미야 하루히의 우울」 1기 총 14화의 모든 가능한 순서가 각각 연속적으로 등장하도록 에피소드들을 배치한다면 최소한 몇 화가 필요할까?”
이렇게 1에서 까지의 가능한 모든 개의 순열이 전부 연속적으로 등장하는 수열은 원래 수학에서 superpermutation이라 불렸으며, 그 최소의 길이를 묻는 이 문제는 1993년 Daniel Ashlock, Jenett Tillotson의 페이퍼에서 처음 등장했다.[1]
Numberphile에서도 다룬 적이 있다
일 때의 그 최솟값은 각각 1, 3, 9, 33, 153으로 나타나게 되는데, 그 값이 와 같아 이렇게 나타나는 것이 아니냐는 의견이 대두되었다. 그러나 이 예상대로라면 이면 최솟값은 873이어야 하지만, 2014년 Robert Houston이 872개의 수로 이루어진 superpermutation을 찾아 그 예상을 깨뜨린다.[2]
Houston은 외판원 문제를 푸는 휴리스틱을 이용해서 위 예시를 찾았다. 각각의 순열을 ‘도시’로 보고, 한 순열에서 다른 순열로 가기 위해 몇 개의 수를 더 붙여써야 하는지를 계산해 그 값을 두 도시 사이를 움직일 때의 비용으로 보면 (예컨대 123에서 231로 갈 때는 123→1231→231로 한 개만 붙이면 되므로 비용은 1, 123에서 312로 갈 때는 123→12312→312로 두 개를 덧붙여야 해서 비용은 2) 외판원 문제의 한 경우로 볼 수 있게 되는 것.
다시 하루히 문제로 돌아가, 4chan에 올려진 질문에 대해, 질문이 올라오고 며칠 지나지 않아 다른 한 유저가 화가 주어졌을 경우 필요한 에피소드 수의 최솟값은 최소 임을 증명해 올렸다. 그러나 이 풀이는 학계에서 큰 관심을 받지 못해 검토되지 않은 채로 인터넷 한 구석에 박혀있게 되었다. 그러다 John Baez가 초기치 예측의 실패에 대한 트윗을 쓰며 2014년 Houston이 발견한 길이 872의 superpermutation을 소개했고, 이를 읽은 SF 소설가 Greg Egan이 2018년 10월 20일 최솟값의 상한 을 찾게 되었으며 이에 따라 4chan에 올려진 하한에 대한 풀이도 재조명을 받게 되었다. (사실 그 전까진 앞서 말한대로 일 것 같다는 예상 때문에, Houston과 Egan의 상한 업데이트 이전까지는 하한에 대해서는 주목을 받기 힘든 상황이었기도 했다)
결국 2018년 10월 25일 Robin Houston, Jay Pantone, Vince Vatter가 이 증명을 검토한 후 결과를 정리해 페이퍼를 썼다.[3] 이 사연에 대해서는 Quanta MAgazine에 기고된 기사를 참조하는 것도 좋다. (여담이지만 Greg Egan은 1994년 한 소설을 발표해 필립 K. 딕 상 후보로도 오르기도 했는데 그 제목은 우연찮게도 “Permutation City”였다고)
증명은 elementary하고 간결하다. Greg Egan처럼 순열을 점으로 하는 그래프를 잡고 한 순열에서 뒤에 개의 수를 붙이는 식으로 다른 순열을 얻을 수 있다면 그에 해당하는 directed edge with weight 를 준다. 단 12345에서 34512로 가는 변은 12345에서 23451, 23451에서 34512로 가는 두 변이 있게 되는데 이런 경우는 변을 그리지 않는다. (반면 12345→34521은 이에 해당되지 않아 weight 2의 변으로 남는다) 그러면 모든 꼭지점을 한 번 이상씩 지나는 경로 을 찾되 그 경로의 가중치 가 최소가 되도록 해야한다. 우리가 찾는 superpermutation의 최소 길이는 이 경로의 최소 가중치에 을 더한 값이 된다.
임의의 순열 은 항상 로 화살표가 그려진다. 이런 변 번을 거치면 의 모든 cyclic rotation들이 포함되는 cyclic class를 얻게 되며 모든 순열들은 개의 class로 분할된다. 한 편, 도 변으로 연결되는데, 이를 편의상 좋은 변이라고 부른다. 처음 한 순열 에서 시작해 cyclic class의 원소들을 차례로 훑은 뒤, 마지막 순열에서 좋은 변으로 연결하고, 거기서 또 cyclic class의 원소들을 차례로 훑고, 마지막 순열에서 좋은 변으로 연결하고, 이를 계속 되풀이하면 총 개의 화살표를 거쳐 다시 원래 로 돌아온다.
“좋은 변”은 주황색으로 표시되었다 Source: [3]
이렇게 완성된 싸이클을 에 의해 생성된 2-loop이라고 부르도록 한다. 그러면 이 2-loop는 에 의해서 생성된 2-loop이기도 하다는 것을 알 수 있다. (위 예시에서 파란 색으로 표시된 순열들이다. 맨 끝의 만 고정하고 나머지 개를 cyclic rotation한 것들이라고 보면 된다) 따라서 총 개의 2-loop들이 나올 수 있게 된다. 여기서 한 가지 정의를 내리는데, 만약 어떤 경로가 로 향하는 가중치 2 이상의 변을 포함한다면, 이 경로가 에 의해 생성된 2-loop에 “진입”했다고 말하도록 한다. (굳이 2-loop 내부의 변을 지날 필요가 없다는 점을 주의한다. 예컨대 가중치 3인 어떤 다른 변으로 에 도착했더라도 이 경로는 에 의해 생성된 2-loop에 진입한 것이 된다)
이제 경로 에 대해, 이 경로가 지나온 서로 다른 순열의 개수를 , 에서 까지 지나오며 완성시킨 cyclic class(즉 모든 개의 cyclic rotation들을 다 포함하는)의 개수를 , 이 경로가 진입한 적이 있는 2-loop의 개수를 으로 정의한다. 그러면
성립함을 보일 수 있게 된다.
증명은 수학적 귀납법을 쓴다. 인 경우 이라 성립한다. 이제 길이 인 경로에 대해 성립함을 가정하고 까지 지나온 상황에서 을 추가했을 때 네 값 가 어떻게 변화하는지를 살펴보도록 한다. 먼저 항상 의 값은 각각 최대 1씩만 증가할 수 있다는 사실을 염두에 두도록 한다.
만약 이라면 은 같은 cyclic class에 놓여야 해서 의 값은 변하지 않는다. 만약 을 한 번도 지난 적이 있었다면 는 변하지 않고 는 최대 1까지 증가한다. 그렇지 않다면 는 1 증가하지만 시점에서 cyclic class가 완성되지 않았으므로 는 변하지 않는다. 어떤 경우든 우변은 최대 1까지만 증가되고 좌변은 1 증가하여 부등식이 계속 성립한다.
만약 이라면 좌변은 3 이상 증가하고 우변은 가 각각 최대 1씩 증가해야 해서 여전히 부등식이 성립한다.
만약 라면 이어야 한다. 이 때, 가 1만큼 증가하면 는 증가하지 않음을 보인다. (이게 성립하면 중 최대 2개까지만 1 증가할 수 있어 우변은 최대 2 증가하게 되고 부등식이 성립하게 된다.) 만약 이라면, 시점에서 한 cyclic class가 완성되었음을 의미한다. 따라서 은 그 이전에 지난 적 없는 점이어야 하며, 더불어 이 cyclic class에 속하는 다른 순열 은 이전에 이미 한 번 지났다는 이야기가 된다. 은 경로에서 번째에서 최초로 등장했기 때문에 이 경로에서 이전의 순열은 일 수가 없고, 따라서 가중치 2 이상인 변을 지나 로 와야만 한다. 따라서 현재 경로는 에 의해 생성된 2-loop을 진입한 적이 있게 된다. 그런데 와 은 마지막 항이 같고 앞의 항은 서로 cyclic rotation한 꼴이므로 앞서 본 바에 의해 같은 2-loop을 생성한다. 따라서 을 추가해도 의 값은 변하지 않는다.
위와 같이 를 얻고 나면 거의 끝난 셈이다. 만약 경로 이 모든 순열을 지났다면 이고, cyclic class 개수가 이므로 이다. (으로 한 cyclic class가 완성된다면 -1이 되어야 한다) 또한, 각각의 2-loop은 개의 순열을 갖고 있으므로 이 경로는 개 이상의 서로 다른 2-loop에 진입했어야 한다. (한 2-loop에 진입한 상태에서 변들을 따라가다가 다른 2-loop으로 옮겨 진입하는 순간의 개수를 센다고 생각한다) 따라서 가 되므로,
을 얻어 superpermutation의 최소 길이는 이상이어야 한다.
결론적으로, Egan과 한 익명의 4chan 유저에 의해 -superpermutation의 최소 길이를 이라 하면
이 증명된 것이다.
이 상한과 하한을 더 개선하는 것은 아직도 현재진행형이다. 정말 말 그대로 현재진행형이다. 위의 superpermutation과 하루히, 4chan 이야기를 다룬 standupmaths의 영상이 올라왔는데, (의 예시를 발견한 Robin Houston이 게스트) 2019년 2월 (2월 된지 며칠 지났다고) 이 영상에 누군가가 다음과 같은 리플을 남겼다.
현재까지 알려진 상한(Egan)에 의하면 일 때의 상한은 5908인데, 누군가가 5907자리의 7-superpermutation을 리플로 올린 것. 그는 (유튜브 닉네임은 Charlie Vane, 실명은 Bogdan Coanda로 밝혀졌다) Robin Houston이 초대한 구글 그룹 페이지에서 자신이 이를 발견한 경위를 설명했다.
비록 조합론의 언저리 저변에 있는 문제이긴 하지만 이렇게 서브컬쳐가 수학 문제의 정사에 편입되어 Haruhi problem이라고 불리기도 하는 것이나, 4chan과 유튜브 등의 리플의 형태로 문제가 조금씩 해결되는 양태 등이 자못 흥미롭다. 이 모든 것도 작중 인물 하루히의 의향에 맞춰 제4의 벽을 넘어 개변된 것이면 어떨까 싶기도.
Elegant Math 계정에서 작성한 트윗 타래를 정리하고 보충함. (2018/11/11)
이라면
은 같은 cyclic class에 놓여야 해서
의 값은 변하지 않는다. 만약
는 변하지 않고
는 최대 1까지 증가한다. 그렇지 않다면
시점에서 cyclic class가 완성되지 않았으므로
이라면 좌변은 3 이상 증가하고 우변은
라면
이어야 한다. 이 때,
이라면,
은 이전에 이미 한 번 지났다는 이야기가 된다.
이전의 순열은
udaqueness 
“스즈미야 하루히의 증명”의 1개의 생각