RSS Feed

님(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$인 것은 모두 몇 개입니까?


로그인 하시면 답안을 제출할 수 있고,
정답을 맞히신 분들은 댓글을 달거나 볼 수 있습니다.