Sorry about missing a post last week. It turned out to be a busier weekend for me than I originally planned.

I'm back this week, and I've brought plenty of snippets with me to make up for the missing post!

• Back in September, in DataGenetics' *Grid Puzzle* post, an intriguing puzzle was posed: *Imagine there is a grid of squares. You draw a line connecting one intersection to another intersection on the grid. The question is: How many squares does this line cross through?*

The link works through the answer, including an interactive widget which may help you work it out. It turns out that the answer involves only simple arithmetic and being able to work out the greatest common divisor (GCD) of 2 numbers.

If you can work out the GCD of 2 numbers in your head, you can turn this into a mental math presentation. How do you go about that? Math-magic.com has the answer, in both webpage form and PDF form! Page 94 of Bryant Heath's *Number Sense Tricks* also has some great tips on finding the GCD of 2 numbers in your head.

• Also back in September, I wrote about Knight's Tours on a calendar, and included sample calendars for both September and October 2014. I figured it's time for the November 2014 version, included below. This month, 6 is most date-to-move matches I could find:

• OfPad.com seems to have a similar goal to Grey Matters, which is to improve your genius. There's plenty to explore as a result, but I'd like to draw your attention to their *Mental Math Tricks* posts in particular. There's lots of great tricks, some of which you may not have seen before.

• To wrap up this month's mental math snippets, I'd like to focus on one particular technique for multiplying any two 2-digit numbers together. I've seen this technique before, but the way dominatemath teaches this multiplication technique, it just made so much more sense than the other instructions I've seen for this approach.

That's all for this month's snippets. Have fun exploring them!

## Even More Quick Snippets

Published on Sunday, November 16, 2014 in fun, Knight's Tour, math, mental math, self improvement, site features, videos

## Prime Mates

Published on Sunday, November 02, 2014 in fun, math, mental math, self improvement

I've wanted to write about factoring numbers in your head for a while, but never really had a good approach to analyze and discuss.

Recently, I've come across some strategies that mesh well with what I've discussed before on this site. Learning to factor a number in your head can be tricky, but it can be done.

**BASICS:** Starting from a given number between 1 and 10,000, you're only going to test for divisibility from the number 2, up to the square root of the given number. If you're familiar with estimating square roots, you only need the whole number part.

For example, if you're given the number 447, you only need to estimate the square root as 21, to realize you only need to be concerned with numbers from 2 to 21.

To narrow things down even further, you're only going to test for divisibility by prime numbers from 2 up to the limit you determine (21 in the above example). Between 2 and 100, there are only 25 prime numbers (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, and 97), so testing only for these minimizes the time it will take.

Certainly, divisibility tests for 2 (is the rightmost digit even?), 3 (do the digits add up to a multiple of 3?), and 5 (is the rightmost digit a 5 or a 0?) are well known, but how do you go about testing, and remembering the tests, for the higher primes?

**TECHNIQUES:** *NUMBERS ENDING IN 9* - Back in April, I discussed how to work out divisibility tests for numbers ending in 9. For divisibility by 19, you would divide by 20, add up the quotient and remainder from that divisibility problem, and see if they added up to a multiple of 19. For 29, you'd run through the same process, but divide by 30, instead. For 59, you'd divide by 60, and so on.

When testing for various primes, however, working out all these quotients and remainders can quickly get confusing. Thankfully, it turns out that there's an alternative method, and it's even a little quicker!

Let's start with the test for 19. Instead of dividing by 20 and running through the process described above, split the number into the rightmost number and the rest of it, multiply that rightmost digit by 2, and add that total to the rest of the number. As an example, let's test 285 for divisibility by 19. You'd split 285 up into 28 and 5. Doubling the rightmost number, 5 × 2 = 10, so we'd add that 10 to the rest of the number, 28, to get 38. 38 is a multiple of 19, so 285 must be a multiple of 19! Wolfram|Alpha confirms that 285 is evenly divisible by 19.

For bigger numbers, you may not be sure about the result you got, so you simply run the test on your new total. For example, when testing 2,527 for divisibility by 19, you'd split it up into 252 and 7. Doubling the 7 makes 14, so you'd add 252 + 14 to get 266. Not sure whether 266 is evenly divisible by 19? We run the same test on 266, by splitting it up into 26 and 6. 6 doubled is 12, and 26 + 12 = 38, which we know is a multiple of 19! Therefore, 2,527 is a multiple of 19!

