# Nondivisibility by 11 puzzle

Source: MacPOW Problem of the Week 1240

Take this math puzzle:

The number 545 has the curious property that upon replacing the digit in any single position by an arbitrary digit (from 0 to 9; it can be a leading 0 or just the same digit), the result is not divisible by 11.

Is there a positive integer with this property having an even number of digits?

I have worked on it for a bit with no real progress when it comes to solving this problem. If anything, all I've really done is pick random numbers and check for the property in question. (which hasn't really worked - I'm still in the 4-digit numbers).

So, my question to you is:

### If there is a solution, what is the smallest number with an even number of digits that has this property with no leading 0?

Recall that a number is divisible by $$11$$ exactly if its alternating digit sum $$S=d_1-d_2+d_3-d_4...$$ is.

From this we immediately glean that a number with the required property must have the same digit in all even and the same digit in all odd positions. Indeed, choose any position and compute the alternating digit sum leaving out that value (without altering the signs of the other terms) $$S_{\widehat k}=S+(-1)^kd_k$$. Because we are allowed to replace the left out place with any digit, none of $$S_{\widehat k},S_{\widehat k}-(-1)^k,S_{\widehat k}-(-1)^k\times 2,\ldots,S_{\widehat k}-(-1)^k\times 9$$ can be divisible by $$11$$. As these are 10 consecutive numbers, the previous and next must be multiples of $$11$$. I.e. $$S_{\widehat k}+(-1)^k \equiv 0 \mod {11}$$, from which the assertion follows.

Call those the even and odd digits $$d_e,d_o$$. Similarly, write $$S_{\widehat e},S_{\widehat o}$$ for the corresponding omissions. Then $$S_{\widehat e} \equiv -1 \mod {11}$$ and $$S_{\widehat o} \equiv 1 \mod {11}$$. Taking the difference yields $$9 \equiv -2 \equiv S_{\widehat e} - S_{\widehat o} \equiv d_e + d_o \mod {11}$$.

Let $$2n$$ be the number of digits. Then $$0 \equiv S_{\widehat o} - 1 \equiv (n-1)d_o - nd_e - 1 \equiv (n-1)d_o + nd_o + 2n - 1 \equiv (2n-1)(d_o + 1) \mod {11}$$. It follows that $$2n-1$$ is a multiple of $$11$$ because $$d_o+1$$ cannot ($$1 \le d_o+1 \le 10$$).

The smallest number with the property is therefore

$$181818181818$$.

• Wow that's quick! I did not expect an answer this fast! (this is a really difficult puzzle) =) Dec 7, 2023 at 2:53
• Perhaps you can explain a bit more on why it must have the same digit in all even and the same digit in all odd positions? I'm thinking it's because of the range of numbers must not have more than 10 different values modulo 11, but feels like it's something that can be easily included for ease of understanding :) The same for the reasoning for changing to 0 one of the digits. Dec 11, 2023 at 16:00