0

The Secrets of Nim (Fibonacci Nim)

Published on Thursday, September 23, 2010 in , , , , ,

NIM is WIN upside down!(NOTE: Check out the other posts in The Secrets of Nim series.)

Thought we were done with Nim? Not by a long shot! Today, I have a single-pile standard Nim game for you (as defined in Part 1 of the Secrets of Nim series), but with a twist!

The New Rules


Just as with most standard single-pile Nim games, this version has the following rules:

• There are two players.
• The players alternate taking turns.
• The game starts out with a set number of objects.
• Neither player is allowed to remove 0 objects.
• The last person to make a move is the winner.

The twist comes from two new rules:

• The player who moves first can remove as many objects as they like from the pile, as long as they leave 1 or more objects for the other player. (e.g., In a game with 26 objects, the first player can remove up to 25 objects.)

• After the first move, each player may remove, at most, twice the number of counters his opponent took on the previous move.

Let's start with 26 objects, which has become a standard starting amount for this version of Nim. Try playing this online Javascript version (To keep trying with 26, reload the page instead of clicking the newgame button).

Did you have any luck? Or did your computer keep winning?

Basic Strategy


Well, it's Nim, and we know there are ways to guarantee a win. Perhaps we could use the Single-Pile Nim Strategy Calculator. Hmmmm...nope, there's no way to account for the variable amounts you're allowed to take.

There's a bit of a hint in the sub-heading of this post, Fibonacci Nim. Let's jump back a few posts, and check out the first video from Fun with Phi again:



Before you get too scared, the method does not involving performing any sort of arithmetic with Phi.

What we need here is the original Fibonacci numbers themselves. Since we should probably keep our games under 100 objects, we'll just focus on the Fibonacci numbers that are less than 100: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, and 89.

If you're going to play Fibonacci Nim regularly, you should probably commit these to memory. Playing the game online is probably the best way to reinforce these numbers.

Let's take a look at two people playing Fibonacci Nim, and pay particular attention to the explanation of the winning strategy at the end:



So, the strategy, as mentioned, is simply to leave a Fibonacci number of objects at the end of your turn.

Is it really that simple? No. It works well enough with certain starting positions, including the standard 26, but when you start varying the numbers, this strategy isn't enough.

For example, what happens if you start with 33 objects? The nearest Fibonacci number is 21, so you might decide to remove 12 objects, and leave 21. Great, except that this means the other person can take up to 24 objects, and with only 21 objects in play, that gives the win to the second player!

Complete Strategy


So what went wrong in our game of 33 objects?

To analyze the game for any given number of objects, you need to first break it down into a series consisting solely of Fibonacci numbers.

Going back to the 26-object version, what's the highest Fibonacci number less than or equal to 26? 21, of course! What does that leave? 5! This happens to be another Fibonacci number. Thinking of 26 as 21 + 5 makes the next play easy to see. Take away 5, and leave 21.

Now, let's apply the same approach to 33. What's the highest Fibonacci number less than or equal to 33? Again, it happens to be 21. Subtracting 21 from 33 leaves 12, which isn't a Fibonacci number.

What do we do in this case? Break the number down again, and again, until all we're dealing with is Fibonacci numbers. What's the highest Fibonacci number less than or equal to 12? 8, and 12 - 8 = 4. 4 isn't a Fibonacci number, but 3 is, and 4 - 3 = 1. 1, of course, is a Fibonacci number, so we're all set!

All this means that 33 breaks down into 21 + 8 + 3 + 1. When you've broken down the number of objects down into its component Fibonacci numbers, your best play is to remove a number of objects equal to the smallest of the Fibonacci numbers in the problem. In the case of 21 + 8 + 3 + 1, that means your play should be to remove 1 object.

Playing the smallest number of objects is best strategy here because it gets you closer to your goal while also minimizing the options for your opponent.

I just went over to the Javascript version of this game, clicked on the newgame button, and it started with 48 objects. Let's see how this goes with this strayegy.

48 breaks down into 34 + 13 + 1, so:

Me: I remove 1, leaving 47. The computer can remove up to 2 objects.
Computer: The computer removed 2, leaving 45. I can remove up to 4 objects.
Me: 45 = 34 + 8 + 3, so I remove 3 objects, leaving 42. The computer can remove up to 6 objects.
Computer: The computer removed 6, leaving 36. I can remove up to 12 objects.
Me: 36 = 34 + 2, so I remove 2 objects, leaving 34. The computer can remove up to 4 objects.
Computer: The computer removed 4, leaving 30. I can remove up to 8 objects.
Me: 30 = 21 + 8 + 1, so I remove 1 object, leaving 29. The computer can remove up to 2 objects.
Computer: The computer removed 2, leaving 27. I can remove up to 4 objects.
Me: 27 = 21 + 5 + 1, so I remove 1 object, leaving 26. The computer can remove up to 2 objects.
Computer: The computer removed 2, leaving 24. I can remove up to 4 objects.
Me: 24 = 21 + 3, so I remove 3 objects, leaving 21. The computer can remove up to 6 objects.
Computer: The computer removed 6, leaving 15. I can remove up to 12 objects.
Me: 15 = 13 + 2, so I remove 2 objects, leaving 13. The computer can remove up to 4 objects.
Computer: The computer removed 4, leaving 9. I can remove up to 8 objects.
Me: 9 = 8 + 1, so I remove 1 object, leaving 8. The computer can remove up to 2 objects.
Computer: The computer removed 2, leaving 6. I can remove up to 4 objects.
Me: 6 = 5 + 1, so I remove 1 object, leaving 5. The computer can remove up to 2 objects.
Computer: The computer removed 1, leaving 4. I can remove up to 2 objects.
Me: 4 = 3 + 1, so I remove 1 object, leaving 3. The computer can remove up to 2 objects.
Computer: The computer removed 1, leaving 2. I can remove up to 2 objects.
Me: I remove both remaining objects, so I win!

To help you practice this strategy, try out this version of the game from cut-the-knot.org (Java required).

Set the Java version up by clicking the No more than twice radio button, and make sure the Hint checkbox is checked. This way, the computer will display the equation breakdown for you at each step. To play, you simply click the button with the number you wish to remove.

Once you get used to thinking of each number as a sum of Fibonacci numbers, and playing the smallest number, uncheck the Hint box, and try doing it without the equation being displayed. When you can win every time with no hints showing, you're almost ready to play the game against another player!

One Last Important Point


Wait, ALMOST?!? There is one last important thing to remember. If the number of starting objects is already a Fibonacci number, you must have the other player go first! Why?

Take 21 objects, for example. The first player must leave at least 1 object for the second player, so you can't remove all 21.

What if we think of 21 as the sum of 13 + 8? In that case, we removed 8 objects, leaving 13. Since 8 objects were removed, the other player can remove double that, or 16. Their move is a no-brainer – remove all 13 objects!

This is true for any Fibonacci number. Starting with 89, removing 34 to leave 55 means the other player can remove anything up to 68.

The reason for this comes back to Phi. If you start with a given Fibonacci number, multiply it by Phi, and round to the nearest whole number, you'll get the next Fibonacci number in the sequence. Since Phi is approximately 1.6180339887, multiplying by that, or anything more than that, such as the 2 in our doubling rule, makes Fibonacci numbers themselves a losing proposition.

Practice this version, play it against your friends, and let me know about your experiences!

0

Think-a-Link

Published on Sunday, September 19, 2010 in , ,

Think-a-Link: Is it in? You know it is!Back in June, I listed several free online mnemonic sites. Recently, I found a mnemonic site with a social networking twist!

It's called Think-a-Link. At its most basic level, it's much like the other mnemonic sites I've mentioned (Yes, I've already added it here and here), with categories and a search feature to help you find specific mnemonics, or “links”, as they're called here.

However, Andy Salmon, AKA “Sir Link-a-Lot”, has taken the extra step of integrating social features into the site. Once you sign up for a free account, you can rank the links of other submitters on a scale of 1-10 (10 being the best), or submit your own.