For 29 instead, you would divide up the number in the same way, but multiply the last digit by 3 instead, and then add . Why? Because 29 is right next to 30, and 30 divided by 10 equals 3 (similar to the way we used 2 as a test for 19, because 19 is next to 20). This same pattern holds for the other prime numbers ending in 9. For 59, you'd multiply the rightmost digit by 6 (59 + 1 = 60, 60 ÷ 10 = 6) and add it to the rest of the number. When testing divisibility by 79, you'd multiply the last digit by 8 before adding, and when testing divisibility by 89, you'd multiply the last digit by 9 before adding. Get the idea?

That's great for those numbers, but what about primes which don't end in 9?

*SCALING NUMBERS TO END IN 9* - As also discussed in *The Great Divide*, you can also use this test on numbers which can be scaled up to end in 9.

This approach is particularly hand for primes ending in 3. For example, 13 × 3 = 39. Since 39 is right next to 40, you should quickly realize that you can test for divisibility by 13 by splitting the number as before, multiplying the rightmost number by 4 (40 ÷ 10 = 4), and adding that total to the rest of the number.

Is 507 evenly divisible by 13? 507 split becomes 50 and 7, multiplying 7 by 4 gives us 28, and 50 + 28 = 78. 78 is a multiple of 13, so 507 is evenly divisible by 13!

In the same way, 23 can be tested by multiplying the last digit by 7 and adding it to the rest of the number, because 23 can be scaled up to 69, and 69 is next to 70. Need to test for divisibly by 43, you split the number, multiply by 13 (do you see why?), and add as before.

Just using this approach covers 10 of the 25 prime numbers from 2 to 97. The well-known tests for 2, 3, and 5 add another 3, so you should comfortably be able to test for divisibility by more than half the prime numbers below 100!

Naturally, that brings up the question of how to handle the other half.

*NUMBERS ENDING IN 1* - In my follow-up to *The Great Divide*, I cover a similar technique for numbers ending in 1. The big difference between the ending-in-9 technique and the ending-in-1 technique is that adding is replaced by subtracting.

Let's start by testing for divisibility by 11. The test will begin with the same splitting as before, and since 11 is next to 10, we'll multiply the last digit by 1. However, this time we'll subtract that number from the other numbers.

Is 341 evenly divisible by 11? We split 341 into 34 and 1, multiply 1 by 1, giving us 1, and subtract that from the rest of the number, 34 - 1 = 33, and since we know that 33 is evenly divisible by 11, then so is 341!

I'm sure you have the idea by now. For 31's divisibility test, you'd multiply the rightmost digit by 3 and subtract, for 41's test, you'd multiply by 4 and subtract, and so on.

*SCALING NUMBERS TO END IN 1* - Just as before, this technique also applies to scaling numbers up to end in 1. For testing prime numbers ending in 7, including 7 itself, this is a big help.

The test for 7 begins by realizing that 7 can be scaled up to 21. This tells us that the rightmost number must be multiplied by 2 (remember why?) before subtracting from the rest from the rest of the number.

Is 665 evenly divisibly by 7? Let's use our knowledge of the 21 test to find out. The number is split into 66 and 5, and we double the 5 to get 10. 66 - 10 = 56, and we know 56 is a multiple of 7, so therefore 665 is evenly divisble by 7!

**WIND-UP:** At this point, we've covered the classic divisibility tests for 2, 3, and 5, as well as how to recall and perform easy divisibility tests for every prime number below 100 which ends in 1, 3, 7, and 9 - in other words, every test you need!

You'll need to recall that 9s and 3s require multiplying then adding, and 1s and 7s require multiplying followed by subtracting. When subtracting, note that you can always subtract the larger number from the smaller, which can prevent having to deal with negative numbers.

Since you're performing multiple tests, this won't be the quickest of mental math feats. However, being able to recall and perform tests for such a wide variety of prime numbers is still an impressive, and even useful, feat!

## Calculate Powers of 2 In Your Head!

Published on Sunday, October 26, 2014 in math, mental math, Pi, videos

Earlier this year, I posted about calculating powers of *e* in your head, as well as powers of Pi.

This time around, I thought I'd pass on a method for calculating powers of a much more humble number: 2. It sounds difficult, but it's much easier than you may think!

