Car Talk Puzzler

Maple

National Public Radio in the USA carries Car Talk, a humorous phone-in program in which Tom and Ray Magliozzi (Click and Clack, the Tappet Brothers) diagnose and offer solutions for mysterious auto-related maladies. It's an amusing hour on Saturday mornings.

One of the program's segments is a weekly Puzzler, a logic (or other) mental puzzle begging for a solution. On May 21, 2011, my wife and I were driving westward across Michigan, headed for a family visit with our son in Iowa. Our radio picked up the morning's broadcast of Car Talk, during which the following Puzzler caught our attention. The link will take you to the exact wording. Here's a synopsis.

A six-digit odometer shows a palindromic number. The car it's in is driven no more than an hour, and again the odometer shows a palindromic number. How far was the car driven?

When I described this puzzle to a colleague, he immediately suggested the successive palindromes 11 and 22, etc. However, a six-digit odometer would display 000011, and that probably shouldn't be considered a palindrome. So, to a mathematician the problem is "What are all the six-digit palindromes (no leading zeros), and what are the successive differences?

As my wife was driving, I was free to think how I might use Maple to get a list of all such palindromes, wondering if, perhaps, the numtheory package had a "palindrome" command. My wife, a psychiatric nurse, who clearly did not deal with logical intellects in her professional career, shortly announced "It has to be 11. If the odometer started at 199991, eleven additional miles would bring it to 200002." Believe me, I didn't even want to know how she did this. I just sat back and marveled at the mate I had picked more than 40 years ago.

But as soon as I could get to a Maple session, I did, indeed, list all the six-digit palindromes, and discovered that adjacent palindromes differed by 11, 110, or 1100. Since it is unlikely that the car in question traveled 110 miles in an hour, the answer to the Puzzler had to be 11. And it was. (Click the link for the solution as presented by Tom and Ray.)

Here's how I did the calculations. The first thing I did was to satisfy myself that Maple had no built-in facility for generating palindromes, so I needed a representation of a six-digit palindrome. This I took as  or

Hence, all the six-digit palindromic numbers, sorted from smallest to largest, are in the list :

The first few members are , but the whole list contains 900 members, as

=

shows. Now the differences between successive palindromes is found with

a list of length  = , as expected. However, the distinct members of  are

=

and in fact, the first time the difference between successive palindromes is 11 is

=

Is a gap of 11 unique? Just how prevalent is such a difference between two six-digit palindromes? In Table 1, the first column lists the index  telling where in the sorted list  two adjacent palindromes differ by 11, and the second and third columns give the adjacent palindromes.

I can't help but note the first pair in the list! (I have no idea how she did it. She doesn't knit, but avidly solves Sudoku puzzles of all types, and is better at it than I am.)

 [100, 199991, 200002] [200, 299992, 300003] [300, 399993, 400004] [400, 499994, 500005] [500, 599995, 600006] [600, 699996, 700007] [700, 799997, 800008] [800, 899998, 900009]
Table 1: Successive palindromes that differ by 11

From Table 1 is should also be clear that because of the gap between the pairs, there aren't three successive palindromes each pair of which differ by 11. The Puzzler can be solved by searching just adjacent palindromes.