스프래그-그룬디 정리

이 글에는 여러 가지 문제가 있다.이 문제를 개선하거나 대화 페이지에서 토의하십시오.(이러한 템플릿 메시지를 제거하는 방법 및 시기 알아보기) 이 글은 일반적인 참고문헌 목록을 포함하고 있지만, 그에 상응하는 인라인 인용구가 충분하지 않다. 좀 더 정밀한 인용구를 도입하여 이 기사를 개선할 수 있도록 도와주십시오.(2014년 6월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기) 이 글은 대부분의 독자들이 이해하기에는 너무 기술적인 것일 수도 있다. 기술 세부 정보를 삭제하지 않고 비전문가가 이해할 수 있도록 개선하십시오.(2014년 6월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기) (이 템플릿 메시지를 제거하는 방법 및 시기 알아보기)

결합 게임 이론에서, 스프래그-그룬디 정리는 정상적인 플레이 컨벤션 하에서 모든 공평한 게임은 님(Nim)의 1에이프 게임이나 님(Nim)의 무한 일반화에 해당한다고 명시하고 있다.따라서 그것은 자연수, 즉 등가선 게임에서 힙의 크기, 무한 일반화의 서수 수, 또는 또는 그 대신에 추가 연산이 여러 개의 힙을 결합하여 님에서 하나의 등가선 힙을 형성하는 대수적 시스템에서 그 1-heap 게임의 가치를 님으로 나타낼 수 있다.

공평한 게임의 그룬디 가치나 민첩한 가치는 게임이 동등한 독특한 민첩성이다.자연수에 의해 포지션이 인덱싱되는 게임의 경우(예: 힙 크기에 의해 인덱싱되는 님 그 자체) 게임의 연속적인 포지션에 대한 민첩성의 순서를 게임의 님 시퀀스라고 한다.

스프래그-그룬디 정리와 그 증거는 R. P. 스프래그(1936)^[1]와 P. M. 그룬디(1939)에 의해 독자적으로 발견된 이론의 주요 결과를 캡슐화한다.^[2]

정의들

스프래그-그룬디 정리의 목적상 게임은 엔드 조건(모든 게임이 끝나게 된다: 무한의 라인이 없다)과 정상적인 플레이 조건(움직이지 못하는 선수)을 만족시키는 완벽한 정보를 가진 2인용 순차 게임이다.

경기 중 어느 지점에서든 선수의 위치는 그들이 할 수 있는 일련의 움직임이다.일례로 제로 게임을 두 선수 모두 합법적인 움직임이 없는 투 플레이어 게임으로 규정할 수 있다.두 플레이어를 $A{\displaystyle }$ ${\displaystyle$A}($$앨리스의 경우)와 B ${\displaystyle$B}($$Bob의 경우)로 지칭하면 각 플레이어의 동작 집합이 비어 있으므로 (${\displaystyle A,}$ ${\displaystyle B}$ )${\displaystyle }$= (${\displaystyle }${${\displaystyle \},}$ {${\displaystystyle(A,B)=(\{\},\})})$로 위치를 표시한다$.$

공평한 게임은 게임에서 주어진 어떤 지점에서, 각 플레이어가 정확히 같은 일련의 움직임을 허용받는 게임이다.정상적인 플레이는 공정한 경기의 한 예다.님에는 하나 이상의 물체가 쌓여 있고, 두 명의 플레이어(우리는 앨리스와 밥이라고 부름)가 돌아가면서 힙을 선택하고 그 속에서 하나 이상의 물체를 제거한다.우승자는 최종 힙에서 최종 오브젝트를 제거하는 선수다.게임은 공정하다. 왜냐하면 앨리스가 그녀의 차례에서 할 수 있는 동작은 밥이 그의 차례라면 할 수 있는 동작과 정확히 같기 때문이다.이와는 대조적으로, 체커와 같은 게임은 공정하지 않다. 왜냐하면 앨리스가 빨간색으로 놀고 있고 밥이 검은색으로 칠하고 있었다고 가정할 때, 만약 앨리스의 차례라면, 그녀는 빨간 조각만 움직일 수 있고, 밥의 차례라면 검은 조각만 움직일 수 있기 때문이다.

