Grundy Number

Grundy Number는 게임 문제에서 많이 사용되는 방법 중 하나다. Grundy Number는 게임 상황을 Nim Game으로 변환 시켜주는 과정이라고 볼 수 있다.

어떤 상황 $S$에 대한 Grundy  Number를 구하는 방법은 아래와 같다.

상황 $S$에서 다음 상황들 중 하나를 $S'$라고 하자.

$G(S) = \min(v) $ ($v \not\in \{G(S')\}$)

즉, 상황 $S$의 Grundy Number $G(S)$는 상황 $S$의 다음 상황들 $S'$의 Grundy Number $G(S')$들 중 존재하지 않는 가장 작은 수다.

각 상황들을 Grundy Number로 표현했을 때, 필승법의 여부는 Nim Game과 마찬가지로 구하면 된다. Grundy Number로 표현된 각 상황들을 XOR($\oplus$) 했을 때 결과가 0이면 무조건 지는 것이고, 0이 아니면 무조건 이길 수 있다.

이에 대한 증명은 Nim Game의 증명과 매우 유사하게 될 수 있지만, 완전히 같은 것은 아니다. Grundy Number로 새로 표현한 게임이 Nim Game과 완전히 동일한 것은 아니기 때문이다. 그러나 필승법 여부를 판별하는 방법은 동일하다.

자세한 증명은 후에 시간이 되면 추가하겠다.

응용 문제 1) 2014 Kuala Lumpur Regional D (해법)