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.