따라서 공평한 게임의 구성은 어느 쪽이든 같은 포지션으로 기록될 수 있다는 점에 유의하십시오. 누구의 차례든 이동은 동일하기 때문이다.예를 들어 제로 게임의 위치는 간단히 $\{\}{\displaystyle }$ ${\displaystyle \{\}}$라고 쓸 수 있는데$,$ 왜냐하면 앨리스의 차례라면 그녀는 할 동작이 없고, 밥의 차례라면 그도 할 동작이 없기 때문이다.이동은 다음 선수를 남겨두는 위치와 연관될 수 있다.

그렇게 하면 위치가 반복적으로 정의될 수 있다.예를 들어 앨리스와 밥이 하는 님의 다음 게임을 생각해 보자.

님의 게임 예

A B C 1 2 앨리스는 A 0에서 1을 B 0에서 1을 B 0에서 1을 B 0에서 1을 B 0에서 1을 B 0에서 1을 B 0에서 1을 B 0에서 1을 B 0에서 1을 C 0에서 0에서 0을 1로 가져갔기 때문에 앨리스가 이긴다.

• 게임의 6단계(모든 힙이 비어 있을 때)에서 위치는 {} ${\displaystyle \{\}$인데$,$ 이는 밥이 유효한 동작을 할 수 없기 때문이다.이 직책의 명칭은${\displaystyle 0}$ 0 {\$displaystyle *0}$ 입니다$.$
• 5단계에서 앨리스는 정확히 한 가지 옵션을 가지고 있었다: 힙 C에서 한 가지 물체를 제거하는 것, 즉 밥은 움직이지 않게 하는 것.그녀의 움직임은 Bob을 위치 ${\displaystyle 0}$에 남겨두기 때문에 그녀의 위치는 {${\displaystyle \ast }$ ${\displaystyle 0}$ ${\displaystyle \}}$ ${\displaystyle \{*0\}}$라고 쓰여 있다$.$ 우리는 이 ${\displaystyle \mathrm{위치}}$의 이름을 $\ast {\displaystyle }$ 1 ${\displaystyle *1}.$
• 4단계에서 Bob은 B에서 하나를 제거하거나 C에서 하나를 제거하는 두 가지 옵션을 가지고 있었다.그러나 Bob이 어떤 힙에서 객체를 제거했는지는 중요하지 않다는 점에 유의하십시오.어느 쪽이든 앨리스는 정확히 하나의 더미 속에 하나의 물체를 남겨 두게 될 것이다.그래서, 우리의 재귀적 정의를 사용한다면, 밥은 정말로 오직 한 가지 움직임만을 가지고 있다: $\ast {\displaystyle }$ ${\displaystyle 1}$ ${\displaystyle *1$ 따라서, 밥의 위치는${\displaystyle }${${\displaystyle 1}$ 1 ${\displaystyle \}}$ ${\displaystyle \{*1$
• 3단계에서 앨리스는 C에서 두 개를 제거하거나, C에서 하나를 제거하거나, B에서 하나를 제거하는 세 가지 옵션을 가졌다.C에서 두 개를 제거하면 Bob이 ${\displaystyle \mathrm{위치}}$ $\ast {\displaystyle }$ 1 ${\displaystyle *1}$에 위치하게 된다$.$ C에서 하나를 제거하면 Bob은 각각의 크기 1인 ${\displaystyle \mathrm{위치}}$ { $,$ 1${\displaystyle \}}$ $displaystyle \{*1\}}}}$의 두 개의 더미를 갖게 된다$.$그러나 B에서 1을 제거하면 밥은 한 무더기에 두 개의 물체를 갖게 된다.His moves would then be ${\displaystyle *0}$ and ${\displaystyle *1}$, so her move would result in the position ${\displaystyle \{*0,*1\}}$. We call this position ${\displaystyle *2}$. Alice's position is then the set of all her moves: ${\displaystyle {\big \$${}*1,\{*1\},*2{\big$ $\backslash \}\}.$
• 같은 재귀적 논리에 따라 2단계에서 밥의 위치는 {${\displaystyle \ast }$ ${\displaystyle 1,}${ ${\displaystyle \ast }$ ${\displaystyle 1}$ ${\displaystyle \},\ast }$ ${\displaystyle 2}$ ${\displaystyle \},\ast }$ ${\displaystyle 2}$} $}$ {\$displaystyle {\{\}\{*1\}\{*1\},*2\},*2$
• 마침내 1단계에서 앨리스의 위치는

${\displaystyle {\Big \{}{\big \{}*1,\{*1\},*2{\big \}},{\big \{}*2,\{*1,\{*1\},*2\}{\big \}},{\big \{}\{*1\},\{\{*1\}\},\{*1,\{*1\},*2\}{\big \}}{\Big \}}}$.

님버스

본 예제에서 언급된 특수$$ 이름 names ${\displaystyle *0},$${\displaystyle }$$,$ ${\displaystyle 1}$ ${\displaystyle *$1}, $,$${\displaystyle 2}$ ${\displaystyle *2$}을$($를) 님버라고 부른다.일반적으로 님 게임에서 님 ${\displaystyle \mathrm{게임}}$에서 님 게임에서 $\ast {\displaystyle }$n {\$displaystyle$ *$n}$개의 객체가$$ 정확히 하나의 힙에 $n{\displaystyle }$ ${\displaystyn}$개의 객체가 있는 위치에 해당한다$$.Formally, nimbers are defined inductively as follows: ${\displaystyle *0}$ is ${\displaystyle \{\}}$, ${\displaystyle *1=\{*0\}}$, ${\displaystyle *2=\{*0,*1\}}$ and for all ${\displaystyle n\geq 0}$, ${\displaystyle *(n+1)=*n\cup \{*$$n$

님버라는 단어는 게임 님에서 유래한 것이지만 님버는 어떤 유한하고 공정한 게임의 위치를 기술하는데 사용될 수 있으며, 사실 스프래그-그룬디 정리는 유한하고 공정한 게임의 모든 예는 님버 한 명과 연관될 수 있다고 기술하고 있다.

콤비네이션 게임스

포지션을 함께 추가하면 두 경기를 병행할 수 있다.예를 들어, 힙 $A{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$ A$\text{'}\},$ $B{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$ B$'}$및 $C{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$을(를) 사용한 님 게임을 한 번 더 생각해 보십시오$.$

예제 게임 2

A' B' C' 1 1 1 B' 1 A' 1 1 Bob은 B' 0 1 B' 0 1 B' 0 1 B' 0 Bob에서 1 B. 0 Bob은 움직임이 없기 때문에 앨리스가 이긴다.

우리는 그것을 우리의 첫 번째 예와 결합하여 여섯 개의 히프를 가진 복합 게임을 얻을 수 있다.${\displaystyle A}$ ${\displaystyle A$ $B{\displaystyle }$ ${\displaystyle B$ $C{\displaystyle }$ ${\$$displaystyle C$$\},$ $A{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$displaystyle A$\text{'}\},$ $B{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$ $B$$'}$및 C ${\displaystyle {\prime }^{}}$ ${\$ C$\text{'}\}:$

콤바인드 게임

Sizes of heaps     Moves  A  B  C  A' B' C'       1  2  2  1  1  1   Alice takes 1 from A  0  2  2  1  1  1   Bob takes 1 from A'  0  2  2  0  1  1   Alice takes 1 from B'  0  2  2  0  0  1   Bob takes 1 from C'  0  2  2  0  0  0   Alice takes 2 from B  0  0  2  0  0  0   Bob takes 2 from C  0  0  0  0  0  0   Alice has no moves, so Bob wins.

두 게임을 구분하기 위해 첫 번째 예시 게임의 시작 위치 $S{\displaystyle }$ ${\$에 라벨을 붙인다.$S}$ $,$ 그리고 파란색으로 색칠하십시오.

${\displaystyle \color}S={\Big \{}{\big \{}*1,\{*1\},*2{\big \}},{\big \{}*2,\{*1,\{*1\},*2\}{\big \}},{\big \{}\{*1\},\{\{*1\}\},\{*1,\{*1\},*2\}{\big \}}{\Big \}}}$

두 번째 예제 게임의 경우 시작 위치 $S{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$에 라벨을 붙이고$$ 빨간색으로 칠하십시오.

${\$$S'={\Big \{}\{*1\}{\Big$ $\backslash \}\}\}.$

복합 게임의 출발 위치를 계산하려면 첫 번째 게임에서 플레이어가 움직여서 두 번째 게임을 그대로 두거나 두 번째 게임에서 첫 번째 게임을 그대로 둘 수 있다는 점을 기억해야 한다.따라서 복합 경기의 출발 위치는 다음과 같다.

${\displaystyle \color}S\color {black}+\color {red}S'\color {black}={\Big \{}\color {blue}S\color {black}+\color {red}\{*1\}\color {black}{\Big \cup}\Big \{}\color {red}S'\color {black}+\color {blue}\{*1,\{*1\},*2\}\color {black}\color {red}S'\color {black}+\color {blue}\{*2,\{*1,\{*1\}}\color {black}\color {red}S'\color {black}+\color {black}\{*1\}}\\{\*1\}\{*1,\}}\{*1\}\color {black}{\big \}}}}}}}}}}}$

