Some examples for calculating Grundy number

Here are some examples to show how to calculate Grundy numbers.

Example 5.3   We show the method to find the value of $X$ in Fig. 5.15 that is a table of Grundy numbers of the chocolate game with the inequality $y \leq z$ .
If we are to find the value $X = G1R(\{10,26\})$ that is in the green rectangle, by Lemma 5.1 we have only to find the smallest number that does not belong to $L1(\{10,26\})$

Figure 5.15  

By Definition 5.2 $L1(\{10,26\})$ can be separated into three parts
$L11(\{10,26\})$ , $L12(\{10,26\})$ and $L13(\{10,26\})$ .
The numbers of $L11(\{10,26\})$ are in blue rectangles.
$L11(\{10,26\}) = \{G1R(\{0,0\}),G1R(\{1,1\}),...,G1R(\{10,10\})\}$

$$= \{0,2,3,5,...,12,14,15\}.$$ (5.1)

The numbers of $L12(\{10,26\})$ are in red or white rectangles.
$L12(\{10,26\}) = \{G1R(\{10,11\}),G1R(\{10,12\}),...,G1R(\{10,25\})\}$ $= \{1,17,4,...,29,20\}$

$$=\{1,4,...,16\}$$ (5.2)

$$\cup \{18,20\}$$ (5.3)

$$\cup \{17,19,...,29\}.$$ (5.4)

The numbers of $L13(\{10,26\})$ are in yellow or white rectangles.
$L13(\{10,26\}) = \{G1R(\{0,26\}),G1R(\{1,26\}),...,G1R(\{9,26\})\}$ $=\{26,25,27,24,...,30,21\}$

$$=\{26,27,28,29,30\}$$ (5.5)

$$\cup \{25,24,23,22,21\}.$$ (5.6)

By (5.1) and (5.2) we have

$$L11(\{10,26\}) \cup L12(\{10,26\}) \supset \{0,1,2,3,...,16\}.$$ (5.7)

By (5.3) and (5.4) we have

$$L12(\{10,26\}) \supset \{17,18,19,20\}.$$ (5.8)

By (5.5) and (5.6)

$$L13(\{10,26\})=\{21,22,23,24,25,26,27,28,29,30\}.$$ (5.9)

By (5.4), (5.7), (5.8) and (5.9) we have $L1(\{10,26\}) = \{0,1,2,3,...,27,28,29,30\}$ , and $31$ is the smallest number that does not belong to $L1(\{10,26\})$ . Therefore $X=G1R(\{10,26\})=31$ .

Remark 5.1   In Fig. 5.15 the positions of $G1R(\{10,21\})$ and $G1R(\{12,25\})$ have important role. These Grundy numbers are in purple rectangles.
$G1R(\{12,25\})$ is the last term in the arithmetic sequence of common difference of 3 in the row when $z = 25$ , and $G1R(\{10,21\})$ is the last term in the arithmetic sequence of common difference of 3 in the column when $y = 10$ . Since these numbers are the last term of arithmetic sequence of common difference of 3, the calculation of $X = G1R(\{10,26\})$ is easy by the fact that $X = G1R(\{10,26\})$ is under Grundy number $G1R(\{10,21\})$ and it is on the right side of Grundy number $G1R(\{12,25\})$ .

Example 5.4   We show the method to find the value of $X$ in Fig. 5.16 that is a table of Grundy numbers of the chocolate game with the inequality $y \leq z$ .
To find the value of $X = G1R(\{11,26\})$ we have only to find the smallest number that does not belong to $L1(\{11,26\})$ .

Figure 5.16  

By Definition 5.2 $L11(\{11,26\}) = \{G1R(\{0,0\}),G1R(\{1,1\}),...,G1R(\{11,11\})\}$

$$= \{0,2,3,5,...,14,15,17\}.$$ (5.10)

