🔢 mathematics

The Nim-Sum of a Random Integer Partition

이 논문은 $N$ 의 정수 분할에서 패배 위치의 비율에 대한 1차 점근적 거동을 결정한다. 이 비율은 $1/(\sqrt{N}\log N)$ 의 척도로 0에 수렴하지만, 자연스러운 척도로 정규화한 후에는 수렴하지 않고 대신 이진 경계 근처에서 푸아송 기우성 전이를 보이는 이진 톱니형 패턴을 나타낸다.

원저자: Daewon Kim

게시일 2026-08-28✓ Author reviewed ⓘ

📖 5 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Daewon Kim

원본 논문은 CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

두 사람이 한 번에 하나의 더미에서 원하는 만큼의 돌을 가져가는 게임을 상상해 보십시오. 목표는 마지막으로 움직이는 사람이 되거나, 반대로 상대방이 이길 수 있는 움직임이 없는 상태로 몰아넣는 것입니다. 이것은 님(Nim) 게임으로, 백 년 넘게 연구되어 온 고전적인 전략 퍼즐입니다. 승리의 비결은 돌의 총 개수를 세는 것이 아니라, 이진법 방식으로 덧셈과 뺄셈을 혼합하는 규칙을 사용하여 더미들의 크기를 결합하는 특정한 방식에 있습니다. 만약 이 결합 결과가 0이 된다면, 차례가 된 플레이어는 상대방이 완벽하게 플레이한다고 가정할 때 패배할 운명입니다. 수십 년 동안 수학자들은 임의의 더미 배치에 대해 이러한 패배하는 위치를 식별하는 방법을 알고 있었습니다. 하지만 더 깊고도 미묘한 질문이 남아 있었습니다. 만약 단순히 정해진 수의 돌을 모아 무작위로 더미로 나눈다면, 그 무작위 배치가 패배하는 위치가 될 확률은 얼마나 될까요?

이 질문은 게임 이론과 정수 분할(숫자를 더 작은 정수들로 나누는 방법을 다루는 수학 분야)의 교차점에 놓여 있습니다. 단일 게임의 규칙은 정밀하고 결정론적이지만, 시작 위치가 무작위로 선택될 때 이러한 게임의 행동은 놀라울 정도로 복잡합니다. 돌의 총 개수가 커짐에 따라 이러한 패배하는 위치의 빈도가 단순한 점근적 패턴으로 안정될지는 자연스러운 질문입니다. 그러나 하와이 대학교 마노아 캠퍼스의 데이원 킴(Daewon Kim)의 새로운 연구는 그 답이 단순한 안정화보다 훨씬 더 복잡하다는 것을 밝혀냈습니다. 돌의 총 개수가 늘어남에 따라 패배하는 위치가 나타날 실제 확률은 0에 가깝게 줄어들지만, 그 확률을 자연스러운 기준값으로 다시 조정한 정규화된 밀도는 숫자가 아무리 커지더라도 결코 진정으로 안정되지 않는 들쭉날쭉하고 반복적인 패턴 속에서 진동합니다.

킴의 연구는 돌의 총합이 짝수인 특정 경우에 집중하는데, 이는 게임의 규칙상 홀수 총합으로는 패배하는 위치를 형성하는 것이 불가능하기 때문입니다. 이 연구는 무작위 샘플링 대신 정밀한 계산법을 사용하여, 돌의 총 개수가 증가함에 따라 패배하는 위치의 밀도가 어떻게 변화하는지를 정확히 결정합니다. 연구 결과, 이 정규화된 확률은 단일 상수 값에 접근하지 않습니다. 대신, 문제의 규모와 관련된 자연스러운 척도가 2의 거듭제곱을 통과할 때마다 반복되는 톱니 모양의 패턴을 그리며 격렬하게 요동칩니다. 만약 당신이 확률의 밀도를 그래프로 그린다면, 낮은 지점에서 높은 지점까지 꾸준히 올라갔다가 급격히 떨어져 다시 올라가기 시작하는 선을 보게 될 것입니다. 이 순환은 무한히 반복되며, 이는 정규화된 밀도가 특정 기준값의 1배에서 2배 사이 어디에나 있을 수 있음을 의미하며, 이는 전적으로 이 순환의 어느 단계에 있는지에 달려 있습니다.

