teacher
Sign in

Game Theory, Nim and Grundy Numbers

Decide who wins a two-player game with perfect play, using win/lose states, the XOR rule of Nim, and Grundy numbers for sums of games.

45 minCF 1400–22005 interactive11 problems

The problem

Two players take turns making moves in a game with no luck and no hidden information. Both play perfectly. In normal play the player who cannot move loses. Who wins from the starting position?

Games where both players have the same moves from every position are called impartial. Chess is not impartial (each player moves only their own pieces). Taking stones from piles is.

1 of 9