About this question

Sprague-Grundy Theorem Application

Hard · Game Theory & Logic · Quant Trader interview question · game-theory, sprague-grundy, nim, combinatorial-game-theory

You are analyzing a combinatorial game played between two players. The game is impartial, meaning both players have the same moves available from any given position. The game is also finite, meaning it must eventually end. The Sprague-Grundy theorem states that every impartial game is equivalent to a Nim heap of a certain size. Consider a game composed of several independent subgames played simultaneously. On their turn, a player chooses one subgame and makes a valid move in it. The game ends wh