Subsets of the Integers that Cover All Residues Modulo $n$

Question

Call a subset of the integers special if, for every integer $n$, every residue from $0$ to $n-1$ is obtained when all elements from the subset are taken modulo $n$. Is the set of all non-decreasing integers special? Non-decreasing integers never have digits decrease from left to right in base $10$. Examples are 11134, 44489, and 567.

It seems as if it would be true. Since I saw no method for a direct proof, I first looked for counterexamples. Then I thought that perhaps no such integer is congruent to 10 modulo 11. I searched hard and found no such example. I'm not sure how to proceed with either route (i.e. either proving the statement directly or disproving it by proving that 10 modulo 11 is never obtained).

Answer 1

Dunno about $10$ mod $11$. But it's obvious that the set of non-decreasing integers is not special: Consider $n=100$.

Answer 2

The set of non-decreasing positive integers has no number that is equivalent to $10$ mod $11$. Read about modulo arithmetic to understand notation and basic facts. To prove the statement, notice that (where $a_i$ are digits)

$$\overline{a_na_{n-1}\cdots a_1a_0}\equiv 10^na_n+10^{n-1}a_{n-1}+\cdots+10a_1+a_0\equiv$$

$$\equiv (-1)^na_n+(-1)^{n-1}a_{n-1}+\cdots+(-1)a_1+a_0\pmod{11}$$

If there are two equal digits in a number, then they don't change anything mod $11$ and you can ignore the pair of two equal digits. So WLOG let the number be strictly increasing. Then the number has at most nine digits. If the number has one digit, then it's obvious. If the amount of digits is odd and $\ge 3$, then the number is equivalent to $(a_{2k}-a_{2k-1})+\cdots+(a_2-a_1)+a_0$ mod $11$. All the values in parentheses are negative, i.e. $\le -1$, because the number is strictly increasing, so $(a_{2k}-a_{2k-1})+\cdots+(a_2-a_1)+a_0\le -1+a_0\le -1+9=8$. If you use parentheses differently, then you'll get $a_{2k}+(-a_{2k-1}+a_{2k-2})+\cdots+(-a_1+a_0)$. All the values in parentheses are positive and $a_{2k}\ge 1$, so $a_{2k+1}+(-a_{2k}+a_{2k-1})+\cdots+(-a_1+a_0)\ge 2$. So the number is equivalent to $r\in[2,8]$, $r\in\mathbb Z$ mod $11$ and never $10$ or $-1$ mod $11$.

If the amount of digits is even and $\ge 2$, then the number is equivalent to $(-a_{2k+1}+a_{2k})+\cdots+(-a_1+a_0)$ mod $11$. All the values in parentheses are positive, so $(-a_{2k+1}+a_{2k})+\cdots+(-a_1+a_0)\ge 1$. Notice that $(-a_{i+1}+a_i)$ is the distance between $a_{i+1}$ and $a_i$ in the real number line. $(-a_{2k+1}+a_{2k})+\cdots+(-a_1+a_0)\le a_0-a_{2k+1}\le 9-1=8$. So the number is equivalent to $r\in[1,8]$, $r\in\mathbb Z$ mod $11$ and never $10$ or $-1$ mod $11$.