In: Math
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∈S, such that 2018 | n.
Consider the set { where the last number in the set contains 2019 such }.
There are 2019 numbers in the set . Now, we consider their remainders when divided by . See that when any number is divided by , the possible remainders are {i.e. there are 2018 possible remainders}. Since has 2019 numbers, by the Pigeonhole Principle at least two of the numbers in give the same remainder when divided by .
Let those numbers be and . Then we have
i.e. when divides then the remainder is .
i.e. { where }.
Note that the difference between any two numbers in the set is of the form { i.e. a string of followed by a string of , which are precisely the elements of }.
So . Put . Then we have an such that .
This completes our proof.