Claude의 사이클

Claude’s Cycles

Don Knuth, Stanford Computer Science Department (28 February 2026; revised 02 March 2026)

충격! 충격! 어제 나는, 몇 주 동안 작업해 오던 미해결 문제가 Claude Opus 4.6 — 3주 전에 출시된 Anthropic의 하이브리드 추론 모델 — 에 의해 막 해결되었다는 사실을 알게 되었다! “생성형 AI”에 대한 내 의견을 언젠가 수정해야 할 것 같다. 내 추측이 멋진 해법을 갖고 있음이 밝혀졌을 뿐 아니라, 자동 추론과 창의적 문제 해결의 이 극적인 진보를 함께 축하할 수 있다니 얼마나 기쁜 일인가. 이 노트에서 그 이야기를 간단히 전해 보려 한다.

다음은 내가 『The Art of Computer Programming』의 미래 권에서 유향 해밀턴 사이클을 다루는 글을 쓰는 동안 등장한 문제다: 0 ≤ i, j, k < m 인 $m^3$개의 꼭짓점 ijk를 갖는 유향 그래프를 생각하라. 각 꼭짓점에서 나가는 호는 세 개이며, 즉 i+jk , ij +k, ijk + 로 향한다. 여기서 i+ = ( i+1) mod m 이다. m > 2인 모든 m에 대해, 이 호들을 세 개의 유향 $m^3$-사이클로 일반적으로 분해하는 방법을 찾아보라.

나는 m = 3에 대해서는 이 문제를 풀었고, [3]의 한 연습문제 해설의 일부로 일반화를 요청했다. 내 친구 Filip Stappers가 도전에 나섰고, 4 ≤ m ≤ 16에 대해 실험적으로 해를 발견했다. 따라서 m ≤ 2인 경우를 제외하면 원하는 분해가 존재할 가능성이 매우 커졌다. 실제로 이 질문을, 위와 똑같은 문구로 Claude에게 던질 배짱을 낸 사람은 Filip이었다. 그는 또 진행 상황을 요약하라고 안내/코칭도 했는데, Claude에게 다음과 같이 지시했다:

** After EVERY exploreXX.py run, IMMEDIATELY update this file [ plan.md ]before doing anything else. ** No exceptions. Do not start the next exploration until the previous one is documented here.

그리고 Claude의 공격 계획은 상당히 훌륭했다. 먼저 문제를 다음처럼 재정식화했다: “Need sigma: $Z3 \n\n> m\n\n→ S3$,assigning a permutation of {0, 1, 2} at each vertex; cycle c at vertex v goes in direction sigma( v)[ c]. Each resulting functional digraph must be a single Hamiltonian cycle.” 그런 다음 단순한 답을 시도했다: “‘If sigma is cyclic, i.e. fc(v) = ( c+g(v)) mod 3 for some g : $Z3 \n\n> m\n\n→ Z3$, then we only need one function g. Tested linear g = ( a·i+b·j +c·k) mod 3 and quadratic variants. No linear or simple quadratic g works. ”

Claude의 두 번째 탐색은 DFS 탐색 시도(깊이 우선 탐색)라고 불렀다: “Attempted brute-force DFS over sigma assignments for m = 3 (6 27 search space). Too slow without good pruning.” 세 번째로는 2D 뱀형(serpentine) 분석을 시도했다: “ Key 2D result: The pattern [0 m−11] m\n\ngives a Hamiltonian cycle in Cay( $Z2 \n\n> m,$\n\n{e0, e 1}) for m = 3. Its complement also works, giving a valid 2D decomposi-tion.”

