님(Nim) 게임
Problem 301
출제 일시 : 2020-12-31 00:01:13, ☕ ☕ ☕
님(Nim) 게임은 몇 개의 돌더미를 가지고 하나의 돌도 남지 않을 때까지 두 선수가 차례대로 몇 개씩의 돌을 제거합니다.
3개의 돌더미를 가진 일반적인 님(Nim) 게임은 다음과 같습니다:
- 게임 초기에 3개의 돌더미가 있습니다.
- 각 선수는 자기 차례에 하나의 돌더미에서 양수 개의 돌을 제거합니다.
- 남아 있는 돌이 없어서 할 게 없어진 선수가 집니다.
$(n_1,n_2,n_3)$을 세 돌더미의 크기가 각각 $n_1$, $n_2$, $n_3$인 님 게임의 상태라고 하면, 아래 값을 반환하는 단순한 함수 $X(n_1,n_2,n_3)$가 존재합니다:
- 0, 완벽한 전략을 사용할 경우, 이번 차례의 선수가 결국 지게 됩니다; 또는
- 0이 아닌 값, 완벽한 전략을 사용할 경우, 이번 차례의 선수가 결국 이깁니다.
예를 들어 $X(1,2,3) = 0$인데, 현재 선수가 무엇을 하더라도, 상대방은 두 돌더미를 같은 크기로 만들 수 있고, 그 다음부터는 현재 선수가 하는 모든 것을 그대로 따라해서 결국 모든 돌을 없앱니다; 그래서 현재 선수가 집니다. 예로 설명해보면:
- 현재 선수가 $(1,2,1)$ 상태로 만듭니다
- 상대방은 $(1,0,1)$ 상태로 만듭니다
- 현재 선수가 $(0,0,1)$상태로 만듭니다
- 상대방이 $(0,0,0)$ 상태로 만들어서 승리합니다.
자연수 $n \le 2^{30}$일 때, $X(n,2n,3n) = 0$인 것은 모두 몇 개입니까?