Structural Conjectures for 4 x n Chomp: Unique Extension, Asymptotic Ratios, and Period-112 Geometry

아라브 가르그의 논문 "Structural Conjectures for 4 × n Chomp: Unique Extension, Asymptotic Ratios, and Period-112 Geometry"(4 × n Chomp 을 위한 구조적 추측: 고유 확장, 점근적 비율, 그리고 주기 112 기하학) 에 대한 상세한 기술적 요약은 다음과 같습니다.

1. 문제 제기

본 논문은 $4 \times n$ 직사각형 격자에서 진행되는 조합 게임 Chomp를 조사합니다.

• 게임 규칙: 플레이어는 번갈아 가며 하나의 정사각형과 그 위쪽 및 오른쪽에 있는 모든 정사각형을 제거합니다. 왼쪽 위 모서리의 정사각형 $(1,1)$ 은 "유독"하며, 이를 강제로 취하게 되는 플레이어가 패배합니다.
• 목표: P-위치(이전 플레이어가 승리하는 위치, 즉 현재 차례인 플레이어에게 패배하는 위치) 를 식별합니다.
• 맥락: $1 \times n$ 및 $2 \times n$ 사례는 완전히 해결되었고, $3 \times n$은 부분적인 알고리즘적 해법이 존재하지만, $4 \times n$ 사례는 체계적인 계산 분석이 부족했습니다. 본 논문은 P-위치를 표로 정리하고 근본적인 구조적 패턴을 식별함으로써 이 격차를 메우려는 것입니다.

2. 방법론

저자는 보드 너비가 $n = 500$까지인 경우의 P-위치를 계산하기 위해 C++ 로 최적화된 후방 탐색 솔버를 개발했습니다.

• 상태 표현:
  • 위치는 각 행의 정사각형 수를 나타내는 비증가 튜플 $(a, b, c, d)$로 표현되며, 여기서 $a \ge b \ge c \ge d \ge 0$입니다.
  • 비트 패킹: 각 튜플은 메모리 사용을 최소화하고 해싱 속도를 극대화하기 위해 네 개의 16 비트 필드를 사용하여 단일 uint64 정수로 인코딩됩니다.
• 알고리즘 설계:
  • 희소 저장: P-위치만 해시 세트에 저장됩니다. 솔버는 알려진 P-위치로 이동하는 수를 발견하자마자 N-위치(현재 플레이어에게 승리하는 위치) 를 즉시 단축 처리합니다.
  • 하향식 평가: 상태는 총 셀 수의 증가 순서로 처리되어, 상태를 평가하기 전에 모든 후속 상태가 해결되도록 보장합니다.
• 성능:
  • $n \le 500$에 대해 4,316,097 개의 P-위치를 계산했습니다.
  • 실행 시간: Apple M4 프로세서에서 약 70 분.
  • 메모리 사용량: 피크 사용량 45 MB.
• 검증:
  • 알려진 $2 \times n$ 공식 ($c=d=0$일 때 $b=a-1$임) 에 대해 검증되었습니다.
  • $n=50$까지의 $3 \times n$ 부분 사례 ($d=0$) 에 대해 독립적인 Python 솔버와 교차 검증되었습니다.
  • 데이터 출력 시 초기 열 정렬 버그가 수정되었습니다.

3. 주요 기여 및 결과

계산된 데이터셋의 분석은 네 가지 주요 구조적 추측으로 이어졌습니다.

A. 추측 1: 고유 확장 속성

• 진술: 유효한 행 길이 삼중체 $(a, b, c)$에 대해, $(a, b, c, d)$가 P-위치가 되는 정수 $d$는 최대 하나만 존재합니다.
• 함의: 투영 사상 $\pi: (a, b, c, d) \to (a, b, c)$는 P-위치 집합에서 단사적입니다.
• 의의: 이는 $4 \times n$ 게임이 $3 \times n$ 게임의 "결정론적 리프트"임을 시사합니다. 모든 $(a, b, c)$가 P-위치로 확장되는 것은 아니지만 (약 20% 만 확장됨), 확장이 존재한다면 네 번째 행 길이 $d$는 고유하게 강제됩니다. 이는 이전에 그러한 단순한 단사 매핑이 확립되지 않았던 $3 \times n$ 사례와 대조됩니다.

