Correct answers were received from Joseph DeVincentis, Larry Carter, Jim Tilley, Ken Leone, Patrick LoPresti, James Brawner, Jim Guilford, Stephen Meskin, John Guilford, Ken Schilling, and Alberto Vieira Ferreira.
For the problem stated, here's how I did it: a quick computation led to the discovery that the sequence begins 545, 27272, 1818181. Then I tried pairs of digits to start and found that 636363636, 90909090909, and 0909090909090 work. But this last has 12 digits because of the leading 0.
Many readers found the smallest answer, which is 181818181818. Then one can give a short proof that it works, as done by Ken Schilling: "The smallest such number is n = 181818181818 (i.e., 6 repetitions of 18). To see that this number has the desired property, allow the digits zero through ten (while still interpreting the number in base ten). For i = 1, ..., 12, there is exactly one choice of a digit to replace digit i in n to make a multiple of 11, and in each case the required digit is 10."
One can find ALL the numbers with the given property. The set falls into two families according to the parity of the number of digits. The proof presented here is by James Guilford. The odd case is as follows (though 0909090909090 is a 12-digit integer), with periodic repetition to infinity. Note the extra lengthening at 54545454...
545
27272
1818181
636363636
90909090909
0909090909090
363636363636363
81818181818181818
7272727272727272727
454545454545454545454 (next one is 25 digits, skipping 23 = 1 (mod 11))
5454545454545454545454545
272727272727272727272727272
63636363663636363663636363636
...
The evens are as follows (though 090909090909 is an 11-digit number), with periodic repetition to infinity.
090909090909
181818181818
272727272727
363636363636
454545454545
545454545454
636363636363
727272727272
818181818181
909090909090 (12 digits, 12 = 1 mod 11)
0909090909090909090909090909090909
1818181818181818181818181818181818 (34 digits, 34 = 1 (mod 11))
2727272727272727272727272727272727... (next group is at 56 digits)
Therefore, the smallest answer to the question is 181818181818.
Details: All arithmetic in the following is modulo 11. If ABCD is a valid solution, then ABC0 = 1 (mod 11). For if not, one could place a digit in this position making the result 0 (mod 11). For the same reason, AB0D must be 10 or -1 (mod 11). And likewise A0CD is 1, 0BCD is -1, and similarly for longer numbers.
So if N is the digit count, we can construct N linear equations where the coefficient matrix columns are alternating +1 and -1, except for the reverse diagonal, which is 0. This, times the solution expressed as a vector, must be alternating +1 and -1.
For example, if N = 3 and the number was ABC, we would have:
A − B = 1
A + C = -1
-B + C = 1
If N = 4 and we have ABCD, the system is
-A + B − C = 1
-A + B + D = -1
-A − C + D = 1
+ B − C + D = -1
In the odd case, subtracting the first from the second gives B + C = -2 = 9 and subtracting the third from the second we get A + B = 9. In general, this gives that the sum of any two adjacent digits must be 9. Therefore, the form of any solution is ABAB...ABA, where A + B = 9. The even case is similar, yielding ABAB...AB where A + B = 9.
Case 1. N odd: A solution exists unless N = 1 (mod 11). The solution is of the form ABAB...ABA. Using the system's first equation, we get A − B + A − B + ... + A − B = 1. This results in (2A − 9)(N − 1)/2 = 1 or (2A + 2)(N − 1)/2 = 1 or (A + 1)(N − 1) = 1. If N = 1 (mod 11), this has no solution. Otherwise, let A = (1/(N − 1)) − 1 and B = 9 − A, giving the solution ABAB...ABA.
As N goes through 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 25, 27, ... (23 is missing because of the 1 (mod 11) exception), A varies through the mod-11 inverse of 2, 4, 6, 8, 10, etc., and so A = 5, 2, 1, 6, 9, 0, 3, 8, 7, 4, 5, 2, 1,..., yielding initial pairs of 54, 27, 18, 63, 90, 09, 36, 81, 72, 45, 54,... . For example, if N = 3, then A = (1/2 − 1) = 6 − 1 = 5 or -(A + 1)N + A + 1 + 1 = 1 or (A + 1)(N − 1) = 0.
If N! = 1 (mod 11), this gives A = -1 = 10, which is not a valid digit; if N = 1 (mod 11), then any digit A satisfies the equation. So we can let N = 12 and get the solutions listed above, or N = 34 to get
0909090909090909090909090909090909, 1818181818181818181818181818181818, etc.
Therefore the smallest solution to the problem has 12 digits and is 181818181818.
The set of digit counts N for solutions is: 3, 5, 7, 9, 11, 12, 13, 15, 17, 19, 21, 25, 27, 29, 31, 33, 34, 35, 37, 39, 41, 43, 47, 49, 51, 53, 55, 56, 57, 59, 61, 63, with 0 ≤ b ≤ 10. Then x is divisible by 11 iff b = 0 via the usual rule for divisibility by 11.
Consider the result of changing one of the digits. If any p_i is greater than or equal to b, then we can replace that p_i by p_i − b to get a number divisible by 11 (by placing digit 0 in this spot. If any p_i is less than or equal to b − 2, we can replace that p_i by p_i + 11 − b to get a number divisible by 11 (by changing the new b to be 11). Thus the only value for p_i is b − 1. Therefore, each p_i equals b − 1. A similar argument shows that each n_i must be 10 − b. Note that p and n sum to 9.
Let the digit-count N be even, say N = 2m. Then
11a + b = sum{p} − sum{n}
= m(p − n) = m(b − 1 − (10 − b))
= m(2b − 11).
If we solve for b, we find b = 11(a + m)/(2m − 1). Since a, b, and m are all integers and 0 ≤ b ≤ 10, 2m − 1 must be a multiple of 11. Let 2m − 1 = 11y or m = (11y + 1)/2. For this to be an integer, y must be odd. Thus the smallest sized solution has y = 1, m = 6, and N = 12 digits. The smallest solution has a leading digit of 1 and is x = 181818181818.