The explicit formula for adding positions is: ${\displaystyle S+S'=\{S+s'\mid s'\in S'\}\cup \{s+S'\mid s\in S\}}$, which means that addition is both commutative and associative.

등가성

공정한 경기의 포지션은 두 가지 결과 등급으로 나뉜다: 다음 선수(턴이 있는 선수)가 승리하거나(N ${\$$N$$\}\}\}-),$ 이전 선수가 승리한다($P{\displaystyle \mathcal{}}$ ${\$P$\}).$예를 들어 $\ast {\displaystyle }$ ${\displaystyle 0}$ ${\displaystyle *0}$은(는) $P{\displaystyle \mathcal{}}$ ${\$ -position이고$$, $\ast {\displaystyle }$ ${\displaystyle 1}$ ${\displaystyle *$1}은$($는) $N{\displaystyle \mathcal{}}$ ${\$ -position이다$$.

두 위치 $G{\displaystyle }$ ${\displaystyle G}$과${\displaystyle {}^{}}G{\displaystyle {}^{}}$ , {\$displaystyle$ G$'}$은(는$)$ 어떤 위치 $H{\displaystyle }$ ${\displaystyle H}$을(를) 추가하든 항상 동일한 결과 등급에 있으면 동일하다.공식적으로 $\forall {\displaystyle \mathrm{}}$ ${\displaystyle H}$ ${\displaystyle \forall$ H$\},$ $G{\displaystyle }$+ ${\displaystyle H}$ ${\displaystyle$ G$'+H}$이(가) $G{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$+ H ${\displaystyle G'+H$과(와) 동일한 결과 클래스에 속하는 경우에만$$ $G{\displaystyle }$ ${\displaystyle \approx }$ G ′ ${\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$

우리의 러닝 예시를 이용하기 위해, 위의 1차 경기와 2차 경기 모두에서, 앨리스가 매번 Bob을 $P{\displaystyle \mathcal{}}$ ${\${\$mathcal {P}$의 포지션으로 밀어 넣는 동작을 할 수 있다는 것을 알 수 있다.$따라서{\displaystyle }$ 두 S ${\$$S}$ 및$$ S ${\displaystyle {\prime }^{}}$ ${\$은(는) $N{\displaystyle \mathcal{}}$ ${\$ - positions이다$$.(복합 게임에서 $밥$은 N ${\$ -positions를$$ 가진 선수라는 점에 유의하십시오.사실, $S{\displaystyle }$+ ${\displaystyle S{}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$$S\color {black}+\color {red}$$S'}$은(는$)$ P {\$displaystyle$ {\$mathcal {P}}$ -위치인데$$, 우리가 Lema 2에서 보게 될 것처럼 $S{\displaystyle }$ ${\displaystyle \approx }$ ${\displaystyle S{}^{}}$′ ${\$을(를) 의미한다.$S\color {black}\대략 \color {red}S')$

퍼스트 보조정리

주 정리를 증명하기 위한 중간 단계로서 $모든{\displaystyle }$ 위치$$ G ${\displaystyle G}$ 및 모든 $P{\displaystyle \mathcal{}}$ ${\${\$mathcal$ {P$}}$ - 위치 A$$ ${\displaystyle A}$에$$대해 $동등성{\displaystyle }$ G ${\displaystyle \approx }$ ${\displaystyle A}$+ ${\displaystyle G}$ ${\displaystysty$ G\$$약 A$+G}$이 유지됨을$$ 보여준다.$위$의 동등성 정의에 따르면 이는 G${\displaystyle }$+ ${\displaystyle H}$ ${\displaystyle G+H}$ 및 A$$${\displaystyle }$+ ${\displaystyle G}$+ H ${\displaystyle A+G+H}$이(가) 모든 $H{\displaystyle }$ ${\displaystyle H$에 대한 결과 클래스를 공유한다는$$ 것을 보여주는 것과 같다.

$G{\displaystyle }$+ ${\displaystyle H}$ ${\displaystyle G+H}$이(가) $P{\displaystyle \mathcal{}}$ ${\$ - 위치라고$$$$ 가정합시다.그러면 $이전{\displaystyle }$ 플레이어는 A${\displaystyle }$+ ${\displaystyle G}$+ ${\displaystyle H}$ ${\displaystyle$ A$+G+H}$에 대한 승리 전략을 가지고 있다$.$$$ $A{\displaystyle }$ ${\$$displaystyle A}($A {\$displaystyle$ A}이($가{\displaystyle \mathcal{}}$) P ${\$ 포지셔닝으로 존재$$)에 따라$$ A ${\$displaysty $A}$에 응답하고 이동에 대응한다.$G{\displaystyle }$+ ${\displaystyle H}$ ${\displaystyle G+H$$}$에 대한 승자 전략에$$ 따라 G + H ${\displaystyle G+H$$}($$$유사한 이유로 존재함).따라서 $A{\displaystyle }$+ ${\displaystyle G}$+ ${\displaystyle H}$ ${\displaystyle A+G+H}$도 P ${\$ - 위치여야$$ 한다$$.

On the other hand, if ${\displaystyle G+H}$ is an ${\displaystyle {\mathcal {N}}}$-position, then ${\displaystyle A+G+H}$ is also an ${\displaystyle {\mathcal {N}}}$-position, because the next player has a winning strategy: choose a ${\displaystyle {\mathcal {P}}}$-position from among$G{\displaystyle }$+ ${\displaystyle H}$ ${\displaystyle G+H}$ 옵션에서$$ 앞 단락부터 $A{\displaystyle }$ ${\displaystyle A}$을(를) 해당 위치에 추가하는$$ 것이 여전히 $P{\displaystyle \mathcal{}}$ ${\$ -position이라고$$ 결론짓는다.따라서 이 경우 $A{\displaystyle }$+ ${\displaystyle G}$+ ${\displaystyle H}$ ${\displaystyle A+G+H}$은(는) $G{\displaystyle }$+ ${\displaystyle$ ${\mathcal{N}}$ - $위치$여야 한다$$$.$

이 두 가지 사례밖에 없기 때문에 보조정리기가 버티고 있다.

제2 보조정리

한 단계 더 나아가 $G{\displaystyle }$′ ${\displaystyle {}^{}}$ {\$displaystyle G\약 G'}$을(를) $P{\displaystyle \mathcal{}}$ ${\$$G+$$G}$ -position인$$$$ 경우에만$$ $표시$한다$.$

In the forward direction, suppose that ${\displaystyle G\approx G'}$. Applying the definition of equivalence with ${\displaystyle H=G}$, we find that ${\displaystyle G'+G}$ (which is equal to ${\displaystyle G+G'}$ by commutativity of addition) is in the same outcome class as ${\displaystyle G+G}$${\displaystyle G+$$G$$\}.$ $그러나{\displaystyle }$G + ${\displaystyle G}${\$displaystyle$ $G}$은$($는) $P{\displaystyle \mathcal{}}${\$displaystyle {\$$mathcal{P}$ -position$$: $모든{\displaystyle }$ 이동에 대해 이전 플레이어는 다른 복사본에서 동일한 이동으로 응답할 수 있으므로 항상 마지막 이동이어야 한다$$$.$

In the reverse direction, since ${\displaystyle A=G+G'}$ is a ${\displaystyle {\mathcal {P}}}$-position by hypothesis, it follows from the first lemma, ${\displaystyle G\approx G+A}$, that ${\displaystyle G\approx G+(G+G')}$. Similarly, since ${\displaystyl$$e B=G+G}$ is also a ${\displaystyle {\mathcal {P}}}$-position, it follows from the first lemma in the form ${\displaystyle G'\approx G'+B}$ that ${\displaystyle G'\approx G'+(G+G)}$.연관성과 일치성에 의해, 이러한 결과의 오른쪽은 동일하다.또한 동등성은 결과 등급에 대한 동등성 관계이기 때문에 $\approx {\displaystyle }$ ${\displaystyle$\ 약$}$은 동등성 관계다.$\approx {\displaystyle }$ ${\displaystyle$\ \$$\ \$closure$ g'의 transitability를 통해 우리는 $G{\displaystyle }$ ${\displaystyle \approx }$ ${\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$로 결론을 내릴 수 있다$.$

증명

우리는 구조 유도에 의해 모든 포지션이 민첩하다는 것을 증명한다.주어진 게임의 초기 위치가 더 민첩해야 한다는 보다 구체적인 결과는 게임 자체가 더 민첩하다는 것을 보여준다.

Consider a position ${\displaystyle G=\{G_{1},G_{2},\ldots ,G_{k}\}}$. By the induction hypothesis, all of the options are equivalent to nimbers, say ${\displaystyle G_{i}\approx *n_{i}}$. So let ${\displaystyle G'=\{*n_{1}$$,*n_{2},\ldots ,*n_{k}\}}$. We will show that ${\displaystyle G\approx *m}$, where ${\displaystyle m}$ is the mex (minimum exclusion) of the numbers ${\displaystyle n_{1},n_{2},\ldots ,n_{k}}$, that is, the smallest non-negative integer not equal to some ${\displaystyle n_{i$$}}$.

우리가 가장 먼저 주목해야 할 것은 두 번째 보조정리기를 통해 $G{\displaystyle }$g ${\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$ 약 G$'}라는 점$이다$.$$k{\displaystyle }$ ${\displaystyle k}$이(가) 0이면 그 주장은 사소한 사실일 뿐이다.Otherwise, consider ${\displaystyle G+G'}$. If the next player makes a move to ${\displaystyle G_{i}}$ in ${\displaystyle G}$, then the previous player can move to ${\displaystyle *n_{i}}$ in ${\displaystyle G'}$, and conversely if the next player makes a move in ${\disp$$레이스타일 G$ 이 후, 보조마사의 전방 함축에 의한 $P{\displaystyle \mathcal{}}$ ${\${\$mathcal{P}$ 위치$$.따라서 $G{\displaystyle }$+ ${\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$은(는$)$ P {\$displaystyle$ {\$mathcal${P$$$}}$ -포지션이며$$, 보조마사의 역 함축적 의미를 $들어{\displaystyle }$ ${\displaystyle {}^{}}$g G${\displaystyle {}^{}}${ ${\$ G$'}$을(는)라고 한다$.$

$이제{\displaystyle {}^{}}$ G ${\displaystyle {\prime }^{}}$+ ${\displaystyle \ast m}$ m ${\displaystyle$ G$'+*m}$이(가) P$${\$displaystyle${\$mathcal{P}}$위치임을$$ 보여주자, 두 번째 보조정리기를 다시 한 번 $사용$한다는 것은${\displaystyle {}^{}}$G ${\displaystyle \approx }$ ≈ m ≈ m$m$ m${\stythreasy *m$ 이전 플레이어에 대해 명시적인 전략을 부여하여 그렇게 한다.

$G{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$ G$'}$ 및$$ $\ast {\displaystyle }$ ${\displaystyle m}$ ${\displaystyle *m}$이(가) 비어 있다고$$ 가정해 보십시오.${\displaystyle \mathrm{그러면}}$ $G{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$+ ${\displaystyle \ast }$ m ${\displaystyle G'+*m}$이(가) null 집합으로$$, $분명히{\displaystyle \mathcal{}}$ P ${\${\$mathcal {P}}$ -position이다$$.

왜냐하면 m{m\displaystyle}은 최소 제외 수 아니면 옵션에 ∗ m′{\displaystyle *m의}어디 m′<>m{\displaystyle m'<입니다 나이}., 이전 선수 G장조′{\displaystyle G의}∗에 m′{ 움직일 수 있는 다음 선수 구성 요소 ∗ m{\displaystyle *m}에 움직이고려해 보라.\displ$aystyle *m'}$. 그리고 앞에서 보듯이 어떤 포지션 플러스 그 자체는 $P{\displaystyle \mathcal{}}$ ${\$ -position이다$$.

만약 제가 &lt와 마지막으로, 대신 다음 선수는 구성 요소에서 G옵션에 ni{\displaystyle *n_{나는}∗{\displaystyle G의}′}를 움직인다.;m{\displaystyle n_{나는}<, ∗ m{\displaystyle *m}에서 제일}그 때 이전 선수 움직임 나는{\displaystyle *n_{나는}n∗에}, ni입니다. 가정합니다..{\d$isplaystyle n_{i}>m$ 이전 플레이어는 $\ast {\displaystyle n_{}}$ i ${\$에서 $\ast {\displaystyle m}$ m ${\displaystyle *m}$로 이동한다$.$ 두 경우 모두 결과는 포지션 플러스 그 자체다.($m{\displaystyle }$ ${\displaystyle n_$${i}=m$$}$이(가) 모든 $n{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$와(와) 다르다고 정의되었기$$ 때문에$$ n ${\displaystyle i_{}}$= ${\displaystyle m}$ ${\displaystyle$ n_{i}=m$}$일 수 없음)$$

요약하면, ${\displaystyle {}^{}}$는 $G{\displaystyle {}^{}}$${\displaystyle }$′ G ${\displaystyle {\prime }^{}}$ ${\$ 약 G'}과 G $}$${\displaystyle {}^{}\approx }$ $∗$ ${\displaystyle m}$ {\$displaystyle G$$'\ 약$$*m}$을(를) 가지고$$ 있다$.$ transitability에 의해 $G{\displaystyle }$ ${\displaystyle \approx }$ ${\displaystyle \ast }$ ∗ ${\displaystyle m}$ ${\displaysty$ G\ $약 *m$으로 결론짓는다.

개발

$G{\displaystyle }$ ${\displaystyle G}$이(가) 공평한 게임의 위치라면 $G{\displaystyle }$≈ ${\displaystyle \ast }$ m$${\$displaystyle G\ 약$ *$m}$과 같은 고유한 $정수{\displaystyle }$ m$${\$displaystym$ m$}$을 그룬디 값 또는 그룬디 번호라고 하며, 이 값을 각각의 그러한 위치에 할당하는 함수를 스프래그룬디 함수라고 한다.R. L. Sprague와 P. M. Grundy는 독립적으로 이 기능의 명시적 정의를 내렸으며, 님 포지션에 대한 동등성의 어떤 개념에 기초하지 않았으며, 다음과 같은 속성을 가지고 있음을 보여주었다.

• 크기 $m$의$$단일 님 $더미$ {\$displaystyle$ m$}($즉, $\ast {\displaystyle m}$ m ${\displaystyle *m$ $위치$의 Grundy 값은 m ${\displaystyle m$
• 포지션은 그룬디 값이 0인 경우에만 다음 플레이어가 이동할 수 있는 손실($즉{\displaystyle \mathcal{}}$, P ${\$ -position$$)이다.
• 유한한 위치 집합의 합계의 그룬디 값은 그 총계의 그룬디 값의 님섬일 뿐이다.

It follows straightforwardly from these results that if a position ${\displaystyle G}$ has a Grundy value of ${\displaystyle m}$, then ${\displaystyle G+H}$ has the same Grundy value as ${\displaystyle *m+H}$, and therefore belongs to the same outcome class, for any position ${\displaystyle H}$.따라서 스프래그와 그룬디는 이 글에 기술된 정리를 명시적으로 진술한 적은 없지만, 그들의 결과로부터 직접 따르며 그들에게 공로를 인정받는다.^[3][4]이러한 결과는 이후 결합 게임 이론의 분야로 발전되었는데, 특히 리차드 가이, 엘윈 베를캄프, 존 호튼 콘웨이 등이 현재 스프래그-그룬디 정리에 캡슐화되어 있고, 여기에 기술된 형태로 그 증거를 증명하고 있다.이 분야는 '수학적 희곡의 승리 방법'과 '숫자와 게임'이라는 책에 소개되어 있다.

참고 항목

• 속설
• 구별할 수 없는 지수

참조

외부 링크

• 그룬디의 컷더코트 게임
• 읽기 쉽고 UCLA 수학부의 입문 계정
• The Game of Nim sputsoft.com
• Milvang-Jensen, Brit C. A. (2000), Combinatorial Games, Theory and Applications (PDF), CiteSeerX 10.1.1.89.805