Divisibility of Consecutive Powers of 10

Question

Let $S$ be the set of natural numbers which can be written as a non-empty string of ones followed by a non-empty string of zeroes. For example, $10$, $111100$ and $11100000$ are all in $S$, but $11$ and $1110011$ are not in $S$. Prove that there exists a natural number $n$ in $S$ such that $2018$ divides $n$.

The numbers $\,s \in S\,$ have form $\,s = ((10^k-1)/9)10^n\,$ so $\,9s = (10^k-1)10^n = 10^{k+n}-10^k,\,$ so we need $\,10^{k+n}\equiv 10^k\pmod{2018}.\,$ How can we achieve that?

To all future readers and concerned users:

First of all, no this isn't a contest question. As some have pointed out, that this question is rather simple for a contest. In addition, I don't know of any contests that allow you to access the Internet during it, not to mention the fact they are also written in spans of a few hours.

My solution:

It is similar to that of @Bill but mine is probably not as elegant. I also don't think this solution explicitly uses pigeon hole.

Recognize that 2018 = 2 * 1009 which are also relatively coprime. 1009 is also prime as it is not divisible by any numbers between 1 and its square root.

By FLT (Fermat's Little Theorem) 10^1008 = 1 (mod 1009) -> 10^1008 -1 = 0 (mod 1009)

In addition multiplication does not break congruence so:

10^n(10^1008-1) = 0 (mod 1009) for some n in N.

Now this part is hand-wavy...

Since n is in N we can say the result of 10^n(10^1008-1) is a long string 9's followed by at LEAST ONE zero.

By definition of modulus, we can say 1009 also divides this string of 9's followed by at LEAST ONE zero. Since it ends in zero, it is also divisible by 2. Since 2 and 1009 are coprime, it is also divisible by 2018.

For additional context: This question does not require pigeonhole, the only requirement was to have a decently strong proof.

Note: Sorry I was not clearer earlier this wasn't a contest question. I solved the question a few hours after I posted it and forgot to address some concerns about possible ethical issues.

Answer 1

Hint $\bmod 2018\!:\,\ 10^{k+n}\equiv 10^n\ $ by pigeonhole, $ $ so $\,2018\mid (10^k-1)10^n = \color{#c00}9\cdot 11\cdots 100\cdots 0.\,$ But $\,\gcd(2018,9) = \gcd(2\!+\!0\!+\!1\!+\!8,9)=\gcd(11,9)=1\ $ therefore $\,2018\mid \color{#c00}9m\,\Rightarrow\, 2018\mid m$

Answer 2

Every positive integer $M$ may be written as $M =m2^a5^b$ wher $\gcd(m,10) = 1$.

So by Eulers theorem there exist an $n=\phi(m)$ so that $10^n \equiv 1 \pmod m$. So $m|10^n - 1$.

It's well known and easiliy verified that $\frac{10^n -1}9 = \underbrace{111...1}_n$ (just multiply both sides by $9$).

So if $\gcd(m,9) = 1$ then $m|\frac{10^n-1}9=\underbrace{111...1}_n$ And so $M=m2^a5^b|\underbrace{111...1}_n*2^a5^b$ and for $k = \max (a,b)$ then $\underbrace{111...1}_n*2^a5^b|\underbrace{111...1}_n*10^k = \underbrace{111...1}_n\underbrace{000...0}_k$.

And as $2018 = 1009*2$ and $1009$ is relatively prime to $9$. (Actually $1009$ is prime.) We have $2018|\underbrace{111....1}_{\phi(1009) = 1008\text{ times}}0$. (Note: $1008$ might not be the least number of $1$ but it is a sufficient number of $1$. It's possible, extremely likely in fact, that there are $n|1008$ so that $10^n \equiv 1 \pmod {1009}$.)

...

Postscript: If $\gcd(m,9)\ne 1$, we can rewrite $m$ ad $m= m'*3^c$

And $3^c|10000....1000....10000.... 1$ for $3^c$ number of $1$s with $n= \phi(m')$ zeros between then as $m'|11111....1$ the $3^cm'|1000....1000...1*11111111....11=11111111......1111$ and $M|1111.....1000000.....0$.

So this will be true of all numbers.

Answer 3

By pigeonhole principle, among the numbers 1, 11, 111, 1111, ... on up to 2019 ones in a row, there must be at least two who share the same remainder modulo 2018.

Their difference then must be a multiple of 2018 and their difference is of the desired form consisting of a nonempty string of ones followed by zeroes.