이는 정말 인상적이다! 먼저 Claude는 이 유향 그래프가 두 생성자(전통적으로 e0와 e1이라 부르는)를 갖는 이른바 Cayley 유향 그래프임을 알아보았다. 수학자라면, 호들이 $m^2$개의 꼭짓점 위에서 군으로 작용하며 e0가 첫 번째 성분을 증가시키고 e1이 두 번째 성분을 증가시킨다는 것을 이해할 것이다. 그런 다음 일반 m에 대해 사이클을 기호적으로 정식화했는데, 이상하게도 여전히 m = 3만 보고 있다고 말하고 있었다. 그리고 이를 “뱀형 패턴”이라 부르기로 했다!

탐색 4는 “3D 뱀형 패턴” [0 m−11] m−1[0 m−12] m\n\n을 구성했다. (이는 [[0 m−11] m−10m−12] m\n\n의 조판 오류다. 이는 [2]의 299쪽에 있는 고전적 수열 “modular m-ary Gray code”다.)

Claude는 이 사이클을 그래프에서 삭제한 뒤, 남은 2-정칙 유향 그래프를 살펴보고 “분해를 어렵게 만드는 경직된 구조”가 있다고 판단했다. 그럼에도 탐색 5에서 이 잔여 유향 그래프를 분석해 몇몇 사이클을 찾았다. 불행히도 그것들은 맞아떨어지지 않았다. 다시 원점으로.

여러 다른 접근도 시도되었다. 예컨대 i+j +k가 −1과 합동인 초평면 위에 놓인 꼭짓점들에서의 선택을 살펴보는 식이다. 탐색 15에서 Claude가 섬유 분해(fiber decomposition)라고 부른 것을 도입하기 전까지는, 유망한 것이 전혀 나타나지 않았다: “The quotient map ?( i, j, k ) = i+j +k mod m maps all arcs from fiber Fs to Fs+1 . The digraph is layered . In fiber coordinates ( i, j ) with k = ( s−i−j) mod m.”

그 섬유 좌표를 사용하면, 문제는 이제 각 ( i, j, s )에 대해 ( i, j )를 (1 , 0) 또는 (0 , 1) 또는 (0 , 0)만큼 이동시키는 세 연산자의 순열을 선택하는 문제로 재정식화될 수 있었다. “Tried sigma depending 1only on fiber index s (rotation by s): gives the ( i+j +k) mod 3 pattern which doesn’t work. Random local search found solutions for m = 3 but no general pattern emerged.”

탐색 18은 “implemented the full fiber framework as executable code. Exhaustive backtracking for $$\n\n> m\n\n= 3 found a valid decomposition in 0.1s (10932 nodes).” 이 해에서 순열 sigma는 섬유 s = 0에서 모든 ( i, j )에 대해 동일했다. 탐색 20의 일부로, 시뮬레이티드 어닐링을 통해 m = 4에 대해서도 비슷한 “균일한” 섬유가 발견되었다.

탐색 21에서 Claude는 2D 뱀형 함수 “ Q(i, j ) = ( i+1 , j ) if i+j  = m−1mod m, else ( i, j +1)”가 좋은 성질을 갖는다는 것을 깨달았다. 섬유 0에서 균일한 선택을 하고 다른 모든 섬유에서 뱀형의 변형을 쓰면 유망해 보였는데, 이는 m이 홀수일 때 그리고 그때에만 그랬다. 그래서 “대규모” 시뮬레이티드 어닐링 실험이 잔뜩 이어졌지만, 모두 헛수고였다. 탐색 25 이후 결론은 “SA can find solutions but cannot give a general construction. Need pure math.”였다.

그래서 Claude는 새 사고 모자를 썼다. 어느 순간 스스로에게 “아마 올바른 틀은 이거다: 섬유로 생각하지 말고, 해밀턴 사이클을 해밀턴 사이클로 만드는 조건을 직접 생각하라.”고 말하기도 했다. 탐색 27에서 아슬아슬한 근접 실패가 있었다. “Take the 3D serpentine for cycle 0, apply cyclic coordinate rotation to get cycles 1 and 2: d1(i, j, k ) = ( d0(j, k, i ) + 1) mod 3; d2(i, j, k ) = ( d0(k, i, j ) + 2) mod 3; all three are individually Hamiltonian for every m = 3 . . 9 tested! Only 3( m−1) out of $m^3$ vertices have conflicts. all lie on the hyperplane i+j +k = m−1 mod m.” 불행히도 그 충돌들은 해결할 수 없었다.

