Anna loves multiples of 11. Bibi is not quite so keen. One day Anna is flipping idly through the yellow pages (full of 10-digit numbers including area codes), and notices that every number seems to have the interesting property that it is either a multiple of 11, or convertible to a multiple of 11 by altering a single digit. For instance, 999-867-5309 can be changed (by altering the first digit) to 5998675309, which is a multiple of 11.

 Anna challenges Bibi: “Pick any 10-digit number in the phone book. I’ll bet I can change it to become a multiple of 11 by altering at most one digit.”

Is Anna right?

Follow-up: Anna confidently states “Now pick a number with any number of digits. I’ll bet I can still do the same thing.” Now is Anna right? Can you find a number Bibi can pick that could foil Anna? If so, what is the smallest number (positive integer) Bibi could pick that would foil Anna? Can you find and characterize the entire sequence of numbers with this property?

—

Solution

Rephrased, the question asks whether every positive integer has a decimal Hamming distance <= 1 to a multiple of 11. And if not, what are the counterexamples?

Divisibility by 11 can be tested by summing even-place and odd-place digits, and seeing if the two sums differ by a multiple of 11. For instance, the number 123456789 can be separated into 1 + 3 + 5 + 7 + 9 = 25, and 2 + 4 + 6 + 8 = 20. These two numbers differ by 5, which is not a factor of 11, therefore 123456789 is not a multiple of 11. Change the leading ‘1’ to a ‘7’, however, and now we have 7 + 3 + 5 + 7 + 9 = 31, which differs from 20 by a multiple of 11. So 723456789 is divisible by 11.

Consider an arbitrary integer of the form 11n + k, where k is in [1 .. 10], thus not divisible by 11. In order to convert this number to a multiple of 11 by changing one digit, then there are four potential operations that could work: we can subtract k from an odd-position digit, add (11 – k) to an odd-position digit, add k to an even-position digit, or subtract (11 – k) from an even-position digit. The catch is that this operation must not carry; e.g. adding ‘3’ to 8′ would carry and affect the next digit over. E.g. if an odd-position digit is k – 1, then either subtracting k or adding (11 – k) will carry. Similarly, if an even-position digit is 10 – k, then either adding k or subtracting (11 – k) will carry.

So for a number Q to satisfy these constraints, we have the following conditions:

Q = 11n + k, for some k in [1 .. 10]

Every odd-position digit is k – 1

Every even-position digit is 10 – k

It’s efficient enough to simply examine every number with a pattern that satisfies the last two constraints (e.g. 5454545), and check its remainder mod 11. It turns out that the first few numbers that satisfy all the constraints, and thus have a decimal Hamming distance of >1 from any multiple of 11 are:

545
27272
1818181
636363636
90909090909
181818181818
272727272727
363636363636
454545454545
545454545454
636363636363
727272727272
818181818181
909090909090
363636363636363
81818181818181818
7272727272727272727
454545454545454545454

And then the sequence repeats, with the pattern extended in increments of 22 digits for each term. Interestingly, if leading 0’s are allowed, the above list can be neatly divided into ten odd-length terms:

545
27272
1818181
636363636
90909090909
0909090909090
363636363636363
81818181818181818
7272727272727272727
454545454545454545454

and ten even-length terms:

090909090909
181818181818
272727272727
363636363636
454545454545
545454545454
636363636363
727272727272
818181818181
909090909090

The leading zeroes result in two of the terms being duplicated, yielding 18 unique terms. And then the pattern repeats, with the recurrence:

a(n) = a(n – 18) * 10^22 + (a(n – 18) % 100) * 101010101010101010101.

Or put another way, for each term, the last two digits can be appended an additional 11 times, yielding a new term; e.g., 545 -> 5454545454545454545454545.

Finally, an open question: the ordering of the odd-length terms, the leading-digit sequence { 5, 2, 1, 6, 9, 0, 3, 8, 7, 4 } appears fairly random. Is there a simple expression that can generate this pattern? (One clue is that the first five digits (52169) plus the last five reversed (47830) equals 99999.)