What is a combinatorial game?
2. What is a combinatorial game?
The diagram above shows a Slither position on a 3x5 board. The next player has three legal moves: from the left hand endpoint of the path add a down segment in the vertical position, or from the right hand endpoint of the path add a segment in the vertical position up or down. Playing Slither on a rectangular array of dots is an appealing game, but one can generalize the game to play on any graph, where each player tries to continue to create a path using edges that are in the graph. (Thought of this way, Slither as described above is played on the m x n grid graph.) Slither was introduced by David Silverman and like many combinatorial games was treated by Martin Gardner in one of the columns which he used to write for Scientific American and which serve as the basis for many of his books. At the time that Gardner wrote about the game it was not solved, but - partly due to his column - eventually William Anderson, going beyond work of Ronald Read, developed a solution to a generalized version of Slither based on the concept of a matching in a graph.
Given two positive integers, a and b, a positive linear combination of a and b is a number Z = xa + yb where x and y are positive integers. For example, some positive linear combinations of 5 and 9 are 14, 19, 23, and 24. The greatest common divisor of a and b is the largest integer which divides both a and b. The greatest common divisor of a and b is denoted gcd(a, b). Gcd (5, 9) = 1. Sylvester looked at the question of finding the largest multiple of d = gcd(a, b) which is not a positive linear combination of a and b. For example, for 5 and 9, the gcd of the numbers is 1 and the largest multiple of 1 not expressible as a positive linear combination of 5 and 9 is 31. (Check for yourself that 32 is 3(9) + 5 and all integers larger than 32 can be expressed in the form 5x + 9y.) Similarly, given 10 and 14, 116 is the largest multiple of 2 (the gcd of 10 and 14) which can not be expressed in the form 10x + 14y.
Welcome to the
These web essays are designed for those who have already discovered the joys of mathematics as well as for those who may be uncomfortable with mathematics.
Search Feature Column
Feature Column at a glance