February 2005:
Home | Problem Archive | Past Winners | Number Games | Contact Me
| February 2005: | |
|
A natural number is a palindrome if it remains the same after its digits are reversed. For instance, 505 and 6116 are palindromes. Devise a formula for the number of palindromes that have n digits, where n is a positive nonzero integer. Construct another formula for the number of palindromes between 0 and 10k, where k is a positive nonzero integer. |
|
| Let us consider an example for a 3-digit number. For the hundredth digit, we have 9 choices, from 1 to 9 (0 cannot be the leftmost digit). For the tenth digit, we have 10 choices, because 0 can be within the number. For the unit digit, however, we have no choices, because it has to equal the hundredth digit to make the number symmetric. So there are 9*10 = 90 3-digit palindromes. Take the example of a 4-digit number. For the thousandth digit, we have 9 choices, from 1 to 9 . For the hundredth digit, we have 10 choices, since 0 can be within the number. For the tenth and digit units we have no choice since they have to be the same as the hundredth and thousandth digits respectively to make the number symmetric. Hence, there are 9*10 = 90 4-digit palindromes. As the examples demonstrate, the answer depends on whether n is odd or even. So we construct a formula accordingly. For n = 2m + 1, we have 9*10m palindromes. For n = 2m, we have 9*10m+1 palindromes. Now, we know the number of n-digits palindromes for every n. We need to find how many palindromes there are from 0 to 10k, which is simply the summation of i-digit palindromes from i = 1 to i = k. For k = 2m + 1, the number of palindromes equals 9*(2*100 + 2*101 + ... + 2*10m-1 + 10m) For k = 2m, the number of palindromes equals 9*(2*100 + 2*101 + ... + 2*10m-1 + 2*10m) Topic: Number Theory
| |
| Previous Month | Archive | Next Month |
|---|