After my review of Geek Logik and mention of The Geeks' Guide to World Domination, author Garth Sundem has very generously given me a copy of his latest book, Brain Candy: Science, Paradoxes, Puzzles, Logic, and Illogic to Nourish Your Neurons, for review.

The title Brain Candy perfectly sums up the approach to its content. Like The Geeks' Guide to World Domination (GGTWD), it's filled with brief articles, most of which can be read in 1-2 minutes. However, while GGTWD was more of a general guide to things of geeky interests, such as chess openings with cool names, or information about obscure holidays, Brain Candy's focus is topics that tend to be more challenging.

Here, you're more likely to be confronted with the counter-intuitive, and the challenging, including the odd brain maze each time that a, well, “Piece of Mind” is discussed, such as the frontal or occipital lobes. Brain Candy also feels more organized and coherent than GGTWD, where the jumps in subject matter from one article to the next feel far larger.

To get a better idea of what I'm talking about, the author has posted selected segments over on his Science 2.0 blog. The Brain Candy-specific entries are easy to spot, due to their hand-drawn icons (which also appear in the book).

Extending the candy metaphor, what usually happens when you eat it? Usually, one of two things. Either you taste the candy, enjoy it, and then move on. Other times, you try it, enjoy it, and find you want more. When you find a surprising or illogical tid-bit that grabs you, you can find out more usually with a quick internet search. Basically, Brain Candy is a quick way to pass some enjoyable time, while also serving as an inspirational springboard for exploring new concepts.

Many of the ideas in Brain Candy will be familiar to regular Grey Matters readers, such as the Monty Hall Dilemma, discussed here and here (as well as many other areas of game theory), memory, and math. There is plenty in this book that I haven't covered, but will still be likely to grab readers of this blog.

As with Garth Sundem's other books, this will definitely find a place in my geeky library, so I highly recommend that Grey Matters readers give it a look for theirs, as well.

Great minds think alike! I recently added a new section of Penny Puzzles to the Grey Matters Store. A little over 1 week later, Scam School covers the same puzzle!

Before I get to the Scam School episode itself, let's cover the basic challenge first.

Start by drawing a 5-pointed star, and then place a penny (or button, or other small object) on one of the points, and slide it along either connecting line to another point. That's not hard so far, right?

Next, put another penny on any empty star point, and slide it along a line to any other empty star point. The challenge is to place 4 pennies on the star in this manner.

Before you try it, it seems easy. Most people find that they can only get to 3 coins, and find the 4-coin solution unusually elusive.

Let's change the puzzle a bit, but keep the rules the same. Here's an online version that uses an 8-pointed star (Java required). The rules are the same, but you're trying to place 7 pennies this time. Try playing this version without using the hint button and/or the explanation link as long as you can.

Perhaps there's something tricky about those lines? Let's try a similat 9-dot challenge, but just with counting (Flash required), both clockwise and counter-clockwise. The object this time is to turn 8 dots white.

Isn't it maddening that such a seemingly simple task should prove so elusive? As a solo game, this can provide hours of puzzlement.

Leave it to none other than Chico Marx to turn this into a hustle with money. Thankfully, Scam School shows you not only how Chico Marx turned this into a bar scam, but also how to beat this maddening puzzle:



The method taught here is taught so well, it shouldn't take long to work how it applies to all the other versions, as well.

Obviously, if you're doing the Scam School version above, you should go last, as suggested. However, if you're just challenging a friend or two to solve the puzzle, you'll find that if you can demonstrate the solution without explaining the method behind it, your friends will still have trouble solving the puzzle!

Try these out for yourself, and let me know in the comments of anything interesting that happened when you played this yourself, or challenged your friends.

(NOTE: Check out the other posts in The Secrets of Nim series.)

I've received plenty of positive comments on my recent Secrets of Nim posts. Jim Wilder, of jimwilder.com, sent me a private message saying, "looked at your blog on NIM... excellent stuff there". James Grime (also known as singingbanana), gave me a great compliment on his twitter account. Even the gambling-specialists over at the Magic Cafe had many good things to say about my Nim series.