**BASICS:** For 2^{0} up to 2^{10}, you'll memorize precise answers. For answers to 2^{11} and higher integer powers, you'll be estimating the numbers in a simple way that comes very close.

First, you must memorize the powers of 2 from 0 to 10 by heart. Here they are, along with some simply ways to memorize each of them:

```
Problem Answer Notes
2
```^{0} = 1 Anything to the 0th power is 1
2^{1} = 2 Anything to the 1st power is itself
2^{2} = 4 2^{2} = 2 × 2 = 2 + 2
2^{3} = 8 3 looks like the right half of an 8
2^{4} = 16 2^{4} = 4^{2}
2^{5} = 32 5 = 3 + 2
2^{6} = 64 2^{6} begins with a 6
2^{7} = 128 2^{6} × 2^{1}
2^{8} = 256 Important in computers
2^{9} = 512 2^{8} × 2^{1}
2^{10} = 1024 2^{10} begins with a 10

Take a close look at 2^{10}, which is 1024. It's very close to 1,000, so we're going to take advantage of the fact that 2

^{10}≈ 10

^{3}!

When multiplying 2

^{x}× 2

^{y}, remember that you simply add the exponents together. For example, 2

^{3}(8) × 2

^{7}(128) = 2

^{7 + 3}= 2

^{10}(1024). Similarly, you can break up a single power of 2 into two powers which add up to the original power, such as 2

^{9}(512) = 2

^{6 + 3}= 2

^{6}(64) × 2

^{3}(8).

**TECHNIQUE:**We'll start with 2

^{15}as an example.

Start by breaking up the given power of 2 into the largest multiple of 10 which is equal to or less than the given power, and multiply it by whatever amount is leftover, which will be a number from 0 to 9.

Using this step, 2

^{15}becomes 2

^{5 + 10}, which becomes the problem 2

^{5}× 2

^{10}.

For an powers from 0 to 9, you should know by heart, so you can convert these almost instantly. In the example problem we've been doing, we know that 2

^{5}is 32, so the problem is now 32 × 2

^{10}.

Now we deal with the multiple of 10. For every multiple of 10 involved, you can replace 2

^{10}with 10

^{3}. With our problem which is now 32 × 2

^{10}, there's only a single multiple of 10 in the power, so we can replace that with 10

^{3}. This turns our current problem into 32 × 10

^{3}.

At this point, it's best to represent the number in scientific notation. In this feat, that simply refers to moving the decimal point to the left, so that the left number is between 0 and 10, and then adding 1 to the power of 10 for each space you moved the decimal. Converting to scientific notation, 32 × 10

^{3}becomes 3.2 × 10

^{4}.

That's all there is to getting our approximation!

How close did we come? 2

^{15}= 32,768, while 3.2 × 10

^{4}= 32,000. I'd say that's pretty good for a mental estimate!

**EXAMPLES:**Over 6 years ago, I related the story of Dr. Solomon Golomb. While in college, he took a freshman biology class. The teacher was explaining that human DNA has 24 chromosomes (as was believed at the time), so the number of possible cells was 2

^{24}. The instructor jokingly added that everyone in the class knew what number that was. Dr. Golomb immediate gave the exact right answer.

Can you estimate Dr. Golomb's answer? Let's work through the above process with 2

^{24}.

First, we break the problem up, so 2

^{24}= 2

^{4 + 20}= 2

^{4}× 2

^{20}.

Next, replace the smaller side with an exact amount. In this step, 2

^{4}× 2

^{20}becomes 16 × 2

^{20}.

Replace 2

^{10x}with 10

^{3x}, which turns 16 × 2

^{20}into 16 × 10

^{6}.

Finally, adjust into scientific notation, so 16 × 10

^{6}becomes 1.6 × 10

^{7}.

If you know your scientific notation, that means your estimated answer is 16 million. Dr. Golomb, as it happened, had memorized the 1st through 10th powers of all the integers from 1 to 10, and new that 2

^{24}was the same as 8

^{8}, so he was able to give the exact answer off the top of his head: 16,777,216. 16 million is a pretty good estimate, isn't it?

Below is the classic

*Legend of the Chessboard*, which emphasizes the powers of 2. In the video, the first square has one (2

^{0}) grain of wheat placed on it, the second square has 2 (2

^{1}) grains of wheat on it, with each square doubling the previous number of grains.

