How are these three things related? Why are these things related? What are puppies doing at Skyline? And where are the kittens?
Last Tuesday Paul Zeitz led his “Puppies and Kittens” math circle lesson. Puppies and Kittens is a variation of the Nim game also called “take away”. Most of you know it. Puppies and kittens distinguishes itself from Nim by having two piles rather than one. This makes the game becomes much more complex.
Paul Zeitz explains how to beat everyone at this game.
Paul starts by challenging students to play him and letting us know that he is going to beat us every time. And he does. And then promises that we will all be able to beat even those guys that play chess for money in SF. But before he leads us to a method of mapping out the puppies and kittens game, we begin with a simpler version of take-away. (This is a commonly used problem-solving strategy — work with a smaller problem first).
The first version of take-away we play is with 16 hypothetical pennies. We are allowed to take away 1 to 4 pennies each turn, and the last person to make a legal move wins. We play this for a while, and begin exploring strategies. Some people have a few ideas, but no one yet describes a strategy that works with any number of pennies. Paul suggests that we start with even a simpler problem: what is the winning strategy with 1 penny? 2 pennies? Three pennies? Four? Five? Ah-ha, with 5 pennies you can win, that is if you go second.
You can represent this strategy on a number line. The number circled in blue is the Poisoned position.
From there your opponent cannot stop you from winning. But how can you be sure that you leave your opponent with 5 coins? She must leave you with 6, 7, 8, or 9 coins, you will take away whatever is needed to leave her with 5, then you win.
Turns out as long as you leave your opponent with a multiple of 5, you will always win.
Now on to Puppies and Kittens. The rules are you can take away any number of puppies, or you can take away any number of kittens, or you can take away equal numbers of both. Start with 12 puppies and 16 kittens.
It quickly becomes clear that if you leave your opponent with 2 of one baby animal and one of the other, you win. But how can you make sure you do that?
Now it gets really fun! Paul creates a graph with one axis as the number of puppies, and the other the number of kittens. He circles the Poison position we know of either 2 puppies and one kitten, or two kittens and one puppy. All positions one move to finish
are crossed out. Then all moves to the Poison position are crossed out — you don’t want your opponent to be able to get there. An interesting symmetry takes place. And quickly you can see where the next Poison position is. Here is my quick and rather poor sketch.
I hope this gives you an idea of how we can use graphs to see winning strategies. Try it yourself! See how far you can go.
Where does the pizza fit in?
Four Mathematical Games
A discussion of winning strategies and graphs:
Winning at Puppies and Kittens
There is a relationship between the Golden Ration and winning strategies:
Puppies and Kittens and the Golden Ratio