A Bitter Chocolate Problem That Satisfies an Inequality

In a piece of chocolate the green parts are sweet and the red part is very bitter. This game is played by two players taking turns. Each player breaks the chocolate (in a straight line along the grooves) and eats the piece broken off. The player to leave the opponent with the single bitter part is the winner.


  • [Snapshot]
  • [Snapshot]
  • [Snapshot]


You can cut the chocolate in three ways: (1) from the upper right to the lower left, (2) horizontally, or (3) from the upper left to the lower right. Therefore it is appropriate to represent the game state with three non-negative integers , which are shown in the upper-left corner. It is easy to see that the coordinates satisfy the inequality .
We define two important states: (a) states, from which we can force a win, as long as we play correctly at every stage, and (b) states, from which we will lose however well we play if our opponent plays correctly.
One of the most important tasks of chocolate games is to find all the and states of a game. Usually the number of states is small.
In this chocolate game it is easy to find states, since there are formulas for them:
1. The position is an state if and only if .
2. The position is an state if and only if , where is the bitwise exclusive or operation (the same as BitXor in Mathematica).
The list of states makes a beautiful 3D graph. See "graph 1" in the Demonstration. If you rotate the graph around the axis by and project the list onto the plane made by the axis and the axis, then you get a Sierpinski gasket; see "graph 2".
Once we know the formula for states, the strategy to win is clear. Suppose that you have a state; you can choose a move that leads to an state. After that any move by your opponent leads to a state, and you can always move to an state. Finally you reach .
If you have to play with an state, you can only win if your opponent makes a mistake.
See [1, 2] by the authors for a proof of the formula.
[1] M. Naito, T. Yamauchi, H. Matsui, T. Inoue, Y. Tomari, K. Nishimura, T. Nakaoka, D. Minematsu, and R. Miyadera, "Combinatorial Games and Beautiful Graphs Produced by Them," Visual Mathematics, 11(3), 2009. http://vismath.tripod.com/pap.htm# n114.
[2] T. Yamauchi, T. Inoue, and Y. Tomari, "Variants of the Game of Nim That Have Inequalities as Conditions," Rose–Hulman Undergraduate Mathematics Journal, 10(2), 2009. http://www.rose-hulman.edu/mathjournal/v10n2.php.
    • Share:

Embed Interactive Demonstration New!

Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details »

Files require Wolfram CDF Player or Mathematica.

Mathematica »
The #1 tool for creating Demonstrations
and anything technical.
Wolfram|Alpha »
Explore anything with the first
computational knowledge engine.
MathWorld »
The web's most extensive
mathematics resource.
Course Assistant Apps »
An app for every course—
right in the palm of your hand.
Wolfram Blog »
Read our views on math,
science, and technology.
Computable Document Format »
The format that makes Demonstrations
(and any information) easy to share and
interact with.
STEM Initiative »
Programs & resources for
educators, schools & students.
Computerbasedmath.org »
Join the initiative for modernizing
math education.
Step-by-Step Solutions »
Walk through homework problems one step at a time, with hints to help along the way.
Wolfram Problem Generator »
Unlimited random practice problems and answers with built-in step-by-step solutions. Practice online or make a printable study sheet.
Wolfram Language »
Knowledge-based programming for everyone.
Powered by Wolfram Mathematica © 2017 Wolfram Demonstrations Project & Contributors  |  Terms of Use  |  Privacy Policy  |  RSS Give us your feedback
Note: To run this Demonstration you need Mathematica 7+ or the free Mathematica Player 7EX
Download or upgrade to Mathematica Player 7EX
I already have Mathematica Player or Mathematica 7+