Maths Olympiad Prep

Track / Stage 5 / 379 of 400 #979 of 1964

Problem 979

AIME late
Number theory Difficulty 5.9 Prove it

Example 4 (2005 Romanian Mathematical Olympiad) Prove: For every positive integer nn, there exists a unique nn-digit positive integer in decimal notation that is divisible by 5n5^{n}, and each of its digits belongs to {1,2,3,4,5}\{1,2,3,4,5\}.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Prove using mathematical induction.
For each positive integer nn, there exists a unique nn-digit number AnA_{n}, which is divisible by 5n5^{n}, and its digits all belong to the set {1,2,3,4,5}\{1,2,3,4,5\}.
Clearly, A1=5,A2=25A_{1}=5, A_{2}=25.
Assume AnA_{n} is determined, let Bn=An5nB_{n}=\frac{A_{n}}{5^{n}}, then the n+1n+1-digit number cn+1cnc1=cn+110n+cncn1c1\overline{c_{n+1} c_{n} \cdots c_{1}}=c_{n+1} 10^{n}+\overline{c_{n} c_{n-1} \cdots c_{1}} is divisible by 5n5^{n} if and only if cncn1c1\overline{c_{n} c_{n-1} \cdots c_{1}} is divisible by 5n5^{n}.
By the induction hypothesis,
cncn1c1=An=5nBn\overline{c_{n} c_{n-1} \cdots_{c_{1}}}=A_{n}=5^{n} B_{n}.
Therefore, cn+1cnc1=5n(2ncn+1+Bn)\overline{c_{n+1} c_{n} \cdots c_{1}}=5^{n}\left(2^{n} c_{n+1}+B_{n}\right).
It is divisible by 5n+15^{n+1} if and only if 2ncn+1+Bn2^{n} c_{n+1}+B_{n} is divisible by 5.
Since (2n,5)=1\left(2^{n}, 5\right)=1, the equation 2nx+b0(mod5)2^{n} x+b \equiv 0(\bmod 5) has a unique solution in the set {1,2,3,4,5}\{1,2,3,4,5\}, where nN+,bNn \in \mathbf{N}_{+}, b \in \mathbf{N}.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.