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"

(→‎Solution)
(→‎Casework Solution)
 
(7 intermediate revisions by 6 users not shown)
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 (please add latex)
+
Note that <math>2017=2202201_{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 2017=220221
 
  
−
And 2187=3^7=10000000 base 3
+
Now we have to subtract out numbers from <math>2018</math> to <math>2187</math>
  
−
There can be a 1,2,...,7 digit number less than 2187
+
Then either the number must begin <math>221...</math> or <math>222...</math> with  four more digits at the end
  
−
Each digit can be 1 or 2
+
Using <math>1</math>s and <math>2</math>s there are <math>2^4</math> options for each so:
  
−
So 2^1 one digit numbers and so on up to 2^7 7 digit
+
<math>2+4+8+16+32+64+128-2*16=256-2-32=\boxed{222}</math>
  
 +
===Solution 3 (Casework)===
 +
Since the greatest power of <math>3</math> that can be used is <math>3^6</math>, we can do these cases.
  
−
Now we have to subtract out numbers from 2018 to 2187
+
Coefficient of <math>3^6=0</math>: Then if the number has only <math>3^0</math>, it has 2 choices (1 or 2). Likewise if the number has both a <math>3^1</math> and <math>3^0</math> term, there are 4 choices, and so on until <math>3^5</math>, so the sum is <math>2+4+...+64=127-1=126</math>.
  
−
The either the number must begin 221... or 222... with  four more digits at the end
+
Coefficient of <math>3^6=1</math>: Any combination of <math>1</math> or <math>2</math> for the remaining coefficients works, so <math>2^6=64</math>. Why is this less than <math>126</math>? Because the first time around, leading zeroes didn't count. But this time, all coefficients <math>3^n</math> of <math>n<6</math> need 1 and 2.
  
−
Using 1s and 2s there are 2^4 options for each so:
+
Coefficient of <math>3^6=2</math>: Look at <math>3^5</math> coefficient. If 1, all of them work because <math>3^7=2187-3^5=243<<2017</math>. That's 32 cases. Now of this coefficient is 2, then at the coefficient of <math>3^4=81</math> is at least 1. However, <math>3^6*2+3^5*2+3^4>>2017</math>, so our answer is <math>126+64+32=\boxed{222}</math>.
−
 
 
−
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}}

Latest revision as of 13:31, 20 February 2020

Problem

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

Solution

Solution 1

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

Note that $2017=2202201_{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=\boxed{222}$

Solution 3 (Casework)

Since the greatest power of $3$ that can be used is $3^6$, we can do these cases.

Coefficient of $3^6=0$: Then if the number has only $3^0$, it has 2 choices (1 or 2). Likewise if the number has both a $3^1$ and $3^0$ term, there are 4 choices, and so on until $3^5$, so the sum is $2+4+...+64=127-1=126$.

Coefficient of $3^6=1$: Any combination of $1$ or $2$ for the remaining coefficients works, so $2^6=64$. Why is this less than $126$? Because the first time around, leading zeroes didn't count. But this time, all coefficients $3^n$ of $n<6$ need 1 and 2.

Coefficient of $3^6=2$: Look at $3^5$ coefficient. If 1, all of them work because $3^7=2187-3^5=243<<2017$. That's 32 cases. Now of this coefficient is 2, then at the coefficient of $3^4=81$ is at least 1. However, $3^6*2+3^5*2+3^4>>2017$, so our answer is $126+64+32=\boxed{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=118271"