Question

1. Prove that given n + 1 natural numbers, there are always two of them such that their difference is a multiple of n.

2. Prove that there is a natural number composed with the digits 0 and 5 and divisible by 2018.

both questions can be solved using pigeonhole principle.

Answer 1

1. Here, since there are only n possible remainders on division by n, and we have n + 1 numbers, by the Pigeonhole Principle (PHP) some two of them have the same remainder on division by n. Thus we can write these two as

n₁ = nk₁ + r and n₂ = nk₂ + r where r is the remainder on division by n. Then the difference is n₁ − n₂ = (nk₁ + r) − (nk₂ + r) = nk₁ + r − nk₂ − r = nk₁ − nk₂ = n(k₁ − k₂), which is divisible by n.

2. we will prove more general thing for any n in natural numbers.

Show that for any natural number n there is a number composed of digits 5 and 0 only and divisible by n

(here you are having n=2018)

Solution: We will use the previous problem. We want to find a number divisible by n; the previous problem tells us that given any set of n + 1 numbers, some two of them have a difference that’s divisible by n. So we should try to find a set of n + 1 numbers with the property that for any two of them, the difference is a number composed of digits 5 and 0 only. One possibility is the sequence of numbers 5, 55, 555, 5555, 55555, . . ., since the difference of any two of these will be some number of 5’s followed by some number of 0’s. So we can take the first n+ 1 numbers whose only digits are 5, and there must be some pair whose difference is composed of only 5’s and 0’s, and divisible by n.