The 64th square, then, would have 2

^{63}grains of wheat on it. About how many is that? I'm going to run through the process a little quicker this time.

Step 1: 2

^{63}= 2

^{3 + 60}= 2

^{3}× 2

^{60}

Step 2: 2

^{3}× 2

^{60}= 8 × 2

^{60}

Step 3: 8 × 2

^{60}≈ 8 × 10

^{18}

While 2

^{63}is 9,223,372,036,854,775,808, our estimate of 8,000,000,000,000,000,000 works.

**TIPS:**If you're really worried about the error, there is a way to improve your estimate. Percentage-wise, the difference between 1,000 (10

^{3}) and 1,024 (2

^{10}) is only 2.4%. So, for every multiple of 10 to which you take the power of 2 (or every power of 3 to which you take 10), you can multiply that by 2.4% to get a percentage difference. You can then multiply that percentage difference by your estimate to improve it.

Just above, we converted 2

^{63}into 8 × 10

^{18}. Since we started with six 10s, our percentage difference would be 6 × 2.4%, or 14.4%. In other words, our estimate of 8 × 10

^{18}could be made closer by adding 14.4% to 8.

Assuming your comfortable with doing percentages like this in your head, 8 increased by 14.4% is 8 + 1.152 = 9.152, so our improved estimate would be 9.152 × 10

^{18}. Considering the actual answer is roughly 9.223 × 10

^{18}, that's quite close!

Practice this, and you'll have an impressive skill with which to impress family, friends, and computer geeks!

## 100 Years of Martin Gardner!

Published on Tuesday, October 21, 2014 in fun, magic, Martin Gardner, math, mental math, puzzles, videos

*“Martin has turned thousands of children into mathematicians, and thousands of mathematicians into children.”* - Ron Graham

100 years ago today, Martin Gardner was born. After that, the world would never again be the same.

His life and his legacy are both well represented in David Suzuki's documentary about Martin Gardner, which seems like a good place to start:

As mentioned in the snippets last week, celebrationofmind.org is offering *31 Tricks and Treats* in honor of the Martin Gardner centennial! Today's entry features a number of remembrances of his work in the media:

Scientific American — “A Centennial Celebration of Martin Gardner”There are quite a few other ways to enjoy and remember the work of Martin Gardner, as well. The January 2012 issue of the

Included in the above article is this quiz: “How Well Do You Know Martin Gardner?”

NYT — “Remembering Martin Gardner”

Plus — “Five Martin Gardner eye-openers involving squares and cubes”

BBC — “Martin Gardner, Puzzle Master Extraordinaire”

Guardian — “Can you solve Martin Gardner's best mathematical puzzles?”, Alex Bellos, 21 Oct 2014

Center for Inquiry — “Martin Gardner's 100th Birthday”, Tim Binga

*College Mathematics Journal*, dedicated entirely to Martin Gardner, is available for free online! The Gathering 4 Gardner YouTube channel, not to mention just searching for Martin Gardner on YouTube, are both filled with enjoyable treasures to be uncovered.

Here at Grey Matters, I've written about Martin Gardner quite a few times myself, as I have great respect for him. Enjoy exploring the resources, and take some time to remember a man who has brought joy, wonder, and mystery to the world over the past 100 years.

## Even More Quick Snippets

Published on Sunday, October 12, 2014 in Martin Gardner, math, mental math, puzzles, Scam School, self improvement, videos

It's time for October's snippets, and all our favorite mathematical masters are here to challenge your brains!

• I'm always looking for a good mathematical shortcut, in order to make math easier to learn. More generally, I'm always looking for better ways to improve my ability to learn. I was thrilled with BetterExplained.com's newest post, *Learn Difficult Concepts with the ADEPT Method*.