Even if there's already a link for a particular thing to remember, you can submit your own link, and become a contender for the best-rated link for that fact. For example, let's say you want to remember that China's time zone is GMT plus 7 hours. At this writing, the top-rated link for that is to remember, "'Is the Great Wall of China one of the 7 Wonders of the Ancient World?'...'No.'" However, there are also 3 other contending links, here, here, and here.

I like the idea of having competing links for a given topic, because sometimes even the lower-rated links might be catchier for you personally. If something works great for others, that doesn't mean it will work great for you.

I created my own account on the site recently, and found it very easy to use. My first submission has already been added.

The intro video gives you a good idea of the site, but for sheer inspiration and creativity, it's hard to beat the video of the school presentation:



Note that the kids are able to come up with some impressive associations on the fly. To me, the Think-a-Link approach is what education should really be about – getting kids not only to learn more about the world, but improving their creativity so they can improve that world, as well.

Not only does the Think-a-Link site work well on its own, but it also works well with other tools I've discussed before. The links you learn there can help you learn with flashcards quicker, or do better on timed quizzes.

It's not hard to see that a little imagination can go a long way here. I like Think-a-Link because it has the same basic idea as Grey Matters: Not only can learning and fun go together, they should go together!

2

Scam School Meets Grey Matters...Again!

Published on Thursday, September 16, 2010 in , , , , ,

Scam School logoThe Calendar Nim scam from Scam School was actually the 2nd scam idea I submitted to Scam School. This week, the 1st scam idea I submitted to them has been turned into an episode!

OK, to be fair, Penney's Game (or Penney Ante) is well known, and Brian Brushwood does mention that many people sent it in. Note, though, that he does give a special mention to me and the Grey Matters site at the end! Thank you very much, Brian!



James Grime (singingbanana), whom you may remember from the Pi Day Magic Trick, has a great video explanation in two parts. The first part focuses on the rules and how to make the choices, much like the above episode of Scam School. In the second part, he explains the mathematics behind the bet.

If you're interested in more of the technical details, Plus Magazine's most recent issue (at this writing) features an excellent article explaining the math behind Penney's Game.

The part that causes most of the confusion (besides the probabilities) is what it called non-transitivity. It's actually a fancy word for a very simple concept.

Imagine you have 3 cars models, which we'll call A, B, and C. If model A is more expensive than model B, and model B is more expensive than model C, it's not too hard to figure out that model A is more expensive than model C, right? This is a transitive relationship, and is the kind of relationship we're used to when comparing things. Think of transitivity as a relationship where you can rank things in the manner first, second, and so on down to last.

However, this kind of relationship doesn't always hold true. In Rock/Scissors/Paper, for example, rock beats scissors, and scissors beats paper, but this doesn't mean that rock beats paper (as we might expect in a transitive relationship). As we all know, paper beats rock. In this kind of relationship, each item can rank higher than at least one other item in the set, and each item can rank lower than another item in the set. For example, rock beats scissors, but rock can be beaten by paper.

Since this latter type of relationship can't be given a rank like that of a transitive relationship, this second type is called, not surprisingly, non-transitive.

Because we're more familiar with the first (transitive) type of relationship, the qualities of non-transitive relationships can often be quite surprising. Want proof? Since we've used Rock/Scissors/Paper as an example, check out Scam School's use of the game:



If you use specially made dice, such as these or these or the home-made set described in the video below, you can also pull a non-transitive dice scam!



Don't like the idea of special dice for this, the dice could be replaced with 6-card hands using the same numbers, and have cards drawn at random from the players' respective face-down hands. You will need 2 decks to make this up, however, as one hand will contain six 3s.

Getting back to the Penney's Game episode, take another look at Brian's parting joke: “Next week, we're going to be learning, from a memory expert, a mnemonic device that will allow you to memorize the entire constitution in 20 minutes.” Hmmm...should I feel bad that I actually did a series of posts (Part I, Part II, Part III) on this very topic? I do suggest spending more than 20 minutes on it, though.

0

Maths Busking

Published on Sunday, September 12, 2010 in , , ,

Maths Busking LogoOver in England, there's a group of street performers that are right down my alley. They call themselves Maths Busking.