이러한 행동을 일으키는 메커니즘은 게임의 승리 규칙이 가진 이진법적 본질에 뿌리를 두고 있습니다. 큰 숫자가 더 작은 부분들로 나뉠 때, 가장 작은 부분들은 이진수의 하위 비트를 뒤섞어 마치 균일하고 예측 불가능한 것처럼 보이게 만드는 무작위성의 원천 역할을 합니다. 가장 큰 부분들은 너무 드물기 때문에 결과에 영향을 거의 미치지 못합니다. 그러나 특정 중간 범위의 부분 크기들이 결정적인 병목 구간 역할을 합니다. 이 범위에서 부분들은 결과에 영향을 미칠 만큼 충분히 크면서도, 사라져 버릴 정도로 크지는 않습니다. 이 특정 범위에 속하는 부분의 개수가 결과를 결정합니다. 이 범위는 돌의 총 개수가 증가함에 따라 이동하기 때문에, 게임의 균형이 앞뒤로 기울어집니다. 이 특정 범위 내에 있는 부분들의 개수가 짝수인지 홀수인지에 대한 기우성(parity)이 이러한 진동을 일으키는 핵심 동력이 됩니다. 이 범위가 2의 거듭제곱 임계값을 넘나들 때마다 게임의 균형이 뒤집히며 확률이 도약하게 됩니다.

이를 이해하기 위해, 시계의 바늘이 움직이는 속도가 시계 자체의 크기에 따라 변하는 상황을 시계에 비유할 수 있습니다. 돌의 총 개수가 증가함에 따라, '결정적 범위'의 부분 크기는 위로 이동합니다. 부분의 분포는 희귀한 사건을 설명할 때 자주 사용되는 통계 모델인 포아송 분포와 유사한 법칙에 의해 지배되므로, 이 결정적 범위 내에 있는 부분의 개수가 짝수일 확률이 진동하며 톱니 모양의 패턴을 만들어냅니다. 연구는 돌의 총 개수가 증가함에 따라 패배하는 위치의 확률이 단일 숫자로 수렴하지 않음을 확인했습니다. 대신, 정규화된 밀도가 접근할 수 있는 모든 가능한 값의 집합은 특정 스케일링 인자의 1배에서 2배 사이의 전체 구간을 채웁니다.

이 연구는 패배하는 위치를 넘어 확장됩니다. 이는 이 동일한 진동하는 행동이 0이라는 결과뿐만 아니라, 고정된 특정 목표 결과에도 적용됨을 보여줍니다. 모든 고정된 목표 님 합(nim-sum)에 대해, 밀도는 동일한 1차 쇠퇴를 보이며 동일한 정규화 이후에는 동일한 이진 톱니 모양 프로필을 따릅니다. 이는 이진 구조의 게임이 무작위적인 더미 분포에 영구적인 서명을 남기며, 그 서명은 숫자의 규모가 커지더라도 지워지지 않는다는 것을 시사합니다.

이론적 예측을 검증하기 위해, 저자는 돌의 총합이 2만 개에 달하는 모든 가능한 배치에 대해 정확한 개수를 산출했습니다. 이는 모든 조합을 일일이 나열하지 않고도 특수 알고리즘을 사용하여 수십억 개의 조합을 처리하는 정교한 계산적 접근 방식을 필요로 했습니다. 계산 결과는 이론적 예측과 놀라울 정도로 일치했으며, 톱니 모양의 패턴이 수학적 모델의 오류가 아니라 실제임을 확인해주었습니다. 데이터는 규모의 척도가 2의 거듭제곱을 통과하는 정확한 순간에 급격한 전환이 발생하는 것과 같이, 이론이 예측한 대로 확률이 오르내린다는 것을 보여주었습니다.

연구는 또한 이러한 정점과 골 사이의 전이(transition)의 본질을 탐구합니다. 겉보기에는 확률이 갑자기 튀어 오르는 것처럼 보이지만, 결정적 범위 내의 부분 개수가 짝수인지 홀수인지에 따라 결정되는 이 변화는 점점 좁아지는 구간 안에서 점진적인 변화로 부드럽게 이어집니다. 이 매끄러움은 무작위 사건의 기우성을 설명하는 동일한 통계 법칙에 의해 지배됩니다. 돌의 총 개수가 증가함에 따라 이 매끄러움이 발생하는 창(window)은 점점 좁아지며, 이로 인해 육안으로는 도약이 점점 더 날카롭게 보이지만 수학적으로는 여전히 연속적인 상태를 유지하게 됩니다. 이 현상은 왜 근저의 수학은 매끄러움에도 불구하고 데이터가 그렇게 들쭉날쭉해 보이는지를 설명해 줍니다.

