Hi everyone!
Today I'd like to write about the so-called Grundy numbers, or nimbers. I will start by providing a formal recap on the Sprague-Grundy theorem and then will advance to the topic that is rarely covered in competitive programming resources, that is I will write about nimber product and its meaning to the game theory.
I was asked to add the following to the blog: THANK SIR MASTER Adam_GS FOR GREAT AND VALUABLE REVIEW SIR
Prerequisites
Familiarity with the following concepts:
- Basic set theory notion: union, cartesian product and symmetric difference of sets, set of all subsets denoted as $$$2^A$$$, etc;
- Groups and fields: definitions, basic facts, most well-known examples (e.g. $$$\mathbb R$$$, $$$\mathbb Z_p$$$);
- Familiarity with the xor operation and its properties;
- Notion of equivalence relations.
Familiarity with formal computational models (e.g. deterministic finite automata) is not required, but would be helpful.
Although the nimbers are typically constructed on top of ordinal numbers and transfinite nim, I will try to stick with natural numbers and classic nim. You may familiarize yourself with transfinite nim in e.g. this article by emorgan.