2012:01: Winter Study Conundrum: Party Trap!

Ah, memories from the break . . . Dammit, I’m mad! Mom and Dadhave left me to do the civic duty of babysitting my brother Bob fromnoon to nine on seven eves! That was really not on my radar—I would so rather be at my gym! I tried many distractions to keep him entertained, ranging from shouting “Was it a rat I saw?” to begin a fruitless mouse hunt, to having him repaper his racecar to relive holiday gifts. After fielding the question “Do geese see God?” my face was redder than a tomato and I had to ensure that he wouldn’t saypeep for at least 30 whole minutes! Fortunately, brilliance struck. “Yo, bozo boy! I have a game for you!”

Here is the basic tenet: Take a number and ask whether it’s a palindrome (i.e. reads the same forwards as backwards).  If not, reverse the digits and add.  Repeat this process until you get a palindrome.  For example, 48 is not a palindrome, so write 48 + 84 = 132, which is also not a palindrome.  Then write 132 + 231 = 363, which is a palindrome.  We refer to 48 as a 2-step palindrome.

(1)  Some initial stats: Prove that every number between 1 and 50 is either a 0, 1, or 2-step palindrome.

(2)  Increasing the level: Does there exist an n such that every number between 1 and 100 is a k-step palindrome where k is less than or equal to n? (Hint: There is a clue buried within the text!)

(3)  Don’t nod yet! Asking this question for 3-digit numbers is a party boobytrap! Can you guess why?

Now I won some peace and quiet!

Congratulations to Gabor Gurbacs and Jake Levinson for submitting the following correct solutions!

Solution:

(1) [Due to Jake Levinson]: Suppose after one step we get a three-digit number: n + m = 100 + 10a + b, where b = x+y mod 10, and a = b+1. The reversal is 100b + 10a + 1. Adding them yields 100(b+1) + 10(2a) + (b+1).  We claim that if n ≤ 50 then this is actually the correct decimal representation, i.e. b+1 and 2a are both at most 9.  Since n ≤ 50, the sum of the digits is at most 4 + 9 = 13. So b = 1, 2 or 3, and so b+1 < 5 and 2a = 2(b+1) < 10, so the digits are indeed b+1, 2a and b+1 again, which is a palindrome.

(2) [Due to Gabor Gurbacs]: After the first reverse-add process, call it iteration, is applied to the number ab we end up with: N = (10a+b)+(10b+a) = 11(a+b).  Observe that the game is symmetric with respect to reversing the ones and tens digits, and that the number of steps only depends on the sum a + b.  Therefore, any two-digit non-palindromic numbers with digit sum (a+b) ≤ 9 are one-step palindromes, and any two-digit non-palindromic numbers with digit sum (a+b)=11 are one-step palindromes.  Let’s check the case when (a+b)≥10.  After the first iterations, in the place of units we have b=a+b-10 with a remainder of one which carries over to the tens and is added to a. The tens now have the following form: (a+b-10+1), with one carrying over to the hundreds so that the result has the following form: 1(100)+10(a+b-9) +(1)(a+b-10).  For example, when (a+b) = 10, the first iteration yields N1 = (1)(100)+10(10-9)+(10-10) = 110.  Since the resulting number is not a palindrome, reverse N1 again and add. Numerically this means: (1)(100)(10-10)+10(10-9)+(1)(1); call this reversed number N2 with the exact value 11. Finishing the second iteration, adding N1 and N2 we get N3 = 121.  This means that all two-digit non-palindromic numbers with a digit sum 10 are 2-step palindromes.

Using the same remainder carry method, we can show how many iterations are required to turn the number ab into a palindrome when 11 < (a+b) < 18:

(a+b)=12 for 39, 48, 57, 75, 84, 93 which require 2 steps

(a+b)=13 for 49, 58, 67, 76, 85, 94 which require 2 steps

(a+b)=14 for 59, 68, 86, 95 which require 3 steps

(a+b)=15 for 69, 78, 87, 96 which require 4 steps

(a+b)=16 for 79 and 97 which require 6 steps, and finally

(a+b) = 17 for 89 and 98 which actually require 24 steps.  The resulting palindrome is 8813200023188!  (The hint for this part was that there are 24 verbal palindromes embedded in the text of the problem.)

Finally, note that we need not consider (a+b)=18, since the only possible way the digit sum is 18 would be when a=b=9, and 99 is already a palindrome!  Therefore, we may choose n=24.

(3) [Musings by Gabor]: Extending the domain into three digit numbers the carry method works most of the time, except the case of some numbers called the Lychrel numbers. These numbers (132, 196, 295, 394, 493, 592, 689, 691, 788, 790, 879, 887, 978, etc…) do not turn to palindromes after 724,756,966 iterations!!!  (The iteration number has been acquired from the Wolfram MathWorld Palindromic Number Webpage.) No proof has yet been given for whether all numbers will turn into palindromic numbers after repeating the reverse add process, called the 196 algorithm, sufficiently many times. (This problem is a party boobytrap because it remains an open question!)