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"

(Created page with "<math>\textbf{Problem 4}</math> Find the number of positive integers less than or equal to <math>2017</math> whose base-three representation contains no digit equal to <math>0...")
 
Line 1: Line 1:
−
<math>\textbf{Problem 4}</math>
+
==Problem==
 
Find the number of positive integers less than or equal to <math>2017</math> whose base-three representation contains no digit equal to <math>0</math>.
 
Find the number of positive integers less than or equal to <math>2017</math> whose base-three representation contains no digit equal to <math>0</math>.
  
−
<math>\textbf{Problem 4 Solution}</math>
+
==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, 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, the answer is <math>2^5+2^6+2^6+2^5+2^4+2^3+2^2+2^1=\boxed{222}</math>.
 +
=See Also=
 +
{{AIME box|year=2017|n=II|num-b=3|num-a=5}}
 +
{{MAA Notice}}

Revision as of 11:51, 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, the answer is $2^5+2^6+2^6+2^5+2^4+2^3+2^2+2^1=\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=84894"