[jon.kiparsky]

Here's a fun problem to chew on.

I assert that all 4-digit palindromic numbers are multiples of 11. Can you prove or disprove this assertion?

[sepp2k]

Since the set of 4-digit palindromic numbers is finite (and not even very large), this could easily proven or disproven by exhaustive search, but here's a different approach:

Spoiler

If any number x is divisible by 11 and y-x is divisible by 11, then y is also divisible by 11 (the same is true for any other number than 11, of course, but that doesn't matter here).

All palindromic 4-digt numbers have the form XYYX where X and Y are single digits. If Z is a digit larger than Y, then XYYX - XZZX is equal to 110 * (Z - Y). That number is divisible by 11 because 110 is divisible by 11. So if for any digit X, X00X is divisible by 11, XYYX will also be divisible by 11 for all digits Y. Since 1001 is divisible by 11, we now know that 1YY1 is divisible by 11 for any digit Y.

For any digit X, let Y be X+1. Y00Y - X99X is 11. Thus if X99X is divisible by 11, Y00Y is divisible by 11 (and so is YZZY for any digit Z by the logic of the previous paragraph). So since 1001 is divisible by 11 and 1001 is the smallest 4-digit palindromic number, we can conclude through complete induction that all 4-digit palindromes are divisible by 11).

Generalizing this proof to apply to all n-digit palindromes where n is an even number is left as an exercise for the reader.

[jon.kiparsky]

Nice one, that's exactly the logic I used. But then I started working at it, and I believe it's further provable that this is true for any base b. That is, xFAAF/x11 = xebf exactly.

Oddly enough, this seems to be related to the fact that the digital sum of a multiple of (b-1) in base b always sums to b-1.

[Nikitin]

x*10^3 + y*10^2 + y*10 + x = 11 * (x*91 + y*10)

This post has been edited by Nikitin: 18 April 2013 - 12:45 PM

[rodint]

jon.kiparsky, on 18 April 2013 - 08:37 AM, said:

Here's a fun problem to chew on.

I assert that all 4-digit palindromic numbers are multiples of 11. Can you prove or disprove this assertion?

Let x = a*10^3 + b*10^2 + b*10 + a, where 0 < a,b < 10, a and b are integers.

x = a*1001 + b*110

Since 11|1001 and 11|110, 11|(a*1001 + b*110) for any integer a,b (and specifically for 0<a,b<10)

(This is from rule 7. http://primes.utm.ed...ge/divides.html )

Thus 11|x, which means x is a multiple of 11.

By construction of x, x is any 4-digit palindromic number, which means any 4-digit palindromic number is a multiple of 11.

[Momerath]

While your proof is good, your range is off. It should be 0 < a < 10 and 0 <= b < 10.