Recursive Patterns in the Chocolate Game Tomoro Okubo, Yuzuri Kashiwagi, Nobumitsu Niida Abstract We study the recursive structure of P-positions in the chocolate game C m , m C_{m,m} , an impartial game played on an m × m m\times m chocolate bar. We show that the set of P-positions exhibits self-similar patterns that can be described and enumerated recursively. We further establish a correspondence between these patterns and the cross-sections of a three-dimensional Sierpiński octahedron. Finally, we show that the P-positions can be generated by a second-order cellular automaton, analogous to the one-dimensional Rule-60 automaton. Our results reveal deep connections between combinatorial games, fractal geometry, and discrete dynamical systems. 1 Introduction This paper explores the structural properties of P -positions in the chocolate game C_{m,n} , an impartial game played on a rectangular bar. While Nim-like games are typically studied through algebraic means, we show that C_{m,m} admits a rich geometric and computational description. Specifically, we prove that the P -positions of C_{m,m} exhibit a self-similar pattern equivalent to cross-sections of the Sierpiński octahedron. Furthermore, we show that this pattern emerges from a second-order cellular automaton related to Wolfram’s Rule-60. By connecting game theory with fractal geometry and cellular automata, we provide both a recursive enumeration and a novel visualization of winning strategies. The structure of the paper is as follows: Section 2 reviews the basics of the chocolate game. Sections 3, 4, and 5 present our main results on P-positions, self-similarity, and cellular automata, followed by a discussion of future directions. 2 Chocolate Game and P-Positions Definition 2.1 . Let m,n be positive integers. The chocolate game C_{m,n} is a two-player impartial game defined as follows. The game is played on an m\times n rectangular chocolate bar divided into unit square cells, exactly one of which is poisoned. The players alternately perform the following move: • Break the chocolate bar along grid lines into two rectangular pieces, eat one piece, and give the other piece to the opponent. • If the chocolate bar cannot be broken, the player must eat it. The player who eats the poisoned cell loses. The position of the poisoned cell is assumed to be visible to both players. We assume that a player always avoids eating the poisoned cell whenever a legal move allows this. The terminal position of the game is defined to be the position in which a 1\times 1 chocolate bar is passed to a player and no further move is possible. Definition 2.2 . For the game C_{m,n} , define B_{m,n}=\{(i,j)\in\mathbb{Z}^{2}\mid 1\leq i\leq m,\ 1\leq j\leq n\}, and call B_{m,n} the board of C_{m,n} . Elements of B_{m,n} are called cells . A cell corresponding to a poisoned position for which the second player has a winning strategy is called a P-position . Let P_{m,n}\subset B_{m,n} denote the set of all P-positions. We define the pattern of P_{m,n} as the set R_{m,n}=\bigl\{(i-x,j-y)\in\mathbb{R}^{2}\mid 0\leq x\leq 1,\ 0\leq y\leq 1,\ (i,j)\in P_{m,n}\bigr\}, which gives a geometric visualization of P_{m,n} (see Figure 1 ). For a cell (i,j)\in B_{m,n} , we define its cell value by (i-1)\oplus(j-1)\oplus(m-i)\oplus(n-j), where \oplus denotes the bitwise exclusive OR (xor) of integers. In the square case m=n , define v_{m}(i,j)=\begin{cases}0,&\text{if }(i-1)\oplus(j-1)\oplus(m-i)\oplus(m-j)=0,\\ 1,&\text{otherwise}.\end{cases} Finally, for a subset A\subset\mathbb{R}^{2} and a real number r , we write rA=\{(rx,ry)\mid(x,y)\in A\}. Figure 1: The scaled pattern \frac{1}{m}R_{m,m} The following theorem is a well-known criterion for P-positions in the game of four-pile Nim. A proof can be found, for example, in [ 3 ] . Here we state and prove the result in the context of the square chocolate game C_{m,m} . Theorem 2.3 . For the chocolate game C_{m,m} , a cell (i,j) is a P-position if and only if (i-1)\oplus(j-1)\oplus(m-i)\oplus(m-j)=0. Proof. Let (i,j) be the cell corresponding to the poisoned position. A single move of breaking the chocolate can be regarded as choosing one of the four nonzero integers i-1,\quad j-1,\quad m-i,\quad m-j, and decreasing it by a positive integer so that it remains nonnegative. By symmetry, it suffices to consider the case in which i-1 is decreased. Set X=(i-1)\oplus(j-1)\oplus(m-i)\oplus(m-j). Suppose that one move transforms the position into Y=(i-\alpha)\oplus(j-1)\oplus(m-i)\oplus(m-j),\qquad 2\leq\alpha\leq i. Using the associativity and commutativity of \oplus together with (i-1)\oplus(i-1)=0 , we obtain Y=X\oplus(i-1)\oplus(i-\alpha). We claim that the following two statements hold: (1) If X=0 , then Y\neq 0 for any legal move. (2) If X\neq 0 , then there exists a legal move such that Y=0 . For (1), note that (i-1)\oplus(i-\alpha)\neq 0 , which implies Y\neq 0 . To prove (2), write X in binary form and let 2^{p} be the highest power of 2 appearing in X . If the 2^{p} -digit of i-1 is 1 , then X\oplus(i-1)<(i-1), and hence we can choose \alpha so that i-\alpha=X\oplus(i-1), which yields Y=0 . The same argument applies if the 2^{p} -digit is 1 in j-1 , m-i , or m-j . The terminal position is a P-position and satisfies X=0 . Since conditions (1) and (2) characterize the recursive structure of the game, it follows that a position is a P-position if and only if X=0 . ∎ 3 Recursive Structure of P-Positions Proposition 3.1 . The pattern R_{m,m} is symmetric with respect to the horizontal and vertical axes, and also with respect to the diagonal. More precisely, for any cell (i,j) , the cells (i,j),\ (i,m-j+1),\ (m-i+1,j),\ (j,i) are either all P-positions or all non-P-positions. Proof. The cell values of all four cells coincide and are equal to (i-1)\oplus(j-1)\oplus(m-i)\oplus(m-j). The claim therefore follows from Theorem 2.3 . ∎ Proposition 3.2 . In the chocolate game C_{m,m} , all cells on the two diagonals are P-positions. That is, for any integer 1\leq k\leq m , the cells (k,k) and (k,m+1-k) are P-positions. Proof. For these cells, the corresponding cell value satisfies (k-1)\oplus(k-1)\oplus(m-k)\oplus(m-k)=0. The assertion follows again from Theorem 2.3 . ∎ Theorem 3.3 . For any positive integer m , R_{2m,2m}=2R_{m,m}. In particular, R_{m,m} and R_{2m,2m} are similar figures. Proof. It suffices to show that v_{2m}(2i,2j)=v_{2m}(2i-1,2j)=v_{2m}(2i,2j-1)=v_{2m}(2i-1,2j-1)=v_{m}(i,j) for all 1\leq i,j\leq m . Using binary representations, the exclusive OR operation satisfies \displaystyle 2a\oplus 2b \displaystyle=2(a\oplus b), \displaystyle(2a+1)\oplus(2b+1) \displaystyle=2(a\oplus b). We compute \displaystyle(2i-2)\oplus(2j-2)\oplus(2m-2i+1)\oplus(2m-2j+1) \displaystyle=2(i-1)\oplus 2(j-1)\oplus\{2(m-i)+1\}\oplus\{2(m-j)+1\} \displaystyle=2\bigl((i-1)\oplus(j-1)\oplus(m-i)\oplus(m-j)\bigr), which implies v_{2m}(2i-1,2j-1)=v_{m}(i,j) . Similarly, \displaystyle(2i-1)\oplus(2j-1)\oplus(2m-2i)\oplus(2m-2j) \displaystyle=\{2(i-1)+1\}\oplus\{2(j-1)+1\}\oplus 2(m-i)\oplus 2(m-j) \displaystyle=2\bigl((i-1)\oplus(j-1)\oplus(m-i)\oplus(m-j)\bigr), so that v_{2m}(2i,2j)=v_{m}(i,j) . The remaining two cases, v_{2m}(2i-1,2j) and v_{2m}(2i,2j-1) , are treated in the same way. Hence the claim follows. ∎ Theorem 3.4 . Let m be a positive integer and write its binary expansion as m=a_{0}+a_{1}2+a_{2}2^{2}+\cdots+a_{k}2^{k}+2^{k+1}. Define s=a_{0}+a_{1}2+a_{2}2^{2}+\cdots+a_{k}2^{k},\qquad t=2^{k+1}-s. Then the pattern R_{m,m} consists of four copies of R_{s,s} placed at the corners and one copy of R_{t,t} placed at the center. For example, if m=11=1011_{2} , then s=011_{2}=3 and t=101_{2}=5 . In this case, R_{11,11} consists of four copies of R_{3,3} at the corners and one copy of R_{5,5} in the center (see Figure 2 ). Figure 2: R_{3,3} , R_{5,5} , and R_{11,11} Proof. By symmetry (Proposition 3.1 ), it suffices to verify the following three cases. (1) If 1\leq i\leq s and 1\leq j\leq s , then since m=2^{k+1}+s , we have \displaystyle v_{m}(i,j) \displaystyle=(i-1)\oplus(j-1)\oplus(2^{k+1}+s-i)\oplus(2^{k+1}+s-j) \displaystyle=(i-1)\oplus(j-1)\oplus(s-i)\oplus(s-j) \displaystyle=v_{s}(i,j). (2) If s+1\leq i\leq 2^{k+1} and s+1\leq j\leq 2^{k+1} , then \displaystyle v_{m}(i,j) \displaystyle=(i-1)\oplus(j-1)\oplus(2s+t-i)\oplus(2s+t-j) \displaystyle=v_{t}(i-s,j-s). (3) If s+1\leq i\leq 2^{k+1} and 1\leq j\leq s , then v_{m}(i,j)=(i-1)\oplus(j-1)\oplus(2^{k+1}-(i-s))\oplus(2^{k+1}+s-j). Since i-s\geq 1 and s-j\geq 0 , notice that the terms 2^{k+1}-(i-s) and 2^{k+1}+s-j straddle a power of two. In particular, 2^{k+1}-(i-s)<2^{k+1},\quad 2^{k+1}+s-j\geq 2^{k+1}. This implies that the exclusive OR of these four terms cannot vanish, i.e., v_{m}(i,j)=(i-1)\oplus(2^{k+1}-i+s)\oplus(j-1)\oplus(2^{k+1}+s-j)\neq 0. Combining these cases proves the theorem. ∎ Propositions 3.1 and 3.2 , together with Theorems 3.3 and 3.4 , show that the set P_{m,m} can be determined recursively. 4 Enumeration of P-Positions In this section, we investigate the number of P-positions. Let g(m)=\#P_{m,m} denote the number of P-positions for the square chocolate game C_{m,m} . For a positive integer x , let u(x) denote the largest nonnegative integer such that 2^{u(x)} divides x . Lemma 4.1 . For any positive integer m , the following relations hold: \displaystyle g(2m) \displaystyle=4g(m), \displaystyle g(2m+1) \displaystyle=g(m)+g(m+1). Proof. The identity g(2m)=4g(m) follows immediately from Theorem 3.3 . We prove g(2m+1)=g(m)+g(m+1) . It suffices to show that v_{2m+1}(2i-1,2j-1)=v_{m+1}(i,j),\quad v_{2m+1}(2i,2j)=v_{m}(i,j), and v_{2m+1}(2i-1,2j)=v_{2m+1}(2i,2j-1)=1. First, \displaystyle(2i-2)\oplus(2j-2)\oplus(2m+1-2i+1)\oplus(2m+1-2j+1) \displaystyle=2\bigl((i-1)\oplus(j-1)\oplus(m+1-i)\oplus(m+1-j)\bigr), which implies v_{2m+1}(2i-1,2j-1)=v_{m+1}(i,j) . Next, \displaystyle(2i-1)\oplus(2j-1)\oplus(2m+1-2i)\oplus(2m+1-2j) \displaystyle=\{2(i-1)+1\}\oplus\{2(j-1)+1\}\oplus\{2(m-i)+1\}\oplus\{2(m-j)+1\} \displaystyle=2\bigl((i-1)\oplus(j-1)\oplus(m-i)\oplus(m-j)\bigr), so v_{2m+1}(2i,2j)=v_{m}(i,j) . Finally, \displaystyle(2i-2)\oplus(2j-1)\oplus(2m+1-2i+1)\oplus(2m+1-2j) \displaystyle=2(i-1)\oplus\{2(j-1)+1\}\oplus 2(m+1-i)\oplus\{2(m-j)+1\} \displaystyle=2\bigl((i-1)\oplus(j-1)\oplus(m+1-i)\oplus(m-j)\bigr). If m is even, then the least significant bit of (i-1)\oplus(m+1-i) is 0 , while that of (j-1)\oplus(m-j) is 1 . If m is odd, the situation is reversed. In either case, the resulting xor is nonzero, and hence v_{2m+1}(2i-1,2j)=1 . By the same argument, v_{2m+1}(2i,2j-1)=1 . Therefore g(2m+1)=g(m)+g(m+1) , completing the proof. ∎ Theorem 4.2 . For any positive integer n , \sum_{m=1}^{2^{\,n-1}}g(2m-1)=6^{\,n-1}. Proof. We prove the claim by induction on n . For n=1 , we have g(1)=1=6^{0} , so the statement holds. Assume that the assertion holds for all integers up to n=k . For integers x with 1\leq x<2^{k+1} , the number of integers satisfying u(x)=y is 2^{k-y} . Using Lemma 4.1 , we obtain \displaystyle\sum_{m=1}^{2^{k}-1}g(m) \displaystyle=\sum_{i=1}^{k}\sum_{j=1}^{2^{i-1}}g\bigl(2^{k-i}(2j-1)\bigr) \displaystyle=\sum_{i=1}^{k}\sum_{j=1}^{2^{i-1}}4^{k-i}g(2j-1) \displaystyle=\sum_{i=1}^{k}4^{k-i}6^{i-1} \displaystyle=4^{k-1}\sum_{i=1}^{k}\left(\frac{3}{2}\right)^{i-1} \displaystyle=2^{2k-1}\left(\left(\frac{3}{2}\right)^{k}-1\right) \displaystyle=2^{k-1}(3^{k}-2^{k}). Therefore, \displaystyle\sum_{m=1}^{2^{k}}g(2m-1) \displaystyle=g(1)+\sum_{m=1}^{2^{k}-1}g(2m+1) \displaystyle=g(1)+\sum_{m=1}^{2^{k}-1}\bigl(g(m)+g(m+1)\bigr) \displaystyle=2\sum_{m=1}^{2^{k}-1}g(m)+g(2^{k}) \displaystyle=2^{k}(3^{k}-2^{k})+2^{2k} \displaystyle=6^{k}. This completes the induction. ∎ Theorem 4.3 . For any positive integer n , \sum_{m=1}^{2^{n}}g(m)=\frac{4^{n}+6^{n}}{2}. Proof. By Theorem 4.2 , \displaystyle\sum_{m=1}^{2^{n}}g(m) \displaystyle=\sum_{m=1}^{2^{n}-1}g(m)+g(2^{n}) \displaystyle=2^{n-1}(3^{n}-2^{n})+2^{2n} \displaystyle=\frac{4^{n}+6^{n}}{2}. ∎ 5 Self-Similar Structure and Cellular Automata By integrating the results obtained so far, we observe that the patterns appearing in the chocolate game are similar to planar sections of a certain three-dimensional self-similar structure, which converges to a fractal in the limit defined below. Definition 5.1 (Sierpiński Octahedron of order n ) . Let us define a geometric operation T on a regular octahedron as follows: (1) Let O be the center of the octahedron. (2) For each face of the octahedron, consider the tetrahedron formed by the three midpoints of the edges of the face and the point O . (3) Remove all six such tetrahedra from the original octahedron. Applying operation T to a regular octahedron yields six smaller octahedra, each with half the edge length(see Figure 3 ). Figure 3: Operation T on a regular octahedron Starting from the regular octahedron with vertices (\pm 1,0,0),\ (0,\pm 1,0),\ (0,0,\pm 1), we iteratively apply the operation T . For each n\geq 0 , we denote by S_{n} the resulting figure consisting of 6^{n} regular octahedra of edge length \frac{\sqrt{2}}{2^{n}} , and call S_{n} the Sierpiński octahedron of order n . For integers m , we define the m -th horizontal section of S_{n} by H_{n,m}:=S_{n}\cap\left\{z=1-\frac{m}{2^{n}}\right\}. Theorem 5.2 . For 0u(b),\\ (a-1)\oplus(b-1)&\text{if }u(a)=u(b).\end{cases} In particular, the condition u(a)=u(b) is equivalent to a\oplus(b-1)=(a-1)\oplus b. Suppose that v_{n+1}(i+1,j+1)=i\oplus j\oplus(n-i)\oplus(n-j)=0. Reorder i,n-i as a,b so that u(a)\leq u(b) , and similarly reorder j,n-j as c,d with u(c)\leq u(d) . Then a+b=c+d=n and a\oplus b=c\oplus d . (1) If u(a)