It's one thing to understand the math behind the various versions of Nim. Wouldn't it be nice if there were a quicker way to determine the best strategies for Nim?

Now there is! Today, I'm introducing my Nim Strategy Calculator! It's available as a permanent page, accessible from the Mental Gym's Workout page under Tools.

The Nim Strategy Calculator is actually 3 calculators in 1. The first is the strategy calculator for single-pile Nim, the second is for multi-pile Nim, and the final one is merely for determining the next move in the middle of a multi-pile Nim game (all these terms are defined in Part 1 of my Secrets of Nim post). You choose between them using the tabs at the top.

I've tried to make them easy to use and straightforward by asking for all the information in an interview-type format. Once you enter all the relevant information in a section, you simply click the Calculate button at the bottom of the section, and the strategy will be given to you in plain English.

Here are more details on each section:

Single-Pile Nim Strategy Calculator

Being the simplest form of Nim, you only need to provide 4 pieces of information for single-pile Nim:



The first question, which is the same with all 3 calculators, is whether the person who moves last is the winner or the loser.

The next question is how many objects are used. While single-pile Nim is usually played down to 0, such as the game in Episode 8 of Scam School, there are games where you start at 0, and try and go up to a maximum amount, like in episode 80 of Scam School. This is why this is asked as the “maximum” or “limit”.

This is also why the third question asks whether the game is played down to 0 or up to the limit. Lastly, the final question asks about the range of the amount of objects that can be used per turn.

As an example, let's try using the calculator to analyze the match game from Scam School's 8th episode. The player who makes the last move is the loser, they're using 17 objects, playing down to 0, and up to 3 objects are allowed per turn, so the data would be entered as follows:



Click the Calculate Nim Strategy button below all the data, and you get this response in the box:

The rules for this particular version of the game of Nim are as follows:
* There are two players.
* The players alternate taking turns.
* The game starts out with 17 objects.
* On a given player's turn, they must remove anywhere from 1 to 3 objects.
* Neither player is allowed to remove 0 objects.
* The last person to make a move is the loser.


The Scam: Although seemingly fair, you can rig this game in your favor.

For this particular version of Nim, the other person should go first. This will ensure that you can always leave certain key numbers of objects on each turn that will guarantee your win.

The key numbers of objects you need to leave on each turn, in order to safely win the game, are as follows:

13
9
5
1 (of course)


Tips:

* You don't have to hit every key number. Just make sure you get to one of the above key numbers before the goal is reached, and you'll always be able to win the game from there.

* If it's decided that you must go first, and your opponent isn't wise to the ways of Nim, it's still possible for you to win. Only play small amounts of objects on your turns, until you get an opportunity to reach a key number.

* Instead of playing single-pile Nim with physical objects, you can often just state the numbers verbally, or even use a calculator.

This data can be copied to a text editor or word processor, where you can save the information for later. Note that various tips are given, and they are often different for particular settings.

Whenever you get a response, always read it carefully! Besides the particular goal numbers, it also mentions whether you or the other person should go first, and what to do if that's not possible. I've tried to make the tips as useful as possible, as well.

Try entering the data yourself for Scam School episode 80: The person who makes the last move is the winner, the limit is 31, the game is played up to the limit, and the number of objects used per turn is from 1 to 6. When you click the Calculate Nim Strategy button, note that the advice here is exactly the same advice (for the first round, anyway), as in the video (assuming you entered the information correctly)! There are even some extra tips that aren't given in the video.

Multi-Pile Nim Strategy Calculator

The Multi-Pile Nim Strategy Calculator looks a little different than the single-pile version:



The first question, as before, determines whether standard or Misère Nim is being played.

The next question is a pull-down menu that lets you select from 3 to 9 piles. When you change this number, a number of boxes equal to your choice will appear below it. These boxes allow you to specify how many objects are in the individual piles.

One of the most basic versions of multi-pile nim is taught in episode 37 of Scam School. In this version, the person who removes the last object loses, there are 3 piles, and the piles consist of 3, 5, and 7 objects respectively. The data would be entered like this:



