Revision as of 20:22, 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_{3}$ , and $2187=3^7=10000000_{3}$ . There can be a $1,2,...,7$ digit number less than $2187$ , and each digit can either 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$

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

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

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

@@ Line 8: / Line 8: @@
 Solution 2 (please add latex)
-Note that 2017=220221
+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.
-And 2187=3^7=10000000 base 3
-There can be a 1,2,...,7 digit number less than 2187
+Now we have to subtract out numbers from <math>2018</math> to <math>2187</math>
-Each digit can be 1 or 2
+Then either the number must begin <math>221...</math> or <math>222...</math> with  four more digits at the end
-So 2^1 one digit numbers and so on up to 2^7 7 digit
+Using <math>1</math>s and <math>2</math>s there are <math>2^4</math> options for each so:
+<math>2+4+8+16+32+64+128-2*16=256-2-32=222</math>
-Now we have to subtract out numbers from 2018 to 2187
-Then 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:
-+4+8+16+32+64+128-2*16=256-2-32=222
 =See Also=
 {{AIME box|year=2017|n=II|num-b=3|num-a=5}}
 {{MAA Notice}}

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

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

Revision as of 20:22, 23 March 2017

Problem

Solution

See Also