Picking up from the Fairy Tales post, let's talk specifically about Rip Van Winkle. Shortly before the American Revolution, he wandered up into the Catskill Mountains, where he is supposed to have run into a group of men playing a variation of nine-pins/skittles (shortly before drinking their liquor and sleeping for 20 years).
Let's take a closer look at one variation of nine-pins, introduced in 1857 in Henry Ernest Dudeney's The Canterbury Puzzles as kayles (rhymes with ”tales”).
The rules of kayles are fairly simple. A ball is rolled at a line of wooden pins. The ball is of such a size that it could knock down either a single pin, or two pins that were right next to each other. Two players take turns, and the winner is the person who knocks down the last pin.
When playing with a real ball, the challenge is a combination of strategy (which pins will give you an advantage?) and skill (can you knock down the pins you want?). For the rest of this article, we're going to assume that the game is played by two skillful players who can hit the pins they desire everytime. This way, we can examine the strategy.
Let's start with a line of 5 object (coins, for example), using an O to represent an individual coin in the set-up:
OOOOOAssume the first player “knocks down” (takes away) the object 2nd from the left, leaving this set-up (a dot will represent a removed object):O.OOOThe 2nd player could knock down the left-most pin, the 3rd (counting from the left) 4th, or 5th pin. The player could also knock down the 3rd and 4th pins, or the 4th and 5th pins, but not the 1st and 3rd pins (they're too far apart to knock down together). Let's say he decides to knock down the 4th & 5th pins:O.O..From here, it's not difficult to see that the 2nd player will win. The 1st player can only remove 1 of the pins, and then the 2nd player will remove the other to win.Before we continue, try playing kayles (Java required) against your computer. If you click just to the left of the number of pins (skittles), you can decrease them down to 10. If you click just to the right, you can increase them to 60. Leave the Full circle box unchecked, so that two random pins will always be removed.
I'll wait while you try the game out for yourself...
...Yes, it's frustrating to lose to the computer so often, isn't it? Those of you who are familiar with nim might suspect that a similar strategy to be used here.
Kayles is different enough that you can't use straight nim strategy in it. However, there are ways to win, and I'm going to teach you how to win in games with up to 16 objects. As long as you play perfectly, and the other person doesn't know kayles strategy as well as you do, you can always win. If they do know kayles strategy as well as you do, you can still get the advantage by going first.
If a board had only two pins is a row, the first player could always win by just taking those 2 pins. 3 pins in a row? The first player removes the center pin, forcing the 2nd player to take just 1 of the remaining ones, leaving the other for the first player. The same could be done with 4 pins in a row, by taking the 2 center pins.
What about 5 or more in a row? All you have to do is go first, and you can give yourself a similar advantage! How?
If there are an odd number of pins in a row, simply remove the center most pin. For a row of 11, you would remove the centermost one, leaving 2 groups of 5:
OOOOO.OOOOOIf there an even number of pins in a row, you just remove the two pins in the center. For a row of 10, here's how the board should look after you remove the center two, leaving 2 groups of 4:OOOO..OOOOFrom this point on, all you have to do is mirror the moves made by your opponent, and you'll always be the last to move! Try the Kayles game again, with the settings starting at 10, and keep clicking Reset, until it gives you a single unbroken line of pins. You'll quickly see how and why this is an effective strategy. (It's fun when you start winning, isn't it?)But what about those games when you start with a broken row? Here's where you need to memorize some “safe” groupings that you can leave the other player without fear of losing. Because the groups below only work for groups of no more than 9 cards each, the following approach really only works well for up to 16 cards.
Besides leaving two equal chains, as described above, here are the safe arrangements of 2 groups: 1–4, 1–8, 2–7, 3–6, 4–8, and 5–9. You could remember these groups with help from the Major System, but they're easily remembered by rote, as well.
Sometimes, you'll need to leave three groups instead of two. Memorize these three sets: 1, 4, and 8 (first set); 2 and 7 (second set); 3 and 6 (third set). If you can leave three groups, each containing a number from a different set (such as 4, 2 and 6 – or even 1, 2, and 3!), then you've left yourself in a safe position.
Let's try this out with a puzzle of 10 pins as generated by the kayles page we've been using. It just gave me this arrangement (placed here in a straight line, instead of a circle, and with a dot representing the pre-removed pin):
OOO.OOOOOOOThat's a group of 3, and a group of 7. What are the options here? Well, it could easily be reduced to the safe groups of 3 and 6, so let's do that:OOO..OOOOOOThe computer played so as to leave the following arrangement:OOO..OO.OOOHere's where I have to start thinking about groups of three. Remember the sets (1,4,8 – 2,7 – 3,6)? A quick look here reveals that it wouldn't be tough to leave a group of 1, 2, and 3 (by removing two pin from either of the groups of 3, which would be one number from each of our three memorized sets! Let's do that:OOO..OO...OThe computer decided to remove the solo pin:OOO..OO....At this point, all I have to do is fall back on the original strategy of leaving two equal groups and mirror the computer, and I'll win! I remove one pin from the group of 3:.OO..OO....No matter where you go from here, it's not hard to see that the computer can't win.Memorize these strategies, and practice applying them by playing against the computer (start with 10, and work your way up to 16).
When challenging someone, ask them to set out 16 objects in 1 or two groups, and explain the rules to them. If you've practiced as taught here, you can be confident that you'll win.
Kayles with more than 16 pins is winnable, too, but the larger number of pins do make it more challenging to work out safe arrangements. If you're interested in exploring the math behind Kayles further, check out wikipedia's kayles entry and Numericana's kayles post as starting points. Kayles is also covered thoroughly in John Conway's Winning Ways for your Mathematical Plays (enjoy these free excerpts!).
Who knew that there was so much to learn from Rip Van Winkle?
The 
Let's get right to the June snippets, shall we?
Posts
