To recap from the newsletter:
You are eating a special candy bar. You and a friend each take turns eating squares of blue, pink, and green candy starting from the left and moving right. You can bite off as many squares as you want, so long as they’re all the same color of candy. So, for example, your first move could be to bite off 1, 2, 3, or 4 squares. The winner is the person who eats the green square of candy (which is extra delicious!).
Start by playing around with it and learning how it works. Then, start asking yourself some questions. Can you figure out how to win the game every time you play? Do you want to go first or second to try to win? Can you figure out how to find a winning strategy even if we changed the board you’re playing on?
The Solution
If you start from the beginning, this problem is a mess: there are lots of possibilities to consider. In fact, in our weekend class “Entry to Abstract Math,” this problem was used specifically to introduce the idea of working backwards from the end. Once you have that insight, it becomes quite easy!
Of course, immediately before the final bite, this will be what remains of the candy bar:
You want your opponent to leave you with just that green square. How can you guarantee that? Well, if your opponent is faced with this board, then they have no choice but to leave you with that delicious final square!
Now, if your goal is to leave your opponent with this board, then you want to eat the square right before it, so we’ll put a little bite symbol on the squares you should bite.
To make sure you have the chance to bite that square, you must leave your opponent with just one square before it so they have no choice but to leave you with this configuration:
Which means you want to bite the square right before it:
This time, though, to make sure you can bite that marked pink bite, you need your opponent to leave you with all three pink squares. Otherwise, your opponent could bite to the pink bite and leave you in a losing position!
So how are you guaranteed to get all three pink squares? Simple, you must leave your opponent with just the single square before the pink region:
To guarantee that, you need to bite immediately to the left of that blue square:
If you want to be guaranteed that bite, your opponent must leave you with both pink squares. Otherwise, they could eat both! So you must leave them with just the one square before:
Which means you must bite the square immediately before it, which you can do on the first move:
Thus, the winning strategy is to go first, and bite up to each mark on your turn. If you go first, you will always be able to bite up to a mark (and your opponent will not!)
In addition to teaching about working backwards, this problem helps to introduce the ideas behind combinatorial game theory. In combinatorial game theory, not just can you analyze winning positions in games and develop winning strategies, but you can also develop a theory that lets you assign to each game a certain value that encodes how it works. These values (they’re not quite numbers) can be added together, and in fact, games can be added together as well in a compatible way!
In other words, this problem, which is already fun, is just the beginning!
—
Thanks to Mira Bernstein for creating and sharing this problem.