When you click the Calculate Nim Strategy button here, you might be surprised to find more safe positions than are listed in the Scam School video. In this particular case, the new moves are simply those that are 1 object different from the opening layout.

Just for fun, try using the Multi-Pile Nim Strategy Calculator to determine the best strategy for the Last Year in Marienbad version (it's Misère Nim), or to find out why the XKCD character in this comic reacts the way he does.

Next Move?

Originally, I tried using the Multi-Pile Nim Strategy Calculator to play against online versions of Nim, such as Pearls Before Swine or Nim Master (Flash required for both). Unfortunately, I often found that the number of piles and/or the number of objects involved often made it too difficult to search through the list of safe positions quickly and effectively.

To solve that problem, I added the “Next Move?” calculator. It works pretty much the same as the Multi-Pile Nim Strategy Calculator, with just one added feature: A checkbox you mark if the arrangement in question is the first move. Many computer versions of Nim let you decide who goes first, so this will give you an appropriate recommendation. Here's how the “Next Move?” calculator appears:



As an example, I'll start a game of Pearls Before Swine, in which the last person to remove an object is always the loser. I see 3 piles, consisting of 3, 6, and 8 object as the opening layout. I enter this into the “Next Move?” calculator as follows:



Since this calculator is only concerned with looking 1 move ahead, the reponses are much briefer. The response I get from the above entry, after clicking the Calculate Next Move button was this:

Here are the plays you can make on this turn, in order to insure a win at the end:

3, 6, 5 (8-object pile: Remove 3)

Note that it gives you the layout numerically, but also tells you in plain language how many are removed, and from which pile.

Continuing to play this same game, I make the recommended move, and am now left with 3 piles of 3, 6, and 4 (after the other player's move). Updating this to reflect the new information (including the fact that this isn't the opening move), I get this response:

Here are the plays you can make on this turn, in order to insure a win at the end:

2, 6, 4 (3-object pile: Remove 1)

Needless to say, after a few more moves, I won this particular game.

Uses

There are quite a few nice things about using these calculators.

First, if you want to understand how the strategy changes as the rules change, you can get a quick understanding here. If you have a favorite layout of, say, multi-pile Nim, and people after a few games are asking things like, “What if I go first?” or “What if we make the person who takes the last match a winner?”, you can be ready for such eventualities.

Working with the calculators can make the entire Secrets of Nim series easier to follow and understand.

Also, these calculators can help you learn a particular strategy by heart, as well. In multi-pile Nim, the same safe positions are safe in any game (with certain exceptions for Misère Nim and multiple 1-object piles). Using the “Next Move?” calculator frequently in the beginning will often make these moves very familiar.

Finally, you can use these calculators to create custom Nim variations (and learn to play them correctly). For example, what if you have a friend whose 37th birthday is coming up, and he has 4 kids. You could challenge him to a game of single-pile Nim that starts with 37 objects, where you're allowed to take up to 4 objects per turn. In this particular case, I suggest making it a Misère Nim, because the winning strategy can quickly become obvious (Why? Run it through the calculator and see for yourself).

Alternatively, what if his 4 kids are ages 4, 8, 10 and 14, respectively? You could play a game of multi-pile Nim against him, starting with piles of 4, 8, 10 and 14, and already know the best plays.

I hope you enjoy the Nim Strategy Calculator, and find it useful! If you do find it useful, please take the time to click on the ads on this page, or the calculator page.

Back in 1967, puzzlemaker Frank Armbruster released a devious puzzle through Parker Brothers that took the world by storm.

It was called Instant Insanity, and has sold over 12 million copies (and, like Rubik's Cube, spawned numerous imitations). Parker Brothers re-released it in the 1980s, while the world was going nuts over Rubik's Cube. Here's the 1980s ad for Instant Insanity:



So, what exactly was the challenge? The puzzle itself came as 4 separate cubes, with each side of each cube being one 4 colors (green, red, blue, and yellow), and the colors were arranged on different cubes in different ways. The object of the puzzle is to stack these cubes in a column so that each side (front, back, left, and right) of the stack shows each of the four colors (as shown in the top left photo in this post).

At first, this doesn't sound that hard. As a matter of fact, you can try it out here on Grey Matters (Java required). Alternatively, here's a Javascript version.

In both of the above versions, the cubes are effectively unfolded and lay flat. If you prefer to work with a version where the subes remain in 3-D, there's the online nrich Instant Insanity version (Flash required), or the even more tactile iPad version.

By 1971, the puzzle was so popular and so recognizable, it was used as part of a computer vision project at the Stanford University Artificial Intelligence Laboratory, displayed to the public at an artificial intelligence conference:



How would a human go about solving it, though?

It's not easy. Perhaps you may get a clue from this video (you might want to turn down the volume before hitting play), if you watch carefully enough:



Hmmm...what are those lines and circles? Well, they look kind of like the ones Leonard Euler (pronounced "oiler") used to solve the classic Seven Bridges of Königsberg problem.

Basically, that's exactly what this is. Since the goal of Instant Insanity is to form a particular relationship among the sides, this boils down to a networking problem.

In Ivars Peterson's August 9, 1999 column, Averting Instant Insanity, he shows how to simplify the problem down with simple graphs representing the color arrangements, much like Euler did with the Seven Bridges of Königsberg problem, and then how to use this information to find the answer.

Jaap's Instant Insanity / Buvos Golyok / Drive Ya Crazy Page discusses some of the popular variations. He shows a similar approach to the variations, making this a good page to learn how to generalize the solution approach.

Robin Wilson, Professor of Geometry at Gresham College, has made a video detailing the graph solution that may help you visualize the solution process better:



Although the graph theory approach is the one most commonly used, there is a surprising 2nd approach, using prime numbers, as well. If you're interested, Professor Wilson discusses that 2nd approach in this video.

Be honest, did you peek at the solutions before you even tried the puzzle?

It's time for the August snippets! This month's snippets have two themes – Math fun and FREE stuff!

• The folks over at MathTutorDVD.com have a free weekly video podcast called Mental Math Secrets (iTunes Link). Each week, one math trick is taught on a whiteboard, and explained in detail. They're quite clear, and the weekly nature of the podcast gives you time to master it before learning the next one.

• Ever play Dots and Boxes? You can try a free javascript version online, playing against the computer here, or against another player here. If you play long enough, you might be wondering if there's strategies that can help you win. There sure are, and the best place to learn them that I've ever found is Ilan Vardi's free online course Mathter of the Game. Check it out for an eye-opening look at a seemingly simple game.

• After writing about things like Nim and Corner The Lady, I thought it would be fun to be able to play these against others on my iPad. While there are limited Nim choices and zero Corner the Lady choices in iPad apps, there is a solution: Metaversal Studios' free GameRoom app (iTunes Link) to the rescue! Besides playing the built-in games of Checkers, Go, Reversi, Mancala, and Halma, there's a custom mode that allows you to choose the board size (7x7 up to 20x20), and various features of the look of the board, and will enable you to play just about any grid-based game (or even some games where grids are irrelevant) against another player who agrees on the rules. Check it out!

• While I'm thinking about free iTunes apps, check out Peg Solitaire - BrainVita from TouchMeme (iTunes Link). This is the standard English Peg Solitaire (as opposed to the triangular “Cracker Barrel” version). It's no more or less than what it claims: The standard puzzle where you try to leave a peg in the center. If it fries your brain, there's an excellent and easily-remembered purge-and-package approach to solving it taught here.

I've talked quite a bit about Pi on this blog, but today, I'm turning my attention to a different number: phi. Like Pi, phi goes on forever, and can only be approximated. It's equal to roughly 1.6180339887, but is also known as the golden ratio.

What makes phi as a number so special? And what's with the name golden ratio, anyway? Of course, Grey Matters readers have an additional question: What kind of fun can we have with it?

The Basics

  8
  3
 11
 14
 25
 39
 64
103
167
270

(NOTE: Check out the other posts in The Secrets of Nim series.)

I hope you've enjoyed The Secrets of Nim series. I'm going to wrap it up today, with a brief, yet possibly surprising, look back at Nim.

For most of history, the various versions of multi-pile Nim were played as a regular game, as opposed to a swindle. It was known that if you got to certain positions in some select games that you could win from that point on, but nobody knew whether it was possible to guarantee a win from the start.

That all changed in 1901, when Charles L. Bouton of Harvard University discovered the approaches to multi-pile nim that were detailed in part 2 and part 3 of this series.

Just over three decades later, R. P. Sprague and P. M. Grundy, working independently, both discovered that larger numbers of objects in Nim (among other games) could be made easier to handle by reducing them to smaller ones via certain functions. A good introduction to the Sprague–Grundy theorem, as well as variations of Nim, is available via this PDF from the UCLA Math Department.

If you really want to see where analysis of Nim can take you, including a mind-boggling array of variations, I highly recommend checking out Winning Ways, for Your Mathematical Plays, Volume 1, Volume 2, Volume 3, and Volume 4, by Elwyn R. Berlekamp, John Horton Conway, and Richard K. Guy.

Naturally, once it was proven that you could win Nim from the beginning, and safe moves could be determined throughout, it quickly became a favorite of swindlers. Equipment began to show up to make the game portable and easy to play. The Gambler's Beads were an interesting version of single pile Nim, but multi-pile versions were also developed.

Even while the earliest computers were being developed, compters such as Nimatron were being displayed at the 1940 New York World's Fair. The Nimrod computer, a vastly improved version of Nimatron, was displayed at the 1951 Festival of Britain.

This effectively makes Nim among the first, if not THE first, computer games!

Thanks to the simplicity of Nim, it can also be played against mechanical computers, instead of just electronic ones. In 1961, a single-pile Misère game called Dr. Nim was released. Check out the impressive operation of this simple plastic machine in the video below:



In one of his Scientific American columns, Martin Gardner discussed Hexapawn (PDF), and how you can play against a simple set of matchboxes and stones that learn to improve their play via a system of punishments and rewards (More on this in my Computing . . . Without Computers! post).

On the last page of that same column, there's mention of a Bell Labs research director who used a similar approach to build a matchbox learning machine for Nim! Impressively, the machine required only 18 matchboxes, could go first or second in different games, and yet would play almost perfectly after only around 30 games. I think if I lost a game of Nim to a set of matchboxes and stones, I'd feel dumber than a box of rocks.

When the first pocket calculators were released in the 1970s, Nim was adapted to those just as quickly as it had been with the first electronic computers. I wouldn't be surprised to learn that someone tried getting several pocket calculators together and use them to play some form of multi-pile Nim.

It's not hard to find Flash versions today, but there are a few that really stand out. Pearls Before Swine goes for the whole experience, and constantly challenges you with more and larger piles, while keeping track of your wins and losses.

Ricardo Rix's version of Nim (multi-pile Misère Nim) lets you choose the level of your opponent's play, as well as how many piles will be involved, so you can develop your skill and analytical abilities at your own pace.

1961 must've been a great year for Nim. Not only was the aforementioned Dr. Nim released, but it was also featured in a French art film that year, called Last Year in Marienbad, where it makes 3 appearances. At that link, you can see 2 of them via an embedded Flash or downloadable iPod video. The 3rd can be seen on YouTube:



As a matter of fact, to this day, many people refer to multi-pile Misère Nim played with 1, 3, 5, and 7 objects as Marienbad Nim, or simply Marienbad. You can try a Javascript version here, and try a Flash version here.

If you're geeky enough to analyze and enjoy Nim, as well as being geeky enough to enjoy XKCD, you'll probably get a good laugh from this Spiked Math cartoon, which pays tribute to both.

I'd like to hear your comments and criticisms, especially concerning The Secrets of Nim posts, in the comments below!

(NOTE: Check out the other posts in The Secrets of Nim series.)

At this point, you should have learned and practiced about standard and Misère single-pile Nim, as well as standard multi-pile Nim. Now, we move onto multi-pile Misère Nim.

Trying It Out

(NOTE: Check out the other posts in The Secrets of Nim series.)

My previous post discussed the math and logic behind single-pile nim, including several variations. Make sure you read and understand that post before reading this post.

Review and Practice