탐색 29는 그럴듯한 많은 시나리오들이 사실은 불가능함을 증명했다. “This kills the ‘single-hyperplane + rotation’ approach entirely. . . . We must allow the direction function to use different values across a rotation orbit.” 하지만, 아하. 탐색 30은 탐색 20에서 SA가 찾아낸 해로 되돌아가, 각 섬유에서의 선택이 단 하나의 좌표에만 의존한다는 사실을 알아차렸다: s = 0에서는 j에만, s = 1과 s = 2에서는 i에만 의존한다.

이로부터 구체적 구성(탐색 31)이 나왔고, 파이썬 프로그램 형태로 m = 3, 5, 7, 9, 11에 대해 올바른 결과를 냈다 — 만세! “All three cycles are Hamiltonian, all arcs are used, perfect decomposition!” 다음은 그 파이썬 프로그램을 단순화하여 C 형태로 옮긴 것이다:

int c, i, j, k, m, s, t ; char ∗d; for (c = 0; c < 3; c++ ) { for (t = i = j = k = 0; ; t++ ) { printf ("%x%x%x " , i, j, k ); if (t == m∗m∗m) break ; s = ( i+j +k) % m; if (s == 0) d = ( j == m−1? "012" : "210" ; else if (s == m−1) d = ( i > 0? "120" : "210" ; else d = ( i == m−1? "201" : "102" ); switch (d[c]) { case ’0’ : i = ( i+1) % m; break ; case ’1’ : j = ( j +1) % m; break ; case ’2’ : k = ( k+1) % m; break ; }} printf ("\n" ); }

Filip Stappers는 Claude의 파이썬 프로그램을 3부터 101까지의 모든 홀수 m에 대해 테스트했고, 매번 완벽한 분해를 찾았다. 그래서 그는 (지극히 합리적으로) 이 문제가 홀수 m에 대해서는 해결되었다고 결론내렸다. 그리고 그 충격적인 소식을 즉시 내게 보내왔다.

물론 엄밀한 증명은 여전히 필요했다. 그런데 그 증명을 구성하는 일은 꽤 흥미롭다는 것이 드러났다. 예를 들어, 출력되는 첫 번째 사이클을 보자. 우리는 그것의 길이가 $m^3$임을 증명해야 한다. 그 사이클의 규칙은 자명하지 않지만 꽤 단순하다:

s = ( i+j +k) mod m이라 하자.

s = 0일 때, j = m−1이면 i를 bump하고, 그렇지 않으면 k를 bump한다.

0 < s < m −1일 때, i = m−1이면 k를 bump하고, 그렇지 않으면 j를 bump한다.

s = m−1일 때, i > 0이면 j를 bump하고, 그렇지 않으면 k를 bump한다.

(“Bump”는 “1 증가, mod m”을 뜻한다.)

따라서 특수한 경우 m = 3에서 그 사이클은

022 −−→ 002 −−→ 000 −−→ 001 −−→ 011 −−→ 012 −−→ 010 −−→ 020 −−→ 021 −−→

121 −−→ 101 −−→ 111 −−→ 112 −−→ 122 −−→ 102 −−→ 100 −−→ 110 −−→ 120 −−→

220 −−→ 221 −−→ 201 −−→ 202 −−→ 200 −−→ 210 −−→ 211 −−→ 212 −−→ 222 −−→ 022.

그리고 특수한 경우 m = 5에서는

042 −−→002 −−→012 −−→022 −−→023 −−→024 −−→034 −−→044 −−→004 −−→000 −−→001 −−→011 −−→021 −−→

031 −−→032 −−→033 −−→043 −−→003 −−→013 −−→014 −−→010 −−→020 −−→030 −−→040 −−→041 −−→

141 −−→101 −−→111 −−→121 −−→131 −−→132 −−→142 −−→102 −−→112 −−→122 −−→123 −−→133 −−→143 −−→

103 −−→113 −−→114 −−→124 −−→134 −−→144 −−→104 −−→100 −−→110 −−→120 −−→130 −−→140 −−→

240 −−→200 −−→210 −−→220 −−→230 −−→231 −−→241 −−→201 −−→211 −−→221 −−→222 −−→232 −−→242 −−→

202 −−→212 −−→213 −−→223 −−→233 −−→243 −−→203 −−→204 −−→214 −−→224 −−→234 −−→244 −−→

344 −−→304 −−→314 −−→324 −−→334 −−→330 −−→340 −−→300 −−→310 −−→320 −−→321 −−→331 −−→341 −−→

301 −−→311 −−→312 −−→322 −−→332 −−→342 −−→302 −−→303 −−→313 −−→323 −−→333 −−→343 −−→

443 −−→444 −−→440 −−→441 −−→401 −−→402 −−→403 −−→404 −−→400 −−→410 −−→411 −−→412 −−→413 −−→

414 −−→424 −−→420 −−→421 −−→422 −−→423 −−→433 −−→434 −−→430 −−→431 −−→432 −−→442 −−→042.

같은 s 값을 갖는 삼중항들은 정확히 m 단계 간격으로 떨어져 있다. 모든 $m^3$개의 삼중항이 등장함을 증명하려면, 주어진 s 값에 대한 $m^2$개의 삼중항이 모두 나타난다는 것을 증명하면 된다.

첫 번째 좌표 i는 오직 s = 0이고 j = m−1일 때만 변한다는 점에 주목하자. 따라서 첫 좌표 i가 같은 $m^2$개의 삼중항은 모두 연속해서 나타난다. (우리의 예시 사이클들은 이를, 꼭짓점 000에서 시작하는 대신 i가 막 0으로 바뀐 꼭짓점에서 시작하는 방식으로 드러낸다.)

i = 0인 사이클 원소들은 일반적으로 꼭짓점 0( m−1)2에서 시작해야 한다는 점에 주목하자. 왜냐하면 그 직전 꼭짓점은 i = j = m−1이고 s = 0이었어야 하기 때문이다. 그리고 s = 1인 0( m−1)2의 뒤에는 일반적으로 002, 012, . . . , 0( m−3)2, 0( m−3)3가 이어져, 다시 s = 0으로 돌아오게 된다.

일반적으로 0( m−k)k는 1 < k < m일 때 즉시 0( m−k)( k+1)이 뒤따른다. 그 다음에는 j가 증가하여 0( m−k−2)( k+1)에 도달하고, 그 후속은 0( m−k−2)( k+2)이다. 따라서 s = 0인 꼭짓점을 만날 때마다 k가 (mod m으로) 2씩 증가한다. m이 홀수이므로, 우리는 결국 0( m−1)1에 도달하게 되는데 — 그때까지 우리는 0 jk 꼴의 모든 $m^2$개의 꼭짓점을 본 것이 된다. 그리고 0( m−1)1의 후속은 1( m−1)1이다. 지금까지는 좋다!

일반적으로 첫 성분 i가 0 < i < m −1을 만족하는 사이클 원소들은 i(m−1)(2 −i)에서 시작한다. 여기서 2 −i는 물론 mod m으로 평가된다. 모든 것이 잘 진행된다면, 그 원소들은 i로 시작하는 $m^2$개의 꼭짓점을 모두 포함해야 하고, i(m−i)(1 −i)로 끝나야 한다. 그 후속은 ( i+1)( m−1)(1 −i)이다.

그리고 실제로 모든 것이 잘 진행된다. 우리는 s = 0일 때를 제외하면 두 번째 성분을 계속 증가시키므로, s = 0일 때 보게 되는 꼭짓점들은 i(m−2)(2 −i), i(m−3)(3 −i), . . . , i0( m−i), i(m−1)(1 −i)이다.

마지막으로 우리는 ( m−1)( m−1)3에 도달하는데, 이는 i = m−1인 첫 꼭짓점이다. 이제 지역 규칙이 다시 바뀐다: 이제부터는 s = m−1일 때를 제외하면 세 번째 성분을 계속 증가시키게 된다. s = 0일 때 보게 되는 꼭짓점들은 ( m−1)01, ( m−1)10, . . . , ( m−1)( m−1)2이다. QED.

이로써 첫 번째 사이클(C 프로그램에서 c = 0인 사이클)이 해밀턴임을 증명했다. 다른 두 사이클에 대해서도 비슷한 증명을 할 수 있다. (부록을 보라.)

재미로, 이런 증명이 가능한 더 큰 종류의 사이클들을 생각해 보자. 실제로는 홀수 m에 대해, 위에서 말한 분해 문제를 푸는 방법이 수백 가지나 된다. Claude Opus 4.6은 그중 하나를, 어디를 찾아야 하는지 추론해 냄으로써 우연히 발견했을 뿐이다.

m = 3에 대한 해밀턴 사이클 C가 다음 구성에 의해 모든 홀수 m ≥ 3에 대해 해밀턴 사이클을 산출한다면, 우리는 그 C를 일반화 가능(generalizable)하다고 말하자: “0 ≤ I, J, K < m인 임의의 꼭짓점 IJK가 주어졌을 때, i = I

, j

= J

, s = S

, 그리고 k = ( s−i−j) mod 3이라 하자. 여기서 S = ( I +J +K) mod m, 0 

= 0, ( m−1) 

= 2, 그리고 0 < x < m −1이면 x

= 1이다. 꼭짓점 IJK의 후속은, 사이클 C가 ijk의 후속을 만들 때 bump하는 좌표를 bump함으로써 얻는다.”

예를 들어 m = 5이고 IJK = 301이라면 i = 1, j = 0, S = 4, s = 2, k = 1이다. 따라서 301의 후속은, C가 101 −−→ 201 또는 101 −−→111 또는 101 −−→102 중 어느 호를 포함하느냐에 따라 401 또는 311 또는 302가 된다.

위의 예에서 m = 3에 대한 Claude의 사이클은 일반화 가능이다. 실제로 우리는 $\n\n> m\n\n= 5$에 대한 그 일반화를 이미 보았다. 하지만 일반화 가능하지 않은 사이클을 찾는 것은 쉽다. 예컨대 C가

000 −−→001 −−→002 −−→012 −−→010 −−→011 −−→021 −−→022 −−→020 −−→120 −−→100 −−→101 −−→111 −−→121 −−→

122 −−→102 −−→112 −−→110 −−→210 −−→211 −−→212 −−→222 −−→220 −−→221 −−→201 −−→202 −−→200 −−→000

인 사이클(이는 m = 3인 경우의 모든 해밀턴 사이클 가운데 사전식으로 가장 작은 것)이라면, m = 5에 대한 다음 “일반화”를 얻는다:

000 −−→001 −−→002 −−→003 −−→004 −−→014 −−→010 −−→011 −−→012 −−→013 −−→023 −−→024 −−→020 −−→

021 −−→022 −−→032 −−→033 −−→034 −−→030 −−→031 −−→041 −−→042 −−→043 −−→044 −−→040 −−→140 −−→

100 −−→101 −−→102 −−→103 −−→113 −−→123 −−→124 −−→120 −−→121 −−→221 −−→231 −−→232 −−→233 −−→

234 −−→334 −−→344 −−→340 −−→341 −−→342 −−→302 −−→312 −−→313 −−→314 −−→310 −−→410 −−→411 −−→

412 −−→413 −−→414 −−→424 −−→420 −−→421 −−→422 −−→423 −−→433 −−→434 −−→430 −−→431 −−→432 −−→

442 −−→443 −−→444 −−→440 −−→441 −−→401 −−→402 −−→403 −−→404 −−→400 −−→000 .

이런 — 이 사이클의 길이는 125가 아니라 75다.

m = 3에 대해 해밀턴 사이클은 정확히 11502개가 있으며, 그중 정확히 1012개가 m = 5에 대해 해밀턴 사이클로 일반화된다. 더 나아가 그중 정확히 996개는 m = 5와 m = 7 둘 다에 대해 해밀턴 사이클로 일반화된다. 그리고 그 996개는 실제로 모든 홀수 m > 1에 대해 일반화 가능하다.

이제 요점은 다음과 같다. 위의 C 프로그램 같은 방식으로 생성될 수 있는 분해를 “Claude-유사(Claude-like)”하다고 부르자. 여기서 {0, 1, 2}의 순열 d는 i, j, s가 0인지 m−1인지 혹은 그 외인지에만 의존한다. 0과 m−1 외의 특수 경우가 d의 선택에 영향을 주어서는 안 된다.

Theorem. A Claude-like decomposition is valid for all odd m >

1 if and only if each of the three sequences that it defines for m = 3 is generalizable.

Proof.

그 세 수열이 해밀턴이 아니거나, 혹은 모든 홀수 m > 1에 대해 해밀턴 사이클로 일반화되지 않는다면, 그것들이 올바른 분해를 정의하지 못하는 것은 분명하다. 반대로, 그것들이 모든 홀수 m > 1에 대해 해밀턴 사이클로 일반화되는 해밀턴 사이클들이라면, 그것들은 확실히 올바르다: 각 꼭짓점 ijk는 세 사이클 각각에 나타나고, d가 순열이므로 각 꼭짓점에서 나가는 세 호는 제대로 분할된다.

m = 3에 대한 11502개의 해밀턴 사이클을 사용하여 정확 덮개(exact cover) 문제를 세우면, 3 ×3×3 분해 문제의 해가 정확히 4554개임을 도출할 수 있다. 그리고 유사하게, 996개의 일반화 가능한 사이클들 가운데 단 세 개로 모든 호를 덮는 모든 방법을 조사하면, 그 4554개 해 중 정확히 760개가 일반화 가능한 사이클만을 포함함을 알 수 있다 — 대략 6개 중 1개 꼴이다. 따라서 정리에 의해, 홀수 m > 1에 대해 유효한 Claude-유사 분해는 정확히 760개임을 알 수 있다.

Claude가 찾은 분해는 그 760개 가운데 “가장 좋은” 것이 아니었을지도 모른다. 더 나은 것을 만들 수 있을까? 나는 그중 몇 개를 살펴보았고, 그것들이 서로 다소 다른 동작을 보인다는 것을 알게 되었다. 그러나 실제로 더 “좋은” 것을 만나지는 못했다. i, j, s에 대한 의존성 때문에 이 분해들은 순환 대칭성을 갖지 않는다.

나는 또 놀랍게도, 760개의 일반화 가능한 3 ×3×3 사이클들 중 136개가 $\n\n> ijk\n\n$를 jki로 보내는 사상 아래에서도 일반화 가능함을 알아차렸다. 그러나 {ijk, jki, kij }의 세 사상 모두에 공통인 것은 하나도 없었다.

Filip은 위에서 보고된 탐색들이, 결국 성공하긴 했지만 실제로는 매끄럽지 않았다고 내게 말했다. Claude가 무작위 오류에서 멈추면 재시작을 몇 번 해야 했고, 그러면 이전 탐색 결과 일부가 사라졌다. 테스트 프로그램을 두세 개 돌릴 때마다, 진행 상황을 꼼꼼히 문서화하라는 요구를 Filip이 계속해서 반복해서 상기시켜야 했다. 탐색 31에서 홀수 m에 대한 달콤한 성공은, 세션 시작 후 약 한 시간이 지나서야 찾아왔다.

이 분해 문제는 짝수 m에 대해서는 여전히 미해결이다. m = 2인 경우는 오래전에 불가능함이 증명되었다 [1]. 탐색 24의 일부로 Claude는 m = 4, m = 6, m = 8에 대한 해를 찾았다고 했지만, 그것들을 일반화할 방법은 보지 못했다고 했다. Filip은 또, 홀수 경우가 해결된 뒤 Claude에게 짝수 경우를 계속 탐색해 달라고 요청했다고도 말했다. “그런데 한동안 지나서는 막힌 것처럼 보였다. 끝에는 explore 프로그램을 제대로 쓰고 실행하는 것조차 더 이상 못 하게 되었는데, 매우 이상했다. 그래서 탐색을 중단했다.”

그럼에도 전체적으로 이는 분명 인상적인 성공담이다. Claude Shannon의 정신도 아마, 자신의 이름이 이런 진보와 함께 언급되는 것을 자랑스러워할 것이다. Claude에게 경의를!

Appendix.

Claude의 두 번째 사이클( c = 1)은 다음 규칙을 따른다: “If s = 0, bump j. If 0 < s < m +1, bump i. If s = m−1 and i > 0, bump k. If s = m−1 and i = 0, bump j.”

우리는 s = 0인 꼭짓점들이 다음 순서로 보인다는 것을 보일 수 있다. k = 0, 1, . . . , m−1에 대해:

0k(−k), ( −2)(1+ k)(1 −k), ( −4)(2+ k)(2 −k), . . . 2( −1+ k)( −1−k).

그리고 이것은 s = 1, 2, . . . , m−1인 꼭짓점들이 보이는 순서를 확립해 준다.

Claude의 세 번째 사이클( c = 2)은 다소 더 복잡한 규칙을 따른다: “If s = 0 and j < m −1, bump i. If s = 0 and j = m−1, bump k. If 0 < s < m −1 and i < m −1, bump k. If 0 < s < m −1 and

i

= m−1, bump j. If s = m−1, bump i.”

s = 0이고 j < m −1인 꼭짓점들은 다음 순서로 보인다:

0 j(−j), 2 j(−2−j), 4 j(−4−j), . . . ,(−2) j(2 −j).

그리고 마지막 꼭짓점의 후속은 ( −1) j(2 −j), ( −1)( j +1)(2 −j), ( −1)( j +2)(2 −j),

. . .

, ( −1)( j −2)(2 −j), 0( j −2)(2 −j)이다.

하지만 s = 0이고 j = m−1인 꼭짓점들은 다음과 같이 보인다:

0( −1)1, 1( −1)0, 2( −1)( −1), . . . , ( −1)( −1)2.

그리고 마지막 꼭짓점의 후속은 ( −1)( −1)3, ( −1)03, ( −1)13, . . . (−1)( −3)3, 0( −3)3이다.

따라서 모든 경우에, 주어진 j에 대한 s = 0의 m개 꼭짓점 수열은, mod m으로 j −2에 해당하는 j에 대한 수열 뒤에 이어진다.

References.

[1] Jacques Aubert and Bernadette Schneider, “Graphes orientes ind´ ecomposables en circuits hamiltoniens.”

Journal of Combinatorial Theory B32

(1982), 347–349.

[2] Donald E. Knuth, The Art of Computer Programming , Volume 4A: Combinatorial Algorithms, Part 1

(Upper Saddle River, N. J.: Addison–Wesley, 2011), xvi+883 pp.

[3] Donald E. Knuth, preliminary drafts entitled “Hamiltonian paths and cycles,” currently posted at

https://cs.stanford.edu/~knuth/fasc8a.ps.gz

and updated frequently as more material is being ac-cumulated.

5