궁극적으로, 이 작업은 시작 구성이 무작위로 선택되었을 때 님 게임에서 패배하는 위치가 어떻게 분포되는지에 대한 완전한 설명을 제공합니다. 이는 이러한 위치의 빈도에 대한 오랜 의문을 해결하며, 그것들이 단순하고 일정한 추세를 따르는 것이 아님을 보여줍니다. 대신, 그것들은 더미의 크기와 게임의 이진 구조 사이의 복잡한 상호작용에 의해 지배됩니다. 연구 결과는 시스템이 무작위적이고 매끄러워 보이는 상황에서도, 깊은 산술적 구조가 평균화되는 것에 저항하는 지속적이고 날카로운 패턴을 만들어낼 수 있다는 수학의 더 넓은 원리를 강조합니다. 게임의 이진적 특성은 특정 정보 블록이 시스템이 커지더라도 계속 가시적이고 영향력 있게 남도록 보장하며, 숫자가 커짐에 따라 영원히 반복되는 리듬을 만들어냅니다.

기술 요약: 무작위 정수 분할의 님-합(Nim-Sum)

문제 정의
본 논문은 총 토큰의 수가 $N$ 으로 고정된 일반적인 님(Nim) 위치의 수론적 성질을 조사한다. 님 게임에서 하나의 위치는 힙(heap) 크기들의 다중 집합(multiset)으로 정의된다. 부톤(Bouton)의 정리에 의해, 어떤 위치가 패배하는 위치가 될 필요충분조건은 힙 크기들의 비트 단위 배타적 논리합(XOR)이 0인 것이다. 힙의 순서를 무시할 때, 이러한 위치들은 $N$ 의 정수 분할에 대응한다.

핵심 문제는 $a_N / p(N)$ 의 점근적 거동을 결정하는 것이다. 여기서 $p(N)$ 은 $N$ 의 전체 정수 분할의 수이고, $a_N$ 은 부분들의 XOR 합이 0인 분할의 수이다. 홀수 $N$ 에 대해서는 $a_N = 0$ 인데, 이는 합과 XOR이 동일한 최하위 유효 비트(LSB)를 공유하기 때문이며, 이는 즉각적인 패리티 제한 사항이다. 그러나 짝수 $N$ 에 대하여, 가공되지 않은 밀도(raw density)는 0으로 수렴하지만, 적절하게 정규화된 밀도(normalized density)는 표준적인 분할 점근법으로는 포착할 수 없는 복잡하고 비수렴적인 진동 거동을 보인다.

방법론
저자는 조합론적 분해, 확률 모델링, 그리고 해석적 정수론을 결합한 다각적인 접근 방식을 사용한다:

조합론적 분해: 논문은 부분의 중복도(multiplicity)를 기준으로 분할 $\lambda$ 를 두 구성 요소로 분해한다. 만약 부분 $j$ 가 $c_j$ 번 나타난다면, 이를 $c_j = 2r_j + \varepsilon_j$ (단, $\varepsilon_j \in \{0, 1\}$ )로 쓸 수 있다. 짝수 개의 복사본( $2r_j$ )은 XOR 합에서 상쇄되므로, 오직 "홀수 코어"( $\varepsilon_j=1$ 인 부분들)만이 남는다. 이는 문제를 서로 다른 부분들로 이루어진 분할의 XOR 분석으로 축소시킨다.
볼츠만 샘플링(Boltzmann Sampling): 독립성을 활용하기 위해, 연구는 총 크기가 무작위인 볼츠만 모델로 전환한다. 이 모델에서 서로 다른 부분들의 포함 여부에 대한 지시 변수(indicator)들은 독립적인 베르누이 변수이다. 0인 XOR 합의 확률은 임계 스케일 $J$ $J$ 를 기준으로 정수들을 세 가지 이진 범위(dyadic range)로 나누어 분석된다:
- 하위 블록 ( $[1, J)$ ): 이 작은 부분들은 하위 비트들을 무작위화하여, 하위 비트들에 대해 거의 균등한 분포를 생성한다.
- 임계 블록 ( $[J, 2J)$ ): 이 범위는 1차 확률을 결정한다. $[J, 2J)$ 범위의 모든 정수는 동일한 최상위 $J$ -비트를 갖는다. 이 블록의 최상위 비트 XOR 합이 0이 되는 것은 선택된 부분의 개수가 짝수인 경우와 동치이며, 이 조건이 충족될 때 하위 블록은 남은 하위 비트 잔여물(lower-bit residue)과 일치해야 한다.
- 상위 블록 ( $[2J, \infty)$ ): 이 큰 부분들은 드물게 나타나며 1차 항에 미치는 영향이 미미하다.
이진 계층 구조 및 월시 분석(Walsh Analysis): 저자는 정확한 유한 공식을 도출하고 근사를 정교화하기 위해 월시 분석( $\mathbb{F}_2$ 상의 특성 직교성)을 활용한다. 이진 계층 구조는 볼츠만 근사를 임의의 대수적 차수까지 정교화하지만, 고정된 크기의 분할로의 전달은 1차 항에서만 확립된다.
사델 포인트 분석(Saddle Point Analysis): 볼츠만 모델(무작위 크기)에서 고정된 크기의 분할으로 결과를 전달하기 위해, 생성 함수에 대한 사델 포인트 방법을 사용한다. 생성 함수의 짝수 성질 때문에 두 개의 동일한 사델( $q = e^{-t_N}$ 근처와 $q = -e^{-t_N}$ 근처)을 식별한다.
정확한 계산: 월시 공식과 중국인의 나머지 정리(CRT)에 기반한 정확한 알고리즘을 구현하여 $N=20,000$ 까지 $a_N$ 을 계산하였다. 이는 점근 공식의 검증과 유한 크기 보정 분석의 용도로 사용된다.

