Kayles
Kayles
The game of Kayles formally uses one or more rows of bowling pins. Each player may knock down either one pin alone or an adjacent pair of pins (and must knock down at least one evry time). We denote a file of n pins by Kn, and the sum of two rows of n e m pins by Kn+Km.
As an example, a file of five pins permits five distinct moves: moves that transform K5 in K4, K3, K2+K2, K3+K1 or K2+K1, depending on the player knocking over one or two pins and their being in the middle or at the end of the initial row. Kayles was sold as game at the beginning of the twentieth century in England and is an impartial game. It resembles Nim except for the eventual divisão of a pile into two piles. As before, each player may interfere with only one pile at a time. The values are those of an impartial subtraction game, *n. In Kayles, with one, two, three or four pins in a row, the first to play can always win. With five pins in a row, the moves are those we listed above. If he plays K4 or K3, he loses. And the other moves?
Kayles is an example of a subtraction game of a different type. from those games S(n1, n2, ... nk). In Kayles we have, given m piles with n1, n2, ..., nm toothpicks in each pile, with the following rule:
i)a player may remove one or two toothpicks from any pile with that number or more of toothpicks, or
ii)remove 1 or 2 toothpicks from a pile, dividing the remaining toothpicks in two arbitrar piles
The analysis is done just as in Nim. Kayles has in fact the following mex sequence
n = 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ...
G (n) = 0. 1 2 3 1 4 3 2 1 4 2 6 4 1 2 7 1 ...
Let's understand how this sequence was determined. A row of zero pins is worth zero. A row of one will also result in zero for each player, and therefore is worth *1. A row of two will result in either zero or *1, and is worth *2. A row of three will result in K2, K1 or K1 + K1 = 0, and therefore is worth *3. A row of four can give as alternatives K2 = *2, K3 = *3, K1 + K2 = *3 or K1 + K1 = 0. That means that K4 is worth *1. We leave as an exercize the confirmation of the values of five or more pins. We see that an appropriate name for the game would be (1,2)-Kayles: i.e. these rules can be generalized with complete freedom, resulting in a great number of new games.
An option we've never heard of for Kayles is to arrange the pins in connected rows, not in simple distinct rows. Below on the left we have a “double row” with three distinct moves allowed. One move would leave as the remaining figure the figure on the right.
 |
 |
What is the value of the figures above? Let's calculate the value of the figure on the right first: it may be transformed into any of the five figures below. Their values are illustrated below..
 *1 + *1
|
 *1 + *1
|
 *3
|
 *3
|
 *1 + *1 + *1
|
Simplifying, these values are 0, 0, *3, *3 and *1 respectively. Thefore, the figure above on the right has value *2. Notice that it's quite diferent from a simple mrow of two that has that same value.