Problem

Find the number of positive integers less than or equal to $2017$ whose base-three representation contains no digit equal to $0$ .

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, we find that the answer is $2^5+2^6+2^6+2^5+2^4+2^3+2^2+2^1=\boxed{222}$ .

Solution 2 (please add latex)

Note that 2017=220221

And 2187=3^7=10000000 base 3

There can be a 1,2,...,7 digit number less than 2187

Each digit can be 1 or 2

So 2^1 one digit numbers and so on up to 2^7 7 digit

Now we have to subtract out numbers from 2018 to 2187

The either the number must begin 221... or 222... with four more digits at the end

Using 1s and 2s there are 2^4 options for each so:

2+4+8+16+32+64+128-2*16=256-2-32=222

2017 AIME II (Problems • Answer Key • Resources)
Preceded by Problem 3	Followed by Problem 5
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

Page

Toolbox

Search

2017 AIME II Problems/Problem 4

Problem

Solution

See Also