Quick related side note: If you're more use to North American English than you are British English, the word “maths” might sound unusual to you. It's simply the shortened form of the word “mathematics” used in Britain.

Maths Busking is mainly a central group of performers, who also train others in the art of street performing with math (Yes, I use the North American English form throughout this blog). Their challenge is to engage the audience in such a way that it is the math itself that the audience finds memorable and engaging.

Here's a video showing some of their training and performance sessions:



Maths Busking actually has a central set of a few performance pieces, some of which are shown in the video above. The first bit you see, with two people tied together is known as Zeeman's Ropes (The site dates it back to 1978, but it goes back more than 250 years). The piece where the young boy is trying to turn the vest/waistcoat inside out with his hands tied is Waistcoat and Handcuffs. The final piece in the video is the light and amusing Emergency Pentagon.

Some of their other pieces will already be familiar to regular Grey Matters readers. Cubic Root Whiz, for example, can be learned over in the Mental Gym, as well as practiced.

Their mind reading feat, known to magicians as the Age Cards, has been discussed many times here on Grey Matters. You can learn about it as part of Werner Miller's Age Cube, his Age Square, or my post on age-guessing.

Take a close look at what's going on at about 1:40 into this video from the Guardian (as seen on the Southbank Show). You've got a woman with a £20 note attached to her bandanna with a clothespin, with assorted other clothespins on various parts of her clothes, while the two gentlemen remove the clothespins. Does it look familiar? No? This Guardian's article doesn't talk in detail about it, but this Globe and Mail article on Maths Busking does in detail (about halfway down). Yep, their Twenty Quid Game is our old friend single-pile Nim!

Their Knott a Handkerchief (taught on this eHow video), Divine Remainder (There's a great routine for this in Harry Lorayne's book, Mathematical Wizardry) and Handshakes (also taught in this BetterExplained post) routines are also fun and easy to understand.

You might be wondering at this point what it would be like to go through the training, and perform these in front of people. The BBC had the same question in mind, and sent Ruth Alexander out to do just that. You can see her performance in this video, and hear her talk about the experience in the June 18th, 2010 edition of BBC Radio 4's More or Less (This section begins about 16 minutes into the show).

My next question is, how long before this makes it across the pond?

0

Videos: Bars, Lines, Dots, and Pi

Published on Thursday, September 09, 2010 in , , , , ,

Today's posts contains mainly some memory- and math-related videos I've recently discovered, along with some thoughts they inspired.


The Pi-Reciter Your Man Could Smell Like:


If you're counting, the Old Spice Guy (Isaiah Mustafa) makes it up to 100 digits of Pi, albeit by cheating through editing. Ladies, if you want your man to smell like him, well, use Old Spice.

If you want your man to recite Pi like him, without cheating, have him practice Pimon (Flash required). It's a game much like the classic Simon game, except that it will always light up in the order of the digits of Pi. It's a fun way to push yourself to learn Pi while having fun.


Tom Lehrer's Elements Song, Instant Search Version:


I've featured Tom Lehrer's Elements Song before, but this new version employs the newly released Google Instants, a technology that gives search results as you type. I can see this becoming a very popular internet meme.


Chuck Jones' The Dot and the Line: A Romance in Lower Mathematics:


This unusual feature is based on a book of the same name by Norton Juster, first published in 1963. It's a whimsical story, based in mathematics, that builds up to the perfect pun at the end.


Wanna Bet? Barcode Kid Bet:


This clip is from a German show called Wetten Dass...? (Wanna Bet...?). It's a combination talk show and game show, where celebrities come on, and bet on whether ordinary people can truly perform extraordinary feats. The most intriguing of these are the Kinderwette, or “Kid Bet” challenges.

In the video above, two kids claim they can identify grocery store products solely by their barcode. Look closely, though, and you'll notice that they're give barcodes with no numbers on them! Most likely, they're using variation of a binary memory technique to perform this feat. The amount of work they put into memorizing the items is still impressive, though!

0

New Memory Tools and Techniques Page!

Published on Sunday, September 05, 2010 in , , , ,

