The Ordered Zeckendorf Game

논문 요약: 정렬된 제켄도르 게임 (The Ordered Zeckendorf Game)

1. 문제 제기 및 배경 (Problem & Background)

• 제켄도르 정리 (Zeckendorf's Theorem): 모든 양의 정수는 연속되지 않는 피보나치 수 ($F_1=1, F_2=2, F_{i+1}=F_i+F_{i-1}$) 의 합으로 유일하게 표현될 수 있습니다.
• 기존 연구 (Classical Zeckendorf Game): 기존 연구에서는 피보나치 수의 순서와 무관한 (unordered) 다중집합 (multiset) 을 대상으로 두 플레이어가 번갈아 합치기 (Merge) 나 나누기 (Split) 연산을 수행하는 게임을 연구했습니다.
  • 한계: 기존 게임에서는 $n > 2$인 모든 경우에 2 번 플레이어가必胜 전략 (dominant strategy) 을 가지고 있어 게임의 전략적 깊이가 제한적이었습니다.
• 새로운 변형 (Ordered Variant): 본 논문은 이 게임에 순서 (Order) 와 인접성 (Adjacency) 의 제약을 도입한 새로운 변형인 **'정렬된 제켄도르 게임'**을 제안합니다.
  • 핵심 제약: 모든 연산 (합치기, 나누기) 은 인접한 항들 사이에서만 수행되어야 하며, 순서가 바뀔 경우 이를 재정렬하는 '스위칭 (Switching)' 연산이 추가됩니다.

2. 게임 규칙 및 정의 (Methodology & Definitions)

게임은 $n$개의 $F_1$ (1) 로 구성된 순서 있는 튜플 $(F_1, F_1, \dots, F_1)$로 시작합니다. 플레이어는 다음 5 가지 합법적인 이동 중 하나를 수행합니다.

1. 합치기 (Merging): 인접한 $(F_i, F_{i+1})$를 $F_{i+2}$로 대체.
2. 1 합치기 (Merging Ones): $(F_1, F_1)$을 $F_2$로 대체.
3. 나누기 (Splitting): $i > 2$일 때, $(F_i, F_i)$를 $(F_{i-2}, F_{i+1})$로 대체.
4. 2 나누기 (Splitting Twos): $(F_2, F_2)$를 $(F_1, F_3)$로 대체.
5. 스위칭 (Switching): 인접한 두 항 $(F_i, F_j)$를 $i > j$일 때 $(F_j, F_i)$로 교환 (순서 재정렬).

게임은 더 이상 이동이 불가능할 때, 즉 피보나치 수의 리스트가 엄격히 증가하는 순서로 정렬되어 있고 제켄도르 조건 (연속되지 않음) 을 만족할 때 종료됩니다.

3. 주요 이론적 결과 (Key Theoretical Results)

가. 종료 및 최종 상태 (Termination and Final State)

• 정리 1.3: 게임은 유한한 수의 이동 후 반드시 종료되며, 최종 상태는 $n$의 제켄도르 분해 (Zeckendorf decomposition) 가 됩니다.
• 증명 방법: 단조감소 함수 (Monovariant) $f(S) = \sum (k+1-j)F_{i_j}$를 정의했습니다. 모든 이동 (합치기, 나누기, 스위칭) 이 이 함수의 값을 엄격하게 감소시키므로, 게임은 순환할 수 없고 반드시 종료됩니다.

나. 게임 길이의 경계 (Bounds on Game Length)

• 최소 게임 길이 (Proposition 1.4):
  • 최단 게임의 길이는 $n - Z(n)$입니다. 여기서 $Z(n)$은 $n$의 제켄도르 분해에 포함된 항의 개수입니다.
  • 이는 그리디 알고리즘 (Greedy algorithm) 을 적용하여 가능한 한 빠르게 합치기를 수행할 때 달성됩니다.
• 최대 게임 길이의 점근적 행동 (Theorem 1.5, 1.10, 1.11, Corollary 1.12):
  • 상한: 최대 게임 길이 $M(n)$은 $M(n) \le \frac{n(n-1)}{2}$입니다.
  • 하한: "긴 게임 전략 (Long Game Strategy, LGS)"을 통해 하한을 유도했습니다. LGS 는 스위칭, 1 합치기, 나누기, 합치기의 우선순위를 가진 전략입니다.
  • 점근적 결과: $n \to \infty$일 때, 최대 게임 길이는 다음과 같이 점근적으로 행동합니다.
    $$M(n) = \frac{n^2}{2} - \Theta(n \log_\phi n)$$
    여기서 $\phi$는 황금비입니다. 이는 게임 길이가 $n^2$에 비례하여 증가함을 의미합니다.

다. 승자 전략 (Winning Strategy)

• 시뮬레이션 결과: $n \le 25$ 범위에서의 계산적 실험 결과, 1 번 플레이어가 거의 모든 경우 ($n=18$ 제외) 에서 승리하는 것으로 나타났습니다.
• 의미: 기존 게임 (2 번 플레이어의 승리) 과 대조적으로, 순서와 인접성 제약이 도입됨으로써 게임의 균형이 회복되고 전략적 복잡성이 증가했음을 보여줍니다.
• 미해결 문제: $n > 25$에 대한 일반적 승자 전략의 존재 여부는 아직 증명되지 않았습니다.

4. 확률적 분석 (Probabilistic Analysis)

• 무작위 게임 (Random Play): 모든 합법적인 이동을 동일한 확률로 선택할 때, 게임의 이동 횟수 분포는 로그 정규 분포 (Log-normal distribution) 에 수렴할 것으로 추측됩니다 (Conjecture 3.2).
• 승률: 무작위 게임에서 두 플레이어의 승률은 거의 동일하게 나타났습니다.

5. 의의 및 기여 (Significance & Contributions)

1. 게임 이론적 혁신: 제켄도르 정리를 기반으로 한 게임에 '순서'와 '스위칭' 개념을 도입하여, 기존 게임의 단순한 2 번 플레이어 우세를 깨고 더 풍부하고 예측 불가능한 전략적 환경을 조성했습니다.
2. 이론적 증명: 게임의 종료 보장, 최종 상태의 유일성, 그리고 게임 길이의 상하한에 대한 엄밀한 수학적 증명을 제시했습니다. 특히 최대 게임 길이가 $n^2/2$에 근사한다는 점과 로그 항의 보정 항을 도출했습니다.
3. 알고리즘적 도전: 게임 트리의 크기가 급격히 증가하여 $n$이 커질수록 최적 전략을 찾는 것이 계산적으로 매우 어렵다는 점을 지적하며, 향후 Minimax 알고리즘 및 휴리스틱 탐색의 필요성을 제기했습니다.
4. 확장 가능성: 이 게임은 일반화된 피보나치 수열 (k-bonacci 등), 다인 게임, 동적 시스템 및 확률론적 분석으로의 확장을 위한 새로운 연구 플랫폼을 제공합니다.

6. 결론

본 논문은 정렬된 제켄도르 게임을 통해 수론적 게임 (Number-theoretic games) 의 새로운 지평을 열었습니다. 순서 제약이 게임의 역학을 어떻게 근본적으로 변화시키는지 보여주었으며, 종료성, 게임 길이의 점근적 성질, 그리고 승자 전략에 대한 심층적인 분석을 제공했습니다. 이는 조합론, 게임 이론, 그리고 확률론의 교차점에서 향후 연구가 활발히 이루어질 수 있는 중요한 기초를 마련했습니다.