Phase I-A: Games against the computer
One thread at the beginning of the course is number theory. My immediate objective is to get students thinking and writing with a degree of mathematical precision. This is encouraged through two kinds of activities early in the course, one of which is described here and one in the next section.
- Should you go first or second?
- Every time, or are does it depend on the starting position of the game?
- Does your strategy cover every possible situation, even if your opponent plays irrationally?
They then make a great deal of progress at tightening up their arguments, which take on the character of mathematical proof.
The first Phase IA game is Basic Nim. In this game there are two piles of stones, and the players take turns removing any number of stones from one or the other of the piles. The object is to be the player who removes the last stone. After playing the game a couple of times against the computer, students quickly get the idea that on every turn you want to leave the same number of stones in each pile. This allows introduction of the notion of an "invariant" of the game, namely, the difference between the sizes of the piles. The simplest way to describe the winning strategy is
- go first if the invariant is nonzero at the start, otherwise go second,
- on each move, take enough stones from the larger pile to make the piles equal.
A good exercise is to write a paragraph that explains why this strategy always wins.
Later in the semester, students can try their hand at Extreme Nim. In this version, there are three piles of stones rather than two, and the strategy for winning is more complicated. The invariant this time has to do with the binary representations of the numbers of stones in each pile. A winning position is one where the sum of the i-th binary digits of the sizes of the three piles is even for all i. I use this game in conjunction with the unit on coding and data transmission schemes, since it is an example where binary arithmetic comes up unexpectedly but naturally. I also encourage students to collaborate on trying to find a strategy for this game, since it is difficult.
Other, simpler games are the December 31 game and the 20 game. In December 31, the date begins as January 1, and players alternate either increasing the month or the day of the month. (So from January 1, legal moves would include April 1 and January 12.) The winner is the player who says "December 31." After playing the computer a few times, most students realize that the invariantof the game is the day minus the number of the month, and the winning positions have the invariant equal to 19 -- as it is at the end of the game.
The second such game is 20, which starts at 0, and the players alternately increase the number by either 1 or 2. So the invariant is the remainder mod 3, and a winning position is one that leaves remainder 2 on division by three. (We study modular arithmetic when we look at data encryption.) The 21 variation of this game is interesting because the correct strategy here is to go second rather than first.
In a more mathematical light, students play a game of trying to guess an unknown weight on a balance, which paves the way for our study of the Euclidean algorithm. Many other algorithms encountered in the course are similarly illustrated using this kind of game, and the students become quite adept at explaining in great detail (and with great precision!) how they beat the games, and thus the idea of an algorithm is made plainer to them.