Can someone explain me grundy number as in how to construct it
i read about it on topcoders and other websites but was not able to understand the concept behind it and how to construct it
4 Likes
There is a certain amount of magic to Grundy numbers. Sometimes it is
useful to be able to apply some theory without thinking through the
proofs and explanation every time. So it is with Grundy numbers.
I’ll try to show some calculations with Grundy numbers. Perhaps that will provide enough motivation to make other explanations more understandable.
The game of Nim is played by two players. There are r piles of
counters, with n_1, n_2, ..., n_r counters in them. The players take
turns. In each turn a player chooses one of the non-empty piles of
counters, and removes one or more, possibly all, the counters from
that one pile. The first player to take a turn when all the piles are
empty loses.
The theory of Grundy numbers tells us that the Grundy number of a pile
of n counters is n. It also tells us that the Grundy number of
several piles of counters is given by the binary exclusive-or of the
Grundy numbers of the piles. For example:
Grundy number of two piles size 4 and 4 is zero.
Grundy number of three piles of size 4, 5 and 6 is 7,because the
binary exclusive-or of 100_2, 101_2, 110_2 is 111_2.
Further, a position in Nim is losing for the player about to have a
turn if and only if the corresponding Grundy number is zero. Examples
of losing positions are 1,2,3 and 3,5,6.
There is plenty of discussion of Nim on the internet, and the above
doesn’t really show much usefulness of Grundy numbers. But the key
piece of information is that Grundy number of several piles is given
by the binary exclusive-or of the Grundy numbers of the piles.
Let’s consider another game.
Suppose we have two players again, and r piles of counters. At each
turn a player chooses a pile with more then two counters, and splits
it into exactly two smaller piles. First player not able to move
because all piles have only 1 or 2 counters loses.
Let G(n) be the Grundy number of a pile of n counters. And write
G(n,m) as the Grundy number of two piles of n and m
counters respectively. Following the same sort of structure as in Nim, G(n,m) is
equal to the binary exclusive-or of G(m) and G(n).
We need another piece of notation and theory. Define the minimum
excluded value of a (finite) set of non-negative integers as the
smallest non-negative integer not in the set. If S is a set of
integers, we write this as {\bf mex}(S). For example
{\bf mex}(\{1,2,3\}) = 0, and
{\bf mex}(\{0,1,2\}) = 3, and
{\bf mex}(\{0,1,3,4\}) = 2.
We can now give a definition of a Grundy number: In any game, the
Grundy number of a position is equal to the minimum excluded value of
the set of Grundy numbers of the possible positions which can be reached in
one move.
Using this definition we can calculate the Grundy numbers of piles of n counters in our game,
There are no possible moves from a pile of one or two counters,
because the set of possible reachable positions is the empty set. Thus:
G(1) = {\bf mex}( {\it empty set} ) = 0
G(2) = {\bf mex}( {\it empty set} ) = 0
From a pile of 3 counters, there is just one possible move, resulting
in a pile of 2 counters and a pile on 1 counter:
G(3) = {\bf mex}( \{ G(1,2) \} = {\bf mex}( \{0\}) = 1
And continuing along the same lines:
G(4) = {\bf mex}\{ G(1,3), G(2,2) \}= {\bf mex}\{1,0\} = 2
G(5) = {\bf mex}\{ G(1,4), G(2,3) \}= {\bf mex}\{2,1\} = 0
and so on. You should find that the piles with Grundy numbers 0 are
1,2,5,13,21,31,.... This sequence can be found in OEIS.
9 Likes
“The theory of Grundy numbers tells us that the Grundy number of a pile of n counters is n” …when does this hold true…I mean in the above example clearly this fact is not reflected anywhere…or is it that it depends on the rules of the game being played ?
Thanks a lot @john_smith_3 your explanation cleared the picture just need to apply the concept in few question to realize it 
In the game of Nim, the Grundy number of a pile of n counters is n. (In the game discussed in more detail, this is not true.)
A proof for the game of Nim follows directly from the definition, using induction.
There are no possible moves from an empty pile of counters, so the Grundy number of an empty pile of counters is 0, which is the minimum excluded value of an empty set.
For a pile on n counters, the possible moves leave piles of 0, 1, 2, ..., or n-1 counters, which have Grundy numbers 0, 1, 2, ..., n-1. The minimum excluded value is n, so the Grundy number of a pile of n counters in Nim is n.
2 Likes
It is only when you are allowed to pick up any no of counters from a pile and throw it away. It does follow the definition - grundy nos consider the set of all the grundy nos whose state you can reach and then find the minimum non negative no not in that set.
somebody please upvote me , i have questions to ask
thank you
Here is a post on Grundy numbers and Sprague Grundy theorem
I hope it would be helpful to solve some game theory problems.
Link : https://cpbysucide.quora.com/Grundy-numbers-and-sprague-grundy-theorem-for-competitive-programming
Hi!
@john_smith_3 has already explained this concept well. I would like to point out a few video tutorials on this topic here:
Grundy Numbers - Playlist
Feel free to comments in case you have doubts or suggestions.
Cheers!
5 Likes