Track / Stage 4 / 7 of 340 #267 of 2000

Problem 267

AMC 12 late, AIME early

Number theory Difficulty 4.3 Prove it RMC 2020 · Romania · 2020

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

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

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

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.