Back

Math and Logic

Cookies and Cupcakes

For most games, identifying the perfect move is too difficult to do in practice. Chess, for example, has too many possible moves for even the fastest computer to solve it completely (so far), but many chess programs do have the ability to play the game perfectly when there are only a few pieces left on the board.

Today's problem involves a game, and it just might be possible that this game can be solved perfectly. Keep reading to see some examples of how to approach games like this, or jump ahead straight to today's challenge.

One mathematical game is called Nim. It works like this:

  • There are several heaps, each containing several stones.
  • Taking turns, each player must remove one or more stones from a single heap.
  • The last player to remove a stone loses.

Let's look at a very simple version of Nim: two heaps, each with 22 stones. What are the possible first moves? Since the piles are equal, we can treat taking stones from the left and right as if they are the same move.

Let's look at one possible first move. Try removing just a single stone.

If you do that, your opponent can pick up two stones, leaving you with the last stone. That's not good. Let's try a different move: let's remove both stones from a heap on the first move.

Uh oh. This move also makes it easy for your opponent to win. There's no good option for the first move!

If you want to win a game of Nim that starts with two heaps of two stones each, the best move is to make your opponent go first! No matter what they do, you will be able to win.


Let's look at another mathematical game: "2121". It's like Nim in some ways, and different in others. The rules are as follows:

  • The first player must say "11".
  • After that, players take turns adding to the number. They may add any value from 11 to 3.3.
  • The first player to say or exceed 2121 loses.

What is the optimal strategy for this game? Who will win if both players play perfectly?

One approach that can be helpful for thinking about problems like this is to start from the end. What is the winning move in this game? In this game, if someone says 20,20, then their opponent is forced to say 2121 and lose, so getting to be the one who says 2020 is a winning move. How can we get there?

If we say 17,18,17, 18, or 19,19, then our opponent will have the opportunity to say 2020 and we will lose, but if we say 16,16, then no matter what our opponent says, we'll get to say 2020 next. Since 2020 is a winning move, so is 16.16.

In fact, we can continue to reason our way backwards from here: 16,12,8,16, 12, 8, and then 4.4. If the second player picks 44 as their first move and then chooses multiples of 44 through the entire game, they are guaranteed to win.

Can you use careful reasoning to solve the game below?

Today's Challenge

In this game, there are 66 cookies and 88 cupcakes. The game is played according to these rules:

  • Taking turns, each player must take one or more cookies and/or cupcakes. There are three options.
    1. Take one or more cookies only.
    2. Take one or more cupcakes only.
    3. Take the same number of cookies and cupcakes.
  • The player who makes it so that there are 00 cookies and 00 cupcakes left wins.

Assuming both players play perfectly, who will win the game?

×

Problem Loading...

Note Loading...

Set Loading...