Another chocolate problem that is a variant of the game of Nim

Example 2.1. This time we are gong to use the chocolate in Graph 2.1. This problem has been introduced by the authors.

Graph 2.1. $\includegraphics[height=3cm,clip]{sakaguchichocob1.eps}$

The problem of Graph 1.2 is different from the problem of Graph 2.1. In Graph 2.1 you can cut the chocolate in 6 ways, so it is appropriate to represent it with 6 non-negative integers $\{x_1,x_2,x_3,x_4,x_5,x_6\}$ . We represent the position in Graph 2.1 with {2,1,2,1,2,1}.

Note that these 6 coordinates are not independent, i.e., in some cases you cannot subtract a natural number from one of 6 coordinates without affecting other coordinates.
It is clear that we have 6 inequalities between these 6 coordinates.

$\displaystyle x_1 \leq x_2+ x_6, x_2 \leq x_1+ x_3+1, x_3 \leq x_2+ x_4 ,$
$\displaystyle x_4 \leq x_3+ x_5+1, x_5 \leq x_4+ x_6, x_6 \leq x_5+ x_1.$

We can study chocolates of any size if we use arbitrary non-negative integers that satisfy these 6 inequalities.

Example 2.2. Here we are going to calculate P-positions of this game. Since there is no method to find all the P-position theoretically, we are going to find them by calculation of Mathematica. Because this game has a complicated structure, the Mathematica program for this game is a little bit complicated.

Clear[ss, al, allcases];
ss = 1; al = 
Flatten[Table[{a,b,c,d,e,f},{a,0,ss + 2},{b,0,ss},{c,0, 
ss + 2},{d,0,ss},{e,0,ss + 2},{f,0,ss}],5];
allcases = 
Select[al,#[[1]]+#[[3]]+1>= #[[2]]&&#[[2]]+#[[4]]>=#[[
3]] && #[[3]]+#[[5]]+1>=#[[4]]&&#[[4]]+#[[6]]>=#[[
5]]&&#[[5]]+#[[1]]+1>=#[[6]]&&#[[6]]+#[[2]]>=#[[
1]]&];(*allcases are the set of all possible shapes of the 
chocolate.  Note that the above inequations are the necessary 
and sufficient condtions for {a,b,c,d,e,f} to be a possible 
shape of the cholocate.*)
num=Length[allcases];
(*num is the number of all the cases*)
x1=allcases[[num]];
(*x1 is the case with which we start the fame*)
pos[x_List,y_List]:=
Block[{s,t,u,v},u=x;v=y;t=Apply[Plus,v];
s=Position[v,t][[1,1]];
u[[s]]=u[[s]]-t;{Min[u[[6]]+u[[2]],u[[1]]],
Min[u[[1]]+u[[3]]+1,u[[2]]],
Min[u[[2]]+u[[4]],u[[3]]],
Min[u[[3]]+u[[5]]+1,u[[4]]],
Min[u[[4]]+u[[6]],u[[5]]],
Min[u[[5]]+u[[1]]+1,u[[6]]]}];
(*pos[x,y]returns the case that you will get after removing
 y from x. 
For example let x={1,2,1,2,1,2} and y={1,0,0,0,0,0},
then pos[x,y] denotes the case you get after removing one 
from the 1st coodinate of x; that is {1,1,2,1,2,1}*)
Clear[move,z,p,t1,t2,t3,t4,t5,t6];
move[z_]:=Block[{p},p=z;
Union[Table[pos[p,{t1,0,0,0,0,0}],{t1,1,p[[1]]}],
Table[pos[p,{0,t2,0,0,0,0}],{t2,1,p[[2]]}],
Table[pos[p,{0,0,t3,0,0,0}],{t3,1,p[[3]]}],
Table[pos[p,{0,0,0,t4,0,0}],{t4,1,p[[4]]}],
Table[pos[p,{0,0,0,0,t5,0}],{t5,1,p[[5]]}],
Table[pos[p,{0,0,0,0,0,t6}],{t6,1,p[[6]]}]
]
]
(*move[x] returns all the cases you can get from x when 
you remove a part of x*)
Mex[L_]:=Min[Complement[Range[0,Length[L]],L]];
Gr[z_]:=Gr[z]=Mex[Map[Gr,move[z]]];

By the Mathematica program in Example 2.2 we can find all the P-positions of the chocolate problem of Example 2.1 . (For this scale of problem you can find all the P-position only with pen and paper.) Graph 2.2 contains all the P-positions. All the other positions are N-position. As you can see easily the original position in Graph 2.1 is an N-position, because you cannot find the original position in Graph 2.2. Therefore you are sure to win if you start the game as the first player.

Example 2.3. Here we are going to study how to win the game as the next player. From the original position you can move to the 18th, 19th or 20th positions in Graph 2.2. Note that all of them are P-positions. Suppose that you chose the 18th position. Then your opponent will choose one of the 8 positions in Graph 2.3. Since they do not belong to the list of positions in Graph 2.2, all of positions of Graph 2.3 are N-positions.

Graph 2.3. $\includegraphics[height=4cm,clip]{sakaguchichoco3.eps}$

If the opponent chose the first position of Graph 2.3, then you can choose the 7th of Graph 2.2. Then your opponent choose one of the 4 positions in Graph 2.4. If the opponent choose the 1th or the 3rd position, you can take away the green part and win the game. If the opponent choose the 2nd or 4th position of Graph 2.4, you can move to the 3rd of Graph 2.2. After that the opponent will take the right or left green part, then you can take the remainning green part and win.

The stratedy is clear. If you start with the original position in Graph 2.1, then you have only to move to a P-position. By the next move your opponent will move to an N-position. From this position you have only to move to a P-position. By continuing this process you are sure to win.

Graph 2.4. $\includegraphics[height=2cm,clip]{sakaguchichoco4.eps}$

Remark 2.1. If you are going to play this game and want to memorize all the P-positions, it is better to make the list of P-positions smaller. In Graph 2.2 the 2nd, 3rd and 4th positions are essentially the same, and the 6th and 8th positions are essentially the same, too. By considering this we can choose 7 positions out of 20 positions in Graph 2.2, and we can make Graph 2.5.

Graph 2.5.