계단 님

문제

0번부터 N번까지 번호가 매겨진 계단이 있다. 각 계단에는 돌이 0개 이상 놓여 있다.

두 플레이어가 번갈아 가며 다음 행동을 한다.

• 1번 계단 이상의 임의의 계단에서 돌을 1개 이상 골라, 고른 돌들을 바로 아래 계단으로 이동시킨다.
• 0번 계단에 도달한 돌은 게임판에서 제거된다.

더 이상 돌을 이동할 수 없는 플레이어가 패배한다. 모든 돌이 0번 계단에 도달하여 제거된 상태(즉, 모든 계단의 돌 개수가 0)가 되면 이동할 수 없다.

선공 플레이어가 최적의 전략으로 플레이할 때 승리하는지 패배하는지 판별하라.

참고: 이 문제는 님(Nim) 게임의 변형이다. 1번 계단에 있는 돌 $k$개는 일반 님 게임에서 크기가 $k$인 돌 무더기와 같고, 이 돌을 0번 계단으로 이동하는 것은 무더기에서 돌을 완전히 제거하는 것과 같다. 2번 계단 이상에 있는 돌은 다른 계단으로 이동할 수 있으므로 추가적인 전략적 고려가 필요하다.