Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2017 AIME II Problems/Problem 4"

m (→‎Solution)
(→‎Solution)
Line 4: Line 4:
 
==Solution==
 
==Solution==
 
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 (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
  
 
=See Also=
 
=See Also=
 
{{AIME box|year=2017|n=II|num-b=3|num-a=5}}
 
{{AIME box|year=2017|n=II|num-b=3|num-a=5}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Revision as of 17:58, 23 March 2017

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

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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2017_AIME_II_Problems/Problem_4&oldid=84987"