B. 추측 2: 점근적 비율

• 진술: 보드 너비 $a \to \infty$로 갈 때, P-위치 내 행 길이의 비율은 고정된 상수로 수렴합니다:
  • $b/a \to L_1 \approx 0.762$
  • $c/a \to L_2 \approx 0.499$
  • $d/a \to L_3 \approx 0.224$
• 방법론: 윈도우 중앙값, 이동 윈도우, 그리고 멱법칙 곡선 피팅을 통해 추정되었습니다.
• 관찰: 이러한 상수에 대한 정확한 대수적 항등식은 발견되지 않았습니다. 그러나 $L_3 \approx 0.224$는 $\cos(3\pi/7) \approx 0.2225$와 놀라울 정도로 가깝습니다. 이는 잠재적인 숨겨진 대수적 관계를 시사합니다.

C. 추측 3: 주기 112 모듈러 구조

• 진술: P-위치로 확장되는 삼중체 $(a, b, c)$의 집합은 기본 주기가 112인 모듈러 구조를 보입니다.
• 증거:
  • $d$값의 시퀀스에 대한 자기상관 분석은 지연 112 에서 날카로운 피크를 보여줍니다.
  • $c$와 $(a-b) \pmod{112}$만을 사용하는 로지스틱 분류기는 확장 가능성을 79% 정확도로 예측합니다.
  • 카이제곱 검정은 다른 모듈로와 비교하여 모듈로 112 가 가장 강력한 통계적 분리를 제공함을 확인합니다 ($\chi^2 = 12,433$).
• 해석: $112 = \text{lcm}(7, 8) \times 2$입니다. 7 의 인자는 $3 \times n$ 서브 게임의 주기성에서 비롯된 것으로 보이며, 8 의 인자는 비트 패킹 아티팩트를 배제하고도 여전히 설명되지 않고 있습니다.

D. 추측 4: 선형 원뿔 기하학

• 진술: 확장되는 삼중체 $(a, b, c)$의 집합은 $\mathbb{R}^3$에서 선형 원뿔을 형성합니다.
• 기하학: 고정된 $c$에 대해, 유효한 $(a, b)$ 범위는 연속적인 밴드를 형성합니다. 이 밴드의 너비는 $c$에 따라 선형적으로 증가합니다:
  $$\text{width}(c) \approx \frac{11}{8} \cdot c + f(c \pmod{112})$$
  여기서 $f$는 유계 주기 함수입니다. 기울기 $11/8 = 1.375$는 슬라이스 기반 측정을 통해 도출되었습니다.

4. 의의 및 향후 방향

• 구조적 통찰: 이 발견들은 $4 \times n$ Chomp 가 이전에 의심되었던 것보다 더 풍부하고 결정론적인 구조를 지니며, "고유 확장" 속성으로 인해 $3 \times n$ 사례보다 잠재적으로 더 단순할 수 있음을 시사합니다.
• 일반화: 저자는 고유 확장 속성이 모든 $k$에 대해 $k \times n$ Chomp 로 일반화될 것이라고 가설을 세웠으며, 이는 모든 Chomp 게임이 해결된 $2 \times n$ 사례에 의해 재귀적으로 결정됨을 의미합니다.
• 미해결 질문:
  1. 증명: 고유 확장 속성을 조합론적으로 증명할 수 있는가?
  2. 대수적 한계: 점근적 비율들은 공통 다항식의 근인가?
  3. 고차원: 이것이 $5 \times n$에도 적용되는가? ($O(n^5)$ 상태 공간이 필요함).
  4. 주기 기원: 112 주기 내 주기 8 구성 요소의 출처는 무엇인가?
  5. 폐쇄형: 확장 가능한 삼중체의 약 20% 를 폐쇄형 마스크로 설명할 수 있는가?

논문은 또한 $d$값의 시퀀스를 정수 열 온라인 백과사전 (On-Line Encyclopedia of Integer Sequences) 에 A395126으로 제출했다고 명시하고 있습니다. 코드와 데이터는 저자의 GitHub 저장소를 통해 공개적으로 이용 가능합니다.