Maths Olympiad Prep

Library / /11 of 32

Number theory Difficulty 5.4 AIME, harder Prove it Estonia

Juku writes down all 20-digit numbers in which each of digits 33, 44, 55 and 66 appear five times in a row (in some order). Prove that it is possible to choose two of those numbers such that their difference is divisible by 207207.

Solution

As 207=923207 = 9 \cdot 23 and 99 and 2323 are relatively prime, it suffices to find a difference that would be divisible by both 99 and 2323.

All the 2020-digit numbers listed are divisible by 99 because the sum of their digits is 9090. Therefore the difference of any two of them is also divisible by 99.

It remains to show that the difference of some two of them is divisible by 2323. For this note that there are 2424 different orderings of 33, 44, 55 and 66. Therefore there are 2424 numbers written in total, but there are 2323 different possible remainders. So there must exist some two among those that give the same remainder when divided by 2323. Their difference is divisible by 2323.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.