하루히 문제 (Haruhi Problem)

"Haruhi Problem"은 애니메이션 "스즈미야 하루히의 우울"의 방영 순서와 관련된 문제입니다. 이 애니메이션은 2006년에 처음 방영되었는데, 특이하게도 시간 순서대로 방영되지 않고 뒤섞인 순서로 방영되었습니다.

• 제작진의 의도적인 방영 순서 변경: 제작진은 시청자들에게 혼란과 궁금증을 유발하기 위해 의도적으로 에피소드 순서를 뒤섞었습니다.
• 시간 순서와 뒤섞인 순서의 차이: 예를 들어, 이야기의 시작 부분에 해당하는 에피소드가 나중에 방영되거나, 중요한 사건이 발생하는 에피소드가 중간에 끼어들어 이해하기 어려웠습니다.
• 시청자들의 혼란과 논쟁: 이 때문에 당시 많은 시청자들이 어떤 순서로 봐야 하는지 혼란스러워했고, 온라인 커뮤니티 등에서 방영 순서와 시간 순서에 대한 활발한 논쟁이 벌어졌습니다.
• 이러한 특이한 방영 방식 때문에 "Haruhi Problem"이라는 이름이 붙게 되었고, 애니메이션 팬들 사이에서는 꽤 유명한 이야기입니다.

예를 들어, 1화, 2화, 3화를 다양한 순서로 본다고 할 때, 아래와 같이 6번씩 3번, 즉 18번을 시청해야 모든 순서로 한번씩 볼 수 있습니다.

1 -> 2 -> 3

1 -> 3 -> 2

2 -> 1 -> 3

2 -> 3 -> 1

3 -> 2 -> 1

3 -> 1 -> 2

 

하지만, 이를 연결하여 보게 된다면 18번을 시청하지 않고 9번만 시청해도 비슷하게 볼 수 있습니다.

1 -> 2 -> 3 -> 1 -> 2 -> 1 -> 3 -> 2 -> 1 

 

즉 1~3의 모든 순열을담은 가장 짧은 숫자 = 초순열 문제입니다. 1화가 늘어날 수록 초순열은 n! 만큼 증가합니다.

애니가 n화인 경우, 초순열은 n! + (n-1)! + (n-2)! + ... + 1! 이 됩니다. 그렇지만 이보다 더 적은 값도 가능하며, 하한을 추측할 수 있는 공식이 등장합니다.

 

Traveling Sales Man - 모든 점을 통과하는 가장 빠른 길을 찾는 문제와 유사하게 생각할 수 있습니다

 

n! + (n-1)! + n-3 (for n ≥ 2)

 

• n!: n개의 기호로 만들 수 있는 순열의 총 개수입니다. 최단 초순열은 이 모든 순열을 포함해야 하므로, 이 항은 기본적인 길이에 대한 기여를 나타냅니다.
• (n−1)!: n개의 기호로 이루어진 순열은 (n−1)!개의 순환 클래스로 나눌 수 있습니다. 각 순환 클래스에는 순환 시프트로 서로 변환될 수 있는 n개의 순열이 포함됩니다. 이 항은 초순열이 모든 순환 클래스를 "완료"하는 데 필요한 길이를 나타냅니다.
• (n−2)!: 이 항은 순열 그래프에서 "2-루프"와 관련이 있습니다. 겹침이 n−2인 특정 순열 전환과 관련된 구조입니다.
• n−3: 여기서 n은 초순열의 첫 번째 순열의 길이이고 −3은 최단 초순열 길이의 하한을 유도하는 증명 과정에서 비롯된 상수입니다.

증명에서는 워크(순열 그래프에서의 경로)의 총 가중치(wt), 방문한 고유한 순열의 수(p), 완료된 순환 클래스의 수(c),  방문한 2-루프의 수(v)와 다음 부등식 관계를 갖는다는 것을 보여줍니다:

 

wt ≥ p+c+v−2

 

모든 순열을 포함하는 초순열의 경우, 다음과 같은 하한이 적용됩니다.

p≥n! (모든 n!개의 순열을 방문해야 함)

c≥(n−1)!−1 (총 (n−1)!개의 순환 클래스 중 시작 클래스를 제외한 나머지를 완료해야 함)

v≥(n−2)! (최소한 (n−2)!개의 2-루프를 방문해야 함)

 

이를 대입하면, 

 

wt ≥ n!+((n−1)!−1)+(n−2)!−2 = n!+(n−1)!+(n−2)!−3

 

초순열의 길이 = (첫 순열의 길이 n) + (총 가중치 wt)이므로, 길이의 하한은 양변에 n을 더해 다음과 같습니다.

 

길이 ≥ n+(n!+(n−1)!+(n−2)!−3) = n!+(n−1)!+(n−2)!+n−3

 

 

관련 논문:

https://oeis.org/A180632/a180632.pdf

 

참고영상:

https://www.youtube.com/watch?v=v9zrnS4yL28&t=222s