Winning Moves and Illuminating Mathematical Patterns
David Ginat · Mathematics and computer education · 2006
1. INTRODUCTION Co-primes game. Given a set of N (>20) consecutive integers {k, k+1, k+2, ... , k+N-1}, k> 1, two players remove the integers - one at a time - in alternating turns, until only two integers remain. If the two remaining integers are co-primes then the 1st player (who starts the game) wins; otherwise - the 2nd player wins. Would you like to be the 1st or the 2nd player, and how would you play in order to win? This simply stated game may be regarded as a recreational activity; but is it only recreational? We believe not. It may be useful as an attractive means for illuminating and elaborating mathematical patterns. The game involves integer patterns and invariant patterns, which are basic elements of discrete mathematics. An activity that involves such patterns may enhance students' recognition, utilization, and capitalization on mathematical characteristics. When the activity involves less routine challenges, such as games, students may be more enthusiastic. The objective of this paper is to offer an elaboration of simple, yet powerful, mathematical patterns through mathematical games. Mathematical games may serve as colorful instructional tools for teachers and textbooks, and may raise students' motivation and intuition [3]. Patterns are fundamental in mathematics and computer science. In the case of games, they may involve integer properties such as parity, primality, and divisibility, as well as invariant properties of repeated actions. Invariant properties are fundamental elements of algorithm design and analysis, and the primary means for proving computer programs correct [5, 7]. Thus, patterns reached during the development of game strategies may be beneficial for illuminating properties of numbers and algorithms. Both kinds of properties are essential at the fundamental levels of college mathematics and computer science. We present four simply stated, less familiar mathematical games. (We indicate the original references for two of the games. The original references for the other two games are not known to us.) In each of the following four sections, we gradually develop the winning strategy for each of the games. First, preliminary novice attempts are mentioned, and then instructive strategy developments are presented, through the illumination of underlying mathematical patterns. In the last section, we reflect on the illuminated patterns and the way they were reached. 2. CO-PRIMES We start with the Co-primes game mentioned in the introduction. In our experience, novices often attempt unfounded, heuristic strategies. Some try a winning strategy for the 1st player of reaching two prime numbers at the end of the game; others suggest a rule of removing, at each turn, the integer that has the maximal number of divisors. While these strategies may intuitively make sense, their correctness and simplicity are questionable. One should seek a sound, and preferably simple, strategy. At first glance, we may notice that when N (the initial number of integers) is odd, the 1st player has one extra turn. This may suggest seeking a winning strategy for the 1st player. The strategy may be based on an invariant pattern that will guarantee two remaining co-primes at the end of the game. * What may be an invariant pattern for an odd N that will yield two remaining co-primes? A relevant invariant pattern may be based on pairing all the game integers, except for one, in co-prime pairs. The 1st player will remove the unpaired integer at the beginning of the game, and the 1st player's response to each of the 2nd player's removals will be the removal of the co-prime paired with the 2nd player's removed integer. * Is there a simple co-primes scheme for a sequence of successive integers? Indeed, there is. Every two successive integers are co-primes. Thus, the 1st player may partition the line of the game integers into successive pairs of co-primes, and keep the following invariant: Co-primes Invariant, for odd N. …