Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

A palindrome is a number or word that is the same when read forward and backward, for example, “176671” and “civic.” Can the number obtained by writing the numbers from 1 to n in order (n > 1) be a palindrome?

share|improve this question
    
That's why he defined a palindrome as "number or word" –  Hagen von Eitzen Dec 27 '12 at 21:28
    
I covered all bases :) –  fosho Dec 27 '12 at 21:28
    
Maybe I misread. Thought the word "word" was not there initially. –  Thomas Andrews Dec 27 '12 at 21:29
add comment

3 Answers

up vote 5 down vote accepted

No. With $n=1$, we do have a palindrome of course. But for $n>1$ we can clearly exclude the case $n\le 10$. In fact, we need $n\equiv 1\pmod {10}$, as the palindromic string ms must end in "$\ldots 1$". Let $k\ge1$ with $10^k<n<10^{k+1}$. Then there is exactly one position in the assumed palindromic string "$12345\ldots54321$" where "$1\underbrace{0\ldots0}_k1$" occurs: In the absence of leading zeroes, only the two $1$s in this block can be leading digits of some numbers, and since no number has more than $k+1$ digits, indeed both $1$s must be leading digits, i.e. the only position where this pattern occurs is at the number $10^k$ (together with the leading $1$ of $10^k+1$). For a palindrome, such a uniquely occuring subpalindrome must be in the very middle. But it is preceeded by "$\underbrace{9\ldots9}_k$" from $10^k-1$ and followed by "$\underbrace{0\ldots0}_{k-1}1$" as the rest of $10^k+1$, contradicting the palindromic symmetry.

share|improve this answer
add comment

Here's a beginning of the task where the numbers do not have to be in order. Note that a palindrome can have at most one digit which occurs an odd number of times - the centre digit if the number of digits is odd.

Now after 1, you have to have all digits 1-9 - nine digits. If you stop below 100 you will always have an odd number of digits (1-9 plus pairs from the two digit numbers). So you can work on digit parities to reduce the number of cases you have to consider.

share|improve this answer
add comment

The answer is no - there's a variety of ways to prove this. For example, consider the number $k$ in the list with the most 0's, say $m$ of them. Clearly, $k$ must consist of a single digit followed by $m$ 0's, otherwise there would be a number before it with more 0's. Now we have two cases:

  • Case 1: $k$ is the only number with $m$ 0's. Then $k$ must be the middle number in the palindrome, otherwise $k$ does not have a unique number of 0's. However, the resulting concatenation of integers is not a palindrome since the number before $k$ , $(\ldots999)$, is not symmetric with the number after it: $(\ldots00001)$.
  • Case 2: There are multiple numbers with $m$ 0's. Consider the rightmost one, say $k=n\cdot10^m$ for some $n>1$. Then, $k$ is embedded in the palindrome between $((n-1)999\ldots)$ and $((n)00\ldots01)$. Since $k$ is the rightmost appearance of $m$ 0's, the leftmost appearance is thus $(10\ldots0(n))(00\ldots0(n))(99\ldots9(n-1))$. However, this is absurd since the left most appearance is naturally $10^m$.

Therefore, it's impossible for the concatenation of the $n$ integers $1$ through $n$ to be a palindrome.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.