2017 AIME II Problems/Problem 4

Revision as of 12:35, 23 March 2017 by The turtle (talk | contribs) (Created page with "<math>\textbf{Problem 4}</math> Find the number of positive integers less than or equal to <math>2017</math> whose base-three representation contains no digit equal to <math>0...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

$\textbf{Problem 4}$ Find the number of positive integers less than or equal to $2017$ whose base-three representation contains no digit equal to $0$.

$\textbf{Problem 4 Solution}$ The base-$3$ representation of $2017_{10}$ is $2202201_3$. Because any $7$-digit base-$3$ number that starts with $22$ and has no digit equal to $0$ must be greater than $2017_{10}$, all $7$-digit numbers that have no digit equal to $0$ must start with $21$ or $1$ in base $3$. Of the base-$3$ numbers that have no digit equal to $0$, there are $2^5$ $7$-digit numbers that start with $21$, $2^6$ $7$-digit numbers that start with $1$, $2^6$ $6$-digit numbers, $2^5$ $5$-digit numbers, $2^4$ $4$-digit numbers, $2^3$ $3$-digit numbers, $2^2$ $2$-digit numbers, and $2^1$ $1$-digit numbers. Summing these up, the answer is $2^5+2^6+2^6+2^5+2^4+2^3+2^2+2^1=\boxed{222}$.