2017 AIME II Problem 4

Question

Find the number of positive integers less than or equal to

2017

whose base-three representation contains no digit equal to

0.

Answer

A base-three representation avoids the digit

0

exactly when every digit is

1

or

2;

there are

2^k

such

k

-digit numbers

Since

2017 = 2202201_3,

decide which

7

-digit strings of

1

s and

2

s stay below the bound by looking at the first two digits

A positive integer has no

0

in base three exactly when every digit is

1

or

2.

For

k = 1, 2, \ldots, 6

there are

2^k

such

k

-digit numbers, and all of them are at most

222222_3 = 728 \lt 2017.

Since

2017 = 2202201_3,

a seven-digit string of

1

s and

2

s is at most

2017

exactly when it begins with

11,

12,

or

21:

any string beginning

22

already beats

2202201_3

at the third digit, since its digits are nonzero. That gives

3 \cdot 2^5 = 96

seven-digit numbers.

The total is

2 + 4 + 8 + 16 + 32 + 64

+ 96 = 222.

Problem 4 in other years