Memory ToolsIf you haven't already checked out my Downloads and Feeds/Social Links pages already, now is a good time to do so.

Once you're familiar with the existing pages, it's time to check out the brand new Memory Tools/Techniques page!

I've often reviewed and talked about sites featuring memory tools and techniques, but going back through 5 years of posts can be somewhat laborious. So, I've taken the links containing free (yes, they're all FREE) online tools and techniques and posted them in this new page.

There are three main sections, covering three different approaches to memory. There's mnemonics (the use of memory hooks to link ideas together), spaced repetition (the use of scheduling flashcards for more effective learning), and spiral learning (learning new ideas in ever-increasing complexity).

The heading of each section is a link to a basic introduction of its respective memory approach. Each section has its tools and techniques, except for spaced repetition, since it's a single technique in and of itself.

The mnemonic tool section also has a subsection of online mnemonic encyclopedias, where you may be able to find mnemonics that others have created. The remaining tools are mainly mnemonic generators.

Under techniques, I've simply linked to my existing Memory Basics page over in the Mental Gym. I didn't see a need to simply duplicate those links.

I hope you find this new page useful. If you can think of any links to add to this page, please let me know about them in the comments.

0

More Quick Snippets

Published on Thursday, September 02, 2010 in , , , , , , ,

LinksAs regular Grey Matters readers know, I'm a great supporter of going back to the classics. Therefore, this month's snippets theme is getting back to the classics!

The importance of learning any kind of classical knowledge is summed up by TJIC's law: "A sufficiently large lookup table is worth 10 IQ points."

• I recently ran across a series of books, from the late 19th to early 20th century, on Project Gutenberg which focus on classical knowledge. The series is called Every Child Should Know, and each book focuses on a particular area of knowledge, such as poetry, myths, artwork, and more.

Since this is part of Project Gutenberg, you can access these on iOS devices, Kindle, Nook, and most other ebook readers.

Also available as part of this series are the MP3 version of Poems Every Child Should Know, and an improved PDF version of Pictures Every Child Should Know, which fixes a few errors, including rotated and missing pictures.

• I've set up a few YouTube playlists containing some classical knowledge. 6 of them contain poetry, and the last contains classical music. The YouTube playlists are:
Classic poems
Poems from UBS ads
Poems by Nipsey Russell
Modern poems
Poems from Old Possum's Book of Practical Cats
Poems from Martin Gardner's Best Remembered Poems
Classical Music You Didn't Know You Knew

• Assuming you understand a classic idea properly, there's nothing wrong with modernizing it to regain interest in the idea. For example, one classic number mind-reading feat was updated with lottery tickets to create Powerball 60. Another classic approach in mind-reading magic was adapted for use on the iPhone and iPod Touch to create iForce.

Even better, these 2 ideas were combined to create an unusually powerful mind-reading feat. If you like that idea, check out this nice addition that takes it to the next level.

• As noted in the links below, I've talked about fairy tales, but a look through the aforementioned Every Child Should Know series reminded me that tall tales are just as valuable. Great sources for tall tales include:
– John Henry: James Earl Jones reads Ezra Jack Keats' book (audio only), Disney's American Legends (YouTube: Part I, Part II)
– Johnny Appleseed: Disney's American Legends (YouTube: Part I, Part II)
– Paul Bunyan: HTML book version, Paul Bunyan Swings His Axe (Google books), Disney's 1958 Paul Bunyan movie (YouTube: Part I, Part II)
– Pecos Bill: Disney's American Heroes (YouTube: Part I, Part II, Part III)
Shelley Duvall's Tall Tales & Legends series

• Looking for more in the way of classics? Look no further than here on Grey Matters! Check out the posts on:
Chemical elements
Computer principles, without the use of a computer!
Fairy tales
History, James Burke style
Language learning
Poetry
Study tips
– US Constitutional amendments (Part I, Part II, Part III)
US States, including the following year's update
– More fun, free, and nostalgic learning resources.

1

Review: Brain Candy

Published on Sunday, August 29, 2010 in , , , , , , , ,

Garth Sundem's Brain Candy bookAfter 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.