Difference between revisions of "2017 AIME II Problems/Problem 4"
(→Solution) |
m (→Solution) |
||
Line 3: | Line 3: | ||
==Solution== | ==Solution== | ||
+ | ===Solution 1=== | ||
The base-<math>3</math> representation of <math>2017_{10}</math> is <math>2202201_3</math>. Because any <math>7</math>-digit base-<math>3</math> number that starts with <math>22</math> and has no digit equal to <math>0</math> must be greater than <math>2017_{10}</math>, all <math>7</math>-digit numbers that have no digit equal to <math>0</math> must start with <math>21</math> or <math>1</math> in base <math>3</math>. Of the base-<math>3</math> numbers that have no digit equal to <math>0</math>, there are <math>2^5</math> <math>7</math>-digit numbers that start with <math>21</math>, <math>2^6</math> <math>7</math>-digit numbers that start with <math>1</math>, <math>2^6</math> <math>6</math>-digit numbers, <math>2^5</math> <math>5</math>-digit numbers, <math>2^4</math> <math>4</math>-digit numbers, <math>2^3</math> <math>3</math>-digit numbers, <math>2^2</math> <math>2</math>-digit numbers, and <math>2^1</math> <math>1</math>-digit numbers. Summing these up, we find that the answer is <math>2^5+2^6+2^6+2^5+2^4+2^3+2^2+2^1=\boxed{222}</math>. | The base-<math>3</math> representation of <math>2017_{10}</math> is <math>2202201_3</math>. Because any <math>7</math>-digit base-<math>3</math> number that starts with <math>22</math> and has no digit equal to <math>0</math> must be greater than <math>2017_{10}</math>, all <math>7</math>-digit numbers that have no digit equal to <math>0</math> must start with <math>21</math> or <math>1</math> in base <math>3</math>. Of the base-<math>3</math> numbers that have no digit equal to <math>0</math>, there are <math>2^5</math> <math>7</math>-digit numbers that start with <math>21</math>, <math>2^6</math> <math>7</math>-digit numbers that start with <math>1</math>, <math>2^6</math> <math>6</math>-digit numbers, <math>2^5</math> <math>5</math>-digit numbers, <math>2^4</math> <math>4</math>-digit numbers, <math>2^3</math> <math>3</math>-digit numbers, <math>2^2</math> <math>2</math>-digit numbers, and <math>2^1</math> <math>1</math>-digit numbers. Summing these up, we find that the answer is <math>2^5+2^6+2^6+2^5+2^4+2^3+2^2+2^1=\boxed{222}</math>. | ||
− | Solution 2 | + | ===Solution 2=== |
Note that <math>2017=220221_{3}</math>, and <math>2187=3^7=10000000_{3}</math>. There can be a <math>1,2,...,7</math> digit number less than <math>2187</math>, and each digit can either be <math>1</math> or <math>2</math>. So <math>2^1</math> one digit numbers and so on up to <math>2^7</math> <math>7</math> digit. | Note that <math>2017=220221_{3}</math>, and <math>2187=3^7=10000000_{3}</math>. There can be a <math>1,2,...,7</math> digit number less than <math>2187</math>, and each digit can either be <math>1</math> or <math>2</math>. So <math>2^1</math> one digit numbers and so on up to <math>2^7</math> <math>7</math> digit. |
Revision as of 15:41, 24 March 2017
Problem
Find the number of positive integers less than or equal to whose base-three representation contains no digit equal to
.
Solution
Solution 1
The base- representation of
is
. Because any
-digit base-
number that starts with
and has no digit equal to
must be greater than
, all
-digit numbers that have no digit equal to
must start with
or
in base
. Of the base-
numbers that have no digit equal to
, there are
-digit numbers that start with
,
-digit numbers that start with
,
-digit numbers,
-digit numbers,
-digit numbers,
-digit numbers,
-digit numbers, and
-digit numbers. Summing these up, we find that the answer is
.
Solution 2
Note that , and
. There can be a
digit number less than
, and each digit can either be
or
. So
one digit numbers and so on up to
digit.
Now we have to subtract out numbers from to
Then either the number must begin or
with four more digits at the end
Using s and
s there are
options for each so:
See Also
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 |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.