2002 Pan African MO Problems/Problem 3

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.

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

Page

Toolbox

Search

2002 Pan African MO Problems/Problem 3

Problem

Solution

See Also