2002 Pan African MO Problems/Problem 3

Revision as of 12:52, 24 December 2019 by Rockmanex3 (talk | contribs) (Solution to Problem 3 -- induction rules the day again)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Problem

Prove for every integer $n>0$, there exists an integer $k>0$ such that $2^nk$ can be written in decimal notation using only digits 1 and 2.

Solution

We can use induction to solve the problem. For the base case, note that $2$ is divisible by $2$, $12$ is divisible by $4$, $112$ is divisible by $8$, and $2112$ is divisible by $16$.


Now assume that $x \equiv 0 \pmod{2^{n-1}}$. That means $x = 2^{n-1}k$, where $k$ is an integer. Multiply both sides by $2$ to get $2x = 2^n k$, so $x = \tfrac12 \cdot 2^n k$. That means $x \equiv \tfrac12 \cdot 2^n \pmod{2^n}$ or $x \equiv 0 \pmod{2^n}$.


Additionally, from above, note that $10^{n-1} \equiv \tfrac12 \cdot 2^n \pmod{2^n}$ and $2 \cdot 10^{n-1} \equiv 0 \pmod{2^n}$. Thus, if $x \equiv \tfrac12 \cdot 2^n \pmod{2^n}$, then $x + 10^{n-1} \equiv 2 \cdot \tfrac12 \cdot 2^n \equiv 0 \pmod{2^n}$, and if $x \equiv 0 \pmod{2^n}$, then $x + 2 \cdot 10^{n-1} \equiv 0 \pmod{2^n}$. Therefore, it is possible to write a number with only digits 1 and 2 that is divisible by $2^n$, so there exists a positive integer $k$ where $2^nk$ can be written in decimal notation using only digits 1 and 2.

See Also

2002 Pan African MO (Problems)
Preceded by
Problem 2
1 2 3 4 5 6 Followed by
Problem 4
All Pan African MO Problems and Solutions