What’s the probability that an n-digit palindrome chosen at random is divisible by 11?

James Tanton asked in a tweet: what’s the probability that an n-digit palindrome chosen at random is divisible by 11?

This depends heavily on $n$. In particular, if $n$ is even, the probability is 1. We can notice that $11, 1001, 100001, \cdots$ are each multiples of 11 (these are $11 \times 1, 11 \times 91, 11 \times 9091, \cdots$) and write a palindrome as a sum of multiples of these. For example
52744275 = 5 \times 10000001 + 2 \times 10 \times 100001 + 7 \times 100 \times 1001 + 4 \times 1000 \times 11
is a multiple of 11.

Let’s also consider the case where the digit count is odd. This is a bit trickier, and Mike Lawler (https://mikesmathpage.wordpress.com/2015/01/20/a-nice-divisibility-rule-problem-from-james-tanton/) and his younger son worked out that out of the 900 palindromes with five digits, 82 are divisible by 11.. In the three-digit case it’s not hard to find the full list of palindromes divisible by 11, and there are eight of them, from a total of 90. they’re 121, 242, 363, 484, 616, 737, 858, 969. There’s an obvious pattern here – consecutive elements of the list differ by 121, except when they don’t (going from 484 to 616).

So let’s go back to the notation and say we’re consider an n-digit palindrome where n = 2k+1. We want to iterate over possible “first halves” of the palindrome and figure out what the middle digit should be: we’re answering questions like “what five-digit palindrome starting with 28 is divisible by 11?” There is at most one (2k+1)-digit palindrome with any first k-digit number which is divisible by 11. Consider the numbers
28082, 28182, \ldots, 28982.
Each of these differs by 100 from the last one, which is one more than a multiple of 11, so when we reduce mod 11 we get
k, k+1, \ldots, k+9
which are all different. Unless 28082 happens to be one more than a multiple of 11, one of these is a multiple of 11. As it turns out, 28082 is one {\it less} than a multiple of 11, and 28182 is a multiple of 11: 28182 = 11 \times 2562.

So there is either zero or one palindrome of each of the forms 10x01, 11x11, 12x21, \ldots, 99x99. When is there no such palindrome? Observe that, for example,
12000 - 21 = (10000 + 2000) - (20 + 1) = (10000 - 1) + 10 \times 2 \times (100 - 1) $
and so 12000 and 21 differ by a multiple of 11. So 12x21 and 24x00 are congruent mod 11. To get 24x00 to be a multiple of 11 we need 24x (that is, 240 + x) to be a multiple of 11 – so we take x = 2. Indeed, 12221 is a multiple of 11, with 12221 = 11 \times 1111.

But consider, for example, the number 27x72. This is congruent to 54x00 mod 11, and is a multiple of 11 if and only if 54x is – but none of 540, 541, \ldots, 549 are divisible by 11. Working backwards, this can be traced back to the fact that 27 \equiv 5 \pmod 11.

So the five-digit palindromes divisible by 11 are in one-to-one correspondence with the integers in $10, 11, \ldots, 99$ which are not congruent to 5 mod 11 — of which there are 90 - 8 = 82. This generalizes to (4k+1)-digit palindromes: there are 8182 nine-digit palindromes divisible by 11 (out of 90000 nine-digit palindromes), 818182 thirteen-digit palindromes (out of , and so on. These look an awful lot like the decimal expansion of 9/11, and in fact

For palindromes with three, seven, eleven, … digits the arithmetic works out a bit differently – but the final result can be expressed in this form: the number of (2k+1)-digit palindromes divisible by 11 is the closest integer to (9 \times 10^k)/11. The probability that Tanton asked for is almost exactly 1/11 — the same as the probability that a random integer is divisible by 1/11. The fact that the palindrome constraint has no effect is… obvious? Totally surprising. To be honest I don’t know.

Advertisements

5 thoughts on “What’s the probability that an n-digit palindrome chosen at random is divisible by 11?

  1. Hrm I thought about this for a moment and indeed it may be “obvious” that it’s exactly 1/11… It seems that for every number that’s divisible by 11, the number written backward is also divisible by 11. I think the reverse is also true, if a number is not divisible by 11, the number written backward is also not. Its too long ago I did anything with number theory and too late for me to manage a proof of that, I’ll leave it to you 😉
    Anyway, if the above is indeed true, you can construct a simple N to N mapping: each number maps to a palindrome by mirroring it, eg 132 maps to 132231, and either both number are divisible by 11 or both numbers are not divisible by 11.
    If this is indeed all true, it seems that you can do the same for any other number by writing everything in a different base, eg the chance of a palindrome being divisible by 13 should be 1/13th (because 13 is 11 in base 12)..? Interesting!

    1. Hrm thinking some more it is not entirely correct, because some palindromes are divisible by 11 even though it’s two halves are not, eg 119911. Maybe the line of thought can still be fixed though..

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s