Will We Get to a Palindrome?
Here is a palindrome problem by Nazar Agakhanov from the All-Russian Mathematical Olympiad, 1996:
Can the number obtained by writing the numbers from 1 to n, one after another, be a palindrome?
Of course, we should assume that n > 1.
When I give this problem to my friends, they immediately answer, “No, of course not.” The reasoning is simple. The last 9 digits of this palindrome should be 987654321 β all different digits. The earliest you can get these digits at the end of your string 1 to n, is when your number n is actually 987654321. By that time your string of digits is really huge. If we take a random number with 2k digits, then the probability of it being a palindrome is 10(-k). There is no reason to think that writing consecutive integers increases the probability of finding a palindrome. So the probability of hitting a palindrome is so low, that you can safely answer, “No, of course not.”
After confidently saying “no”, my friends usually stop thinking about the problem altogether. Only my friend David Bernstein suggested a simple solution for this problem. You can try to find the proof, but I do not insist that you do. I am about to give you many other fun problems to solve, and you can choose which ones you want to think about.
Naturally, we can replace the sequence of natural numbers in the Agakhanov’s problem with any sequence. So, one problem becomes 160,000 different problems when you plug all current sequences from the Online Encyclopedia of Integer Sequences into it.
For some periodic sequences every concatenation you create is a palindrome. For example, for the sequence of all zeroes, every set of the first n terms is a palindrome. More interestingly, you can think of an increasing sequence such that any first n terms comprise a palindrome, as we see in the sequence of repunits: 1, 11, 111, 1111, etc. Can you think of other sequences like this?
For some sequences, not every concatenation you create is a palindrome, but you can obtain an infinite number of palindromes. One example, suggested by Sergei Bernstein, is the sequence a(n) of the last digit of the greatest power of 2 that divides n. Can you think of other sequences like that?
For some sequences only the initial term itself is a palindrome. Beyond that you can’t obtain a palindrome by concatenating the first n terms. For a few of those sequences, this fact is easy to prove. Take, for example, the sequence of powers of ten, or the sequence of squares, or the sequence of prime numbers. Can you think of other similar sequences?
There are many sequences that do not produce a palindrome beyond the first term, even if you try many times. I suspect that they do not, in fact, ever produce a palindrome, but I have no clue how to prove that. I have in mind the sequence of the digits of Ο. Can you suggest other sequences like that?
Instead of solving the initial problem, I gave you a variety of other problems. My last challenge for you is to find other sequences that can replace the sequence of natural numbers in the Agakhanov’s problem so that the problem becomes solvable and the solution is interesting.
Share:
Alien:
The sequence 1-2-3 in binary is a palindrome…. 1 10 11 – it’s not base 10 but it is a lot easier to get a palindrome with just 2 digits π
28 August 2009, 12:24 amAustin:
Here are two extensions of Nazar Agakhanov’s problem:
1. Suppose we write the number 1 as many times as we wish (but at least once), then we write the number 2 as many times as we wish (but at least once), and so on up to the number n. Can the concatenation of all of these numbers (e.g., 1122234444455) be a palindrome? (Assume n>1.)
2. Let a_1 < a_2 < a_3 < … be an increasing sequence of natural numbers. Let b_n be the concatenation of the first n entries of that sequence. If there are infinitely many n such that b_n is a palindrome, does it follow that the sequence (a_i) has density approaching zero?
I know the answer to #1, but #2 should be a real test for your overconfident friends’ intuition. π
28 August 2009, 3:54 pmsander P.:
You can try it with the sequence of all the palindromes that exist. And you can also try mixing up the elements in different combinations.
3 September 2009, 9:26 amTanya Khovanova’s Math Blog » Blog Archive » Papaya Words and Numbers, jointly with Sergei Bernstein:
[…] is a strange puzzle that was inspired by the palindrome problem. Suppose you have a sequence of words in some alphabet with the initial term a and all the other […]
26 September 2009, 8:49 pm