돌 나누기 게임

문제

$N$개의 돌로 이루어진 더미 하나가 있다. 두 플레이어가 턴을 번갈아 가며 다음 행동을 한다.

• 현재 더미 중 하나를 골라 크기가 서로 다른 두 더미로 나눈다. (예: 크기 5인 더미는 (1, 4) 또는 (2, 3)으로 나눌 수 있으나 (3, 2)는 (2, 3)과 같으므로 중복되지 않게 한다.)
• 더 이상 나눌 수 있는 더미가 없는 플레이어가 패배한다. (즉, 모든 더미의 크기가 1 또는 2가 되면 더 이상 나눌 수 없다.)

스프래그-그런디 정리(Sprague-Grundy Theorem)를 이용하여 선공 플레이어가 승리하는지 판별하라.