ADEPT stands for **A**nalogy (Tell me what it's like), **D**iagram (Help me visualize it), **E**xample (Allow me to experience it), **P**lain English (Let me describe it in my own words), and **T**echnical Definition (Discuss the formal details). This is a great model for anyone struggling to understand anything challenging. This is one of those posts I really enjoy, and want to share with as many of you as I can.

• If you enjoyed Math Awareness Month: *Mathematics, Magic & Mystery* back in April, you'll love the *31 Tricks and Treats for October 2014* in honor of the 100th anniversary of Martin Gardner's birth! Similar to Math Awareness Month, there's a new mathematical surprise revealed each day. It's fun to explore the new mathematical goodies, and get your brain juices flowing in a fun way!

• Over at MindYourDecisions.com, they have a little-seen yet fun mental math shortcut in their post *YouTube Video – Quickly Multiply Numbers like 83×87, 32×38, and 124×126*. As seen below, it's impressive, yet far easier than you might otherwise think:

They've also recently posted three challenging puzzles about sequence equations that you might want to try.

• If that's not enough, Scam School's latest episode (YouTube link) at this writing also involves three equations. If you have a good eye for detail, you may be able to spot the catch in each one before they're revealed:

That's all for this October's snippets, but it's more than enough to keep your brain puzzled through the rest of the month!

## Convert Decimal to Any Base 2 - 9

Published on Sunday, October 05, 2014 in fun, math, mental math, self improvement, videos

About 2 years ago, I posted about Russian/Egyptian multiplication, and included a technique for mentally converting decimal (base 10) into binary (base 2).

Recently, Presh Talwalkar covered this same technique on his *Mind Your Decisions* blog. I've only just realized that with a little modification, this technique can be used to quickly and mentally convert decimal to any base 2 through 9!

We'll use the *Mind Your Decisions* binary conversion video as a starting point. It's less than 3 minutes long, so it's a quick study:

In both my original *Power of 2* post and the above video, the idea of ignoring the remainder is emphasized. Funnily enough, changing the technique to focus on the remainder makes this basic idea much more usable. If you remember division problems with answers like, “22 ÷ 6 = 3 remainder 4”, that's the type of division we'll be using in this post.

The first step is simply to take the given number and divide it by whatever base you're using, so that you have a quotient and a remainder. For a starting example, we'll convert the decimal number 84 into base 5. 84 ÷ 5 = 16 (the quotient), remainder 4.

The second step is to write down the remainder. In our example, we'd simply write down the 4.

Step 3 is to divide the quotient by the base again. This time, we'd work out 16 ÷ 5 = 3 remainder 1.

Step 4 is to write down this remainder to the immediate left of the previous remainder. Writing down the 1 to the immediate left of the 4 gives us 14.

Repeat steps 3 and 4 until you get a quotient of 0, at which point, you've got your answer! Finishing up our example, we'd use our current quotient of 3, divide that by 5, getting an answer of 0 remainder 3, write the 3 down to the left of the previous remainders, giving us 314. Since our quotient is 0, we also know we're done! Checking with Wolfram|Alpha, we see that 84 in base 5 is indeed 314!

**TIP #1:** Once your quotient is a number less than your base, you can simply write that to the left of the remainders and know you're done. In the above example, once we got down to 3, and we realize this is less than 5, we know this is the final step. Because of this, we can simply write the 3 down and stop.

In short, as long as you're given a decimal number and a base by which you're comfortable dividing that number, you can convert that number to that base in your head with little trouble. Not surprisingly, knowing division shortcuts and divisibility rules can be of great help here.

What about 147 (in base 10) to base 4? As long as you realize that the closest multiple of 4 is 144, and that you can handle 144 ÷ 4 in your head, the rest of the conversion shouldn't be a problem. 147 ÷ 4 = 36, remainder 3. Write down the 3, and then work with 36. 36 ÷ 4 = 9, remainder 0, so write the 0 to the left of the 3 (03), and work with 9. 9 ÷ 4 = 2, remainder 1. Write down the 1 to the left of the previous remainders (103). Tip #1 above tells us that, since 2 is less than 4, we can just write down that 2 to the left of the other numbers (2103) and know we're done. Sure enough, 147 in base 4 is 2103!

**TIP #2:** If the given number is less than the square of the base to which you're converting, you can do everything in a single step. All you have to do is work out the quotient and the remainder, write the quotient to the left of the reminder, and you're done! For example, what is 59 in base 8? 59 ÷ 8 = 7 remainder 3. Write down the 3 as before. Thanks to tip #1, we know that we can write the quotient down to the left, since 7 is less than 8, so we just write the 7 down next to it!

For base 8, this will work for any number less than 8 × 8, or 64. Similarly, for base 5, this will work for any number less than 25 (5 × 5), and so on. 44 in base 7? 44 ÷ 7 = 6 remainder 2, so we can quickly give the answer as 62!

Being able to convert to base 2 and base 8 in your head can be a great asset when working with computers. Practice this skill and have fun with it. You'll not only have a useful skill, but something with which to amaze and amuse others, as well!

## How To Instantly Convert Weeks to Minutes

Published on Sunday, September 21, 2014 in calendar, fun, math, mental math

A little over a year ago, I teased Grey Matters readers with a mystery skill. First, they had to learn to easily multiply by 63, then learn how to easily multiply by 72. The skill itself was revealed to be how to roughly convert any whole number of years into seconds!

In this post, you'll learn a similar skill: how to convert weeks into minutes instantly!

Back in the days before computers and calculators, this was a popular feat among entertainers who performed as human calculators. It was quick and direct to perform, yet was highly impressive to audiences.

One week has 7 days, and each day has 24 hours. Every hour, of course, has 60 minutes, so if we multiply out 1 week × 7 days/week × 24 hours/day × 60 minutes/hour, we get 10,080 minutes in a week. The number 10,080, as it happens is very easy to multiply by almost any number of weeks. If you keep the number of weeks at or below 124 (about 2.37 years), the numbers are even easier to work out.

**STEP 1:** Ask for any number of weeks less than 2 years (104 weeks). As an initial example, we'll say an audience member gave the number 36.

**STEP 2:** Write down the number they just gave you. In our example, you'd write 36.

**STEP 3:** Multiply this number by 8 in your head, and write this result to the immediate right of the first number you wrote. This is simpler than it sounds; all you have to do is double the number 3 times. For 36, doubling once gives you 72, doubling a second time gives you 144, and doubling a third times gives you 288. Writing 288 next to the 36 you wrote earlier gives you 36288.

** NOTE:** In step 3, it's very important to always treat the answer as a 3-digit number. For weeks from 13 to 104, it will be, but for weeks from 2 to 12, it will be a 2-digit number. You can change this into a 3-digit number simply by adding a 0 to the left of it. If you're given 7 weeks in step 1, you write down the 7 as in step 2, then multiply 7 × 8 to get 56, which becomes 056. You would write 056 as your step 3 answer, giving 7056, and then continue with step 4.

**STEP 4:**Write a zero to the immediate right of the other numbers, add commas where appropriate, and you're done! In our example, we add the zero to the right, giving us 362880. With commas, that result is 362,880. This means that there are 362,880 minutes in 36 weeks!

With a little practice, you'll be astounded as to how quickly you can pick this impressive skill up. You can quiz yourself by having Wolfram|Alpha give you a random number of weeks from 2 to 104, and then use it to verify whether you've worked out the correct answer.

**HANDY BONUS TIP:**You can make this more impressive for an audience by having someone with a calculator verify this in a long, drawn-out manner. Tell them to put in the number of weeks given, then multiply by 7 for the number of days in a week, then multiply by 24 hours in a day, and then multiply by 60 minutes in a week. Multiplying it out the long way makes this feat seem more difficult, as you're hiding the simple 10,080 conversion factor.

Try it out and amaze your friends!

## Days and Knights

Published on Sunday, September 14, 2014 in calendar, fun, Knight's Tour, puzzles, software

As you can probably tell from this recent post and this recent post, I've spent quite a bit of time thinking about the Knight's Tour lately.

These thoughts have reminded of a different type of Knight's Tour puzzle. This unusual variation involves moving the knight around a calendar.

It was 4 years ago, during September or October, that I was looking for blog post inspirations and ran across a thread on the XKCD forums, titled “Knight's Tour revamped”, which suggested playing the Knight's Tour on a calendar.

There was an added challenge, however: With your starting square being considered as move #1, how many dates could you land on that were the same as the move number? For example, if move #1 started on the 1st of the month, both the move number and the date would be 1.

As you can see in the original thread, the original poster used a July 2010 calendar and managed to find a complete Knight's Tour on which the 2nd, 6th, 11th, and 23rd moves landed on the dates of the 2nd, 6th, 11th, and 23rd respectively. Not surprisingly, it was Jaap of Jaap's Puzzle Page who found an 8-match solution.

I filed this in the back of my mind, but never really did anything until I ran across the *Solving the Knight’s Tour on and off the Chess Board* post which I mentioned last week. I liked the basic idea of being able to input a shape, and have the computer work out the tour, and especially the idea of using it to work out the XKCD forum's calendar challenge.

With a little knowledge of Java and graph theory under my belt, I managed to work out a program to solve it. For my fellow Java programmers, here's the main portion of my program, and here's the KnightsTour class I wrote to support it. Most of the hard work is done by lines 590 to 749. Those and lines 20 to 23 can removed if you're interested more in the general Knight's Tour than the particulars of the calendar challenge.

One of the first things I did, not surprisingly, was to find out how many day-to-move matches I could find in this month's calendar. I also found 8, all of which are highlighted below in red:

Yes, I've gone through every possible calendar, starting on every possible date, and learned quite a few interesting things in the process:

• Due to the fact that the number of days in a week (7) is odd, and the fact that the knight always moves an odd number of spaces (3), this means that a Knight on a calendar will always move from an odd date to an even date, and vice versa (just like what your teacher taught you about adding even and odd numbers). This, in turn, means that it's impossible to get ANY date matches if move #1 begins on an even-numbered date, as all the odd moves will land on even dates, and vice-versa.

• The above fact also means that if you start on an even date in a month with an odd number of days (29 or 31), you won't be able to complete a Knight's Tour.

• Yes, Jaap's 8-match path is the best one possible for July 2010 in particular. It also happens to be the only way to get 8 date-to-move matches in a Knight's Tour of a 31-day month beginning on a Thursday.

• Given any random month and year, you can always find a complete Knight's Tour and at least 6 date-to-move matches. Surprisingly, these minimum matches aren't found in the shortest months, as you may expect. With 30- and 31-day months starting on a Saturday, as well as 31-day months beginning on a Friday, 6 is the highest number of date-to-move matches you'll be able to find.

• There are months with 9 date-to-move matches, but none with more than that. 9 date-to-move matches can be found in a 29-, 30-, or 31-day month starting on a Tuesday or a Wednesday. In a 29-day month starting on a Thursday, or a 31-day month starting on a Monday, you can also find 9 date-to-move matches. You can often find more than 1 way to get to these matches, as well.

As it happens, next month (October 2014) is a 31-day month starting on a Wednesday, and here's one of the 3 possible ways to get 9 date-to-move matches:

I chose this one simply for the elegance of the column containing 16-23-30 and the diagonal containing 12-20-28. I also find it interesting that so many powers of 2 have date-to-move matches (2-4-8-16).

For the more math-inclined geeks, I'll wind this post up with all the maximum number of matches I've found, including the dates on which they start:

```
28-day months, starting on:
Sunday: 7 matches, beginning from the 1st or 23rd
Monday: 7 matches, beginning from the 1st or 21st
Tuesday: 8 matches, beginning from the 25th
Wedneday: 8 matches, beginning from the 1st
Thursday: 8 matches, beginning from the 1st or 5th
Friday: 8 matches, beginning from the 1st or 15th
Saturday: 7 matches, beginning from the 23rd or 25th
29-day months, starting on:
Sunday: 7 matches, beginning from the 1st
Monday: 7 matches, beginning from the 1st or 27th
Tuesday: 9 matches, beginning from the 25th
Wedneday: 9 matches, beginning from the 1st or 11th
Thursday: 9 matches, beginning from the 1st
Friday: 7 matches, beginning from the 1st, 5th, 27th, or 29th
Saturday: 7 matches, beginning from the 1st
30-day months, starting on:
Sunday: 7 matches, beginning from the 7th or 23rd
Monday: 8 matches, beginning from the 27th
Tuesday: 9 matches, beginning from the 25th
Wedneday: 9 matches, beginning from the 11th
Thursday: 8 matches, beginning from the 1st
Friday: 7 matches, beginning from the 1st or 7th
Saturday: 6 matches, beginning from the 1st or 25th
31-day months, starting on:
Sunday: 8 matches, beginning from the 23rd
Monday: 9 matches, beginning from the 7th or 31st
Tuesday: 9 matches, beginning from the 1st, 23rd, or 25th
Wedneday: 9 matches, beginning from the 7th
Thursday: 8 matches, beginning from the 5th
Friday: 6 matches, beginning from the 1st, 5th, 7th, or 31st
Saturday: 6 matches, beginning from the 1st, 23rd, 29th, or 31st
```