Maths Olympiad Prep

Library / /1 of 6

, 2020

Number theory Difficulty 4.3 AIME Prove it Romania

A positive integer AA has 73 digits, all different from zero. Prove that we can erase 64 digits such that the new number is divisible by 37.

Solution

After the elimination of the 64 digits the final number has 7364=973 - 64 = 9 digits.
If in the composition of AA, every digit appears at most 8 times, then AA would have at most 98=729 \cdot 8 = 72 digits, which is false.
Therefore, there is a digit different from 0, let that be aa, that appears 9 times in AA. Then we can erase 64 digits from AA such that the final number would have the form aaaaaaaaa=a111111111=a1001001337\overline{aaaaaaaaa} = a \cdot 111111111 = a \cdot 1001001 \cdot 3 \cdot 37, so the number is divisible by 37.

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.