주요 결과
논문은 패배하는 위치의 밀도에 대한 1차 점근적 거동을 확립한다. $\tau_N = \pi/\sqrt{6N}$ 이라 하고, $B_N = \log(1/\tau_N)/\tau_N$ 이라 하자. $J_N$ 을 곱셈적 거리에서 $B_N$ 에 가장 가까운 2의 거듭제곱이라 한다. $\Lambda_N = e^{-\tau_N J_N}/\tau_N$ 이라 정의하자.

짝수 $N$ 에 대하여, 비율은 다음과 같다:
$\frac{a_N}{p(N)} = \frac{1 + e^{-2\Lambda_N} + o(1)}{J_N}$

주요 결과는 다음과 같다:

비수렴성: 정규화된 밀도 $B_N \frac{a_N}{p(N)}$ 은 수렴하지 않으며, 그 부분 수렴 극한(subsequential limits)의 집합은 전체 구간 $[1, 2]$ 이다.
이진 톱니 모양(Dyadic Sawtooth): 그 거동은 "이진 톱니 모양" 패턴을 따른다. $N$ 이 증가함에 따라(즉, $B_N$ 이 2의 거듭제곱을 통과함에 따라) 값은 1에서 2로 상승하며, 스케일이 새로운 2의 거듭제곱을 통과할 때 다시 1로 떨어진다.
포아송 평활화(Poisson Smoothing): 이진 경계에서의 외견상의 불연속성은 포아송 확률 변수의 패리티 법칙에 의해 줄어드는 스케일 위에서 평활화된다. 구체적으로, $N$ 이 경계에 접근하여 $\tau_N K - \log(1/\tau_N) \to c$ (여기서 $K$ 는 2의 거듭제곱)를 만족할 때, 극한값은 $1 + e^{-2e^{-c}}$ 이다.
일반적인 님-합: 이 결과는 0인 XOR 합에만 국한되지 않는다. 고정된 타겟 님-합 $x$ 를 갖는 분할의 밀도 또한 패리티 클래스 $N \equiv x \pmod 2$ 를 따라 동일한 1차 프로파일을 따른다.
정확한 계수: 본 논문은 OEIS 수열 A048833을 인덱스 10,000(총 크기 $N=20,000$ )까지 확장하여, 예측된 스케일과 유한 크기 오차의 구조를 확인해 주는 정확한 데이터를 제공한다.

의의 및 주장
본 논문은 제약 없는 정수 분할에 대한 패배하는 님 위치의 완전한 1차 점근적 묘사를 제공한다고 주장한다. 이 연구의 의의는 "매끄러운" 무작위 구조(정수 분할)가 하위 비트들이 무작위화된 후에도 상위 비트들이 미미하게 작용하는 단일 임계 이진 블록의 존재로 인해 날카로운 산술적 특징(이진 패리티)을 유지한다는 것을 밝혀낸 데 있다.

이 연구는 패배하는 위치의 밀도가 $\Theta(1/(\sqrt{N} \log N))$ 의 차수이지만 단일한 점근적 상수를 갖지 않음을 보여준다. 저자는 "이진 계층 구조"를 통해 볼츠만 근사를 임의의 대수적 차수까지 정교화할 수 있음을 강조하며, 왜 1차 정리가 유효한 상황에서도 유한 크기 보정이 중요한지를 설명한다. 논문은 이러한 비수렴성이 근사의 실패가 아니라 문제의 구조적 특징임을 결론짓고, 전이 과정이 포아송 확률 변수의 패리티에 의해 지배됨을 명시한다.

본 논문은 성장하는 타겟 님-합이나 제한된 분할에 대한 일반적인 문제를 해결한다고 주장하지 않으며, 이를 자연스러운 미해결 과제로 남겨둔다. 또한, 유한 크기 보정 분석이 엄밀한 상계(uniform bounds)를 사용한 것이 아닌 형식적 전개(formal expansions)에 의존하므로, 이를 완전한 2차 정론이라고 주장하지 않는다.

유사한 논문