USAMO problem solution

Question

I had asked for a hint here USAMO problem hint. i had tried induction once but i thought it won't work so i left it, but after seeing @lulu 's comment, i decided to give it a go again. Please see if my solution is correct.

[USAMO 2003] Prove that for every positive integer n there exists an n-digit number divisible by $5^n$ all of whose digits are odd.

MY SOLUTION: So first thing, i checked some small cases and figured we could generate the number with (n+1) digits satisfying the property by adding a number to it's front, ie. adding b 10$^n$ to the number with n digits.

We'll proceed with induction, let P(n) mean there exists an n-digit number divisible by $5^n$ all of whose digits are odd.

P(1) is true as 5|5.

Let P(k) be true, ie. let 5$^k$ | $a_ka_{k-1}…a_1$ with $a_i$ $\neq$ 2l for i $\in$ {1,2…k} .

I'll attempt to prove that by adding $ b \cdot 10^k $ with $ b \in {1,3,5,7,9} $ . we can have a number that is divisible by $5^{k+1}$.

So we want 5$^{k+1}$ $|$ $ b \cdot 10^k $ + $a_ka_{k-1}…a_1$ . –> eq.1

Let $a_ka_{k-1}…a_1$ = $5^km $

So from eq. 1, inputting $a_ka_{k-1}…a_1$ = $5^km $ , we will get

5$^{k+1}$ $|$ $ b \cdot 10^k $ + $5^k$m, then dividing throught by $5^k$ , we need

5 $|$ $2^k \cdot b + m$

as $ b \in {1,3,5,7,9} $ , $\equiv$ 0,1,2,3,4 (mod 5)

So now m $\equiv$ 0,1,2,3,4 (mod 5) , let m $\equiv$ r (mod 5),

We need $2^k \cdot b + r =0 (mod 5)$

now,$2^k \equiv$ 1,2,3,4 (mod 5)

so painstakingly going through each and every case of possible values of $2^k$ and m (mod 5) (there are 16 cases), we prove that we can find a $ b \in {1,3,5,7,9} $ such that 5 $|$ $2^k \cdot b + m$ .

This is the first time i have written so much in latex, so i am sorry if there is any mistake.

If you were a grader, out of 7, how many points would you give me?

Answer 1

I don't think math.se answers can address how they'd mark it, but I can advise on a cleaner way to write answers, because your ideas are right but they could do with algebraic clarity, and clarity regarding modulo arithmetic. (If you find yourself claiming that if we do something we eventually get a particular outcome, try to state this as an existence theorem that's either obvious, well-known or proven within your work.) To wit:

We claim some sequence $a_n$ of $n$-digit numbers in base $10$, all digits odd, satisfies $5^n|a_n,\,10^n|a_{n+1}-a_n$. In particular write $a_n=5^nb_n,\,a_{n+1}=a_n+10^nc_n$, so $b_1=1$ (because $a_1=5$) and$$5^{n+1}b_{n+1}=a_{n+1}=c_n10^n+5^nb_n\iff5b_{n+1}=c_n2^n+b_n,$$so it suffices to choose $c_n\in\{1,\,3,\,5,\,7,\,9\}$ with $5|c_n2^n+b_n$. This choice is possible because these $5$ choices of the $c_n$ each achieve a different residue class modulo $5$ (because $5\nmid k2^n$ for $k\in\{2,\,4,\,6,\,8\}$), and exactly one achieves $5|c_n2^n+b_n$.