Будем решать задачу от меньших чисел к большим. Зададим несколько определений:
Выигрышная позиция - позиция из которой можно попасть в проигрышную позицию.
Проигрышная позиция - позиция из которой можно попасть только в выигрышную позицию.
Позиции 1,2 - выигрышные(мы ходим и выигрываем).
Позиция 3 - проигрышная(мы можем попасть только в выигрышную позицию).
Продолжая аналогичные рассуждения получим, что позиции кратные 3-ём проигрышные, а все остальные - выигрышные(при n > 999 добавтся условие, что мы можем забирать из кучи 1000 камней, но (1000 mod 3) = 1).