Optimisation and game theory · Maths EE idea · Solid

Winning at Nim

A research question to start from

Why does the binary 'nim-sum' decide who wins Nim, and how does the Sprague–Grundy theory extend this to other games?

A starting point, not your question: change the case, the comparison or the limit until it is yours. The research-question builder helps you check it.

Why it works as a maths EE

A complete winning strategy you prove, then generalise.

Mathematics you would need

Binary representation
XOR (nim-sum)
Winning and losing positions
Mex and Grundy values

Much of this goes beyond the DP course. That is expected in a maths EE, but you must understand and explain everything you use.

One possible line of attack

Prove the nim-sum strategy.
Compute Grundy values for a subtraction game.
Use them to analyse a sum of games.

Scope and difficulty

Solid. Solid.

Pitfalls

Playing games instead of proving.
Grundy values without meaning.

Where to start reading

Search a library catalogue or a university's open lecture notes for: Bouton's theorem Nim proof; Sprague-Grundy theorem. Prefer textbooks, lecture notes and journal articles to a single website, and cite everything you use (how to reference a maths EE).

Make it your EE

Plan this EEOpens the free EE planner with this question as a starting point. Sharpen the questionSix quick checks for a focused research question. Self-check a draftCheck a section against each criterion, free.