$L12(\{\{11,26 \}) = \{G1R(\{11,12\}),G1R(\{11,13\}),...,G1R(\{11,25\})\}$
$= \{17,1,19,4,21,7,23,10,25,13,27,16,29,18,31\}$

$$=\{1,4,7,10,13,16,18\}$$ (5.11)

$$=\{19,21,23,25,27,29,31\}$$ (5.12)

$L13(\{\{11,26\}) = \{G1R(\{0,26\}),G1R(\{1,26\}),...,G1R(\{10,26\})\}$ $=\{26,25,27,24,28,23,29,22,30,21,31\}$

$$=\{26,27,28,29,30,31\}$$ (5.13)

$$\cup \{25,24,23,22,21\}.$$ (5.14)

By (5.10) and (5.11) we have $L11(\{11,26\}) \cup L12(\{11,26\})$ $\supset \{0,1,2,3,...,18\}$ .
By (5.13) and (5.14) all the numbers in $L13(\{11,26\})$ are bigger than $20$ .
By (5.12) we have $L12(\{11,26\}) \supset \{19,...\}.$ Note that the list {19,21,23,25,27,29,31} does not contain $20$ . Therefore we have $X=20$ . A very important fact is that the numbers in the list and the number $20$ have opposite parity. This fact play an important role when we prove predictions generally.

Example 5.5   We show the method to find the value of $X$ in Fig. 5.17 that is a table of Grundy numbers of the chocolate game with the inequality $y \leq z$ .
To find the value of $X = G1R(\{10,17\})$ we have only to find the smallest number that does not belong to $L1(\{10,17\})$

Figure 5.17  

Remark 5.2   Note that $X = G1R(\{10,17\})$ is in the midst of the the sequence $\{1,4,7,...,\}$ in the column for $y = 10$ , and this condition make this example different from Example 5.3 and Example 5.4.

$L11(\{10,17\})$ $=\{0,2,3,5,6,8,9,11,12,14,15\}$

$$= \{0,2,3,5,6,8,9\}$$ (5.15)

$$\cup \{11,12,14,15\}.$$ (5.16)

Clearly $L12(\{10,17\})$ $= \{1,17,4,19,7,21\}$

$$= \{1,4,7\}$$ (5.17)

$$\cup \{17,19,21\}.$$ (5.18)

$L13(\{10,17\})$ $=\{17,18,16,19,15,20,14,21,13,22\}$

$$= \{17,16,15,14,13\}$$ (5.19)

$$\cup \{18,19,20,21,22\}.$$ (5.20)

By (5.15) and (5.17) we have

$$L11(\{10,17\}) \cup L12(\{10,17\}) \supset \{0,1,2,3,4,5,6,7,8,9\}.$$ (5.21)

By (5.16), (5.18), (5.19) and (5.20) The lists $L11(\{10,17\})$ , $L12(\{10,17\})$ and $L13(\{10,17\})$ do not contain $10$ , and hence we have $X= G1R(\{10,17\}) =10$ .

Example 5.6   We show the method to find the value of $X$ in Fig. 5.18 that is a table of Grundy numbers of the chocolate game with the inequality $y \leq z$ .
To find the value of $X = G1R(\{13,19\})$ we have only to find the smallest number that does not belong to $L1(\{13,19\})$

Figure 5.18  

$L11(\{13,19\})$ $=\{0,2,3,5,6,8,9,11,12,14,15,17,18,20\}$

$$= \{0,2,3,5,6,8,9\}$$ (5.22)

$$\cup \{11,12,14,15,17,18,20\}.$$ (5.23)

Clearly $L12(\{13,19\})$

$$= \{1,4,7\}$$ (5.24)

$$\cup \{22,24\}.$$ (5.25)

By using Prediction 5.3 for $z=19$ and $y=0,1,...,12$
$L13(\{13,19\})$ $=\{19,20,18,21,17,22,16,23,15,24,13,25,10\}$

$$= \{19,18,17,16,15,13,10\}$$ (5.26)

$$\cup \{20,21,22,23,24,25\}.$$ (5.27)

By (5.22) and (5.24) we have

$$L11(\{13,19\}) \cup L12(\{13,19\}) \supset \{0,1,2,3,4,5,6,7,8,9\}.$$ (5.28)

By (5.26) and (5.27) we have $L13(\{13,19\})$

$$\supset \{10,13,15,16,17,18,19,20,21,22,23,24,25\}.$$ (5.29)

By using Prediction 5.3 for $z=19$ and $y=0,1,...,12$
we know that the sequence of (5.29) starts as an arithmetic sequence with common difference of $3$ whose length is $\lceil 19/4 \rceil = 5$ , and hence the last term of this arithmetic sequence is $1+3(5-1)=13$ . The next term in (5.29) is $15$ , and after that we have an arithmetic sequence with common difference of $1$ up until it reaches $25$ . Therefore by (5.23), (5.28) and (5.29) we have $L11(\{13,19\}) \cup L12(\{13,19\}) \cup L13(\{13,19\}) \supset \{0,1,2,3,4,5,6,...,25\}$ . It is clear that there is no $26$ in $L11(\{13,19\}) \cup L12(\{13,19\}) \cup L13(\{13,19\})$ , and hence we have $X= G1R(\{13,19\}) =26$ .