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 "2005 AMC 8 Problems/Problem 24"

(→‎Solution)
(Solution 2 using binary)
 
(10 intermediate revisions by 7 users not shown)
Line 4: Line 4:
 
<math> \textbf{(A)}\ 8\qquad\textbf{(B)}\ 9\qquad\textbf{(C)}\ 10\qquad\textbf{(D)}\ 11\qquad\textbf{(E)}\ 12</math>
 
<math> \textbf{(A)}\ 8\qquad\textbf{(B)}\ 9\qquad\textbf{(C)}\ 10\qquad\textbf{(D)}\ 11\qquad\textbf{(E)}\ 12</math>
  
−
==Solution==
+
==Solution 1 (Now rigorous)==
−
First we can start at 200 and work our way down to 1. Since we want to do divide by two the most, so if we come across an odd number we just subtract 1.  So <math>200/2</math>=<math>100</math>,  <math>100/2</math>=<math>50</math>,  <math>50/2</math>=<math>25</math>,  <math>25-1</math>=<math>24</math>, <math>24/2</math>=<math>12</math>,  <math>12/2</math>=<math>6</math>, <math>6/2</math>=<math>3</math>, <math>3-1</math>=<math>2</math>, and  <math>2/2</math>=<math>1</math>.  We made our way back to 1 but since it is the amount of times the button is pressed than the answer should be <math>10-1</math>=<math>\boxed{\textbf{(B)}\ 9}</math>! - <math>\boxed{\textbf{Javapost}}</math>
+
We can start at <math>200</math> and work our way down to <math>1</math>. We want to press the button that multiplies by <math>2</math> the most, but since we are going down instead of up, we divide by <math>2</math> instead. If we come across an odd number, then we will subtract that number by <math>1</math>. Notice
 +
  <math>200 \div 2 = 100</math>, 
 +
<math>100 \div 2 = 50</math>,
 +
  <math>50 \div 2 = 25</math>,
 +
<math>25-1 = 24</math>, 
 +
<math>24 \div 2 = 12</math>,
 +
  <math>12 \div 2 = 6</math>, 
 +
<math>6 \div 2 = 3</math>,
 +
  <math>3-1 = 2</math>,
 +
<math>2 \div 2 = 1</math>. 
 +
Since we've reached <math>1</math>, it's clear that the answer should be <math>\boxed{\textbf{(B)}\ 9}</math>- <math>\boxed{\textbf{Javapost}}</math>. Because we only subtracted <math>1</math> when we had to, this is optimal. ~Roy2020
 +
 
 +
==Solution 2 (Binary)==
 +
We make two key observations. First, pressing [x2] appends a <math>0</math> to the end of a number's binary representation. Second, pressing [x2] and then pressing [+1] appends <math>1</math> to the end of a number's binary representation.
 +
 
 +
The base-ten number <math>200</math> is represented as <math>11001000_2</math> in binary. Therefore, the five <math>0</math>s contribute <math>5</math> button presses. Similarly, each of the three <math>1</math>s each contribute <math>2</math> button presses, although we do not count one of them as the calculator initially starts with the number <math>1.</math> Thus, the answer is <math>5 + 2 \cdot 2 = \boxed{\textbf{(B)}\ 9}</math>
  
 
==See Also==
 
==See Also==
 
{{AMC8 box|year=2005|num-b=23|num-a=25}}
 
{{AMC8 box|year=2005|num-b=23|num-a=25}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Latest revision as of 22:34, 13 May 2025

Problem

A certain calculator has only two keys [+1] and [x2]. When you press one of the keys, the calculator automatically displays the result. For instance, if the calculator originally displayed "9" and you pressed [+1], it would display "10." If you then pressed [x2], it would display "20." Starting with the display "1," what is the fewest number of keystrokes you would need to reach "200"?

$\textbf{(A)}\ 8\qquad\textbf{(B)}\ 9\qquad\textbf{(C)}\ 10\qquad\textbf{(D)}\ 11\qquad\textbf{(E)}\ 12$

Solution 1 (Now rigorous)

We can start at $200$ and work our way down to $1$. We want to press the button that multiplies by $2$ the most, but since we are going down instead of up, we divide by $2$ instead. If we come across an odd number, then we will subtract that number by $1$. Notice 

$200 \div 2 = 100$,  
$100 \div 2 = 50$,  
$50 \div 2 = 25$,
$25-1 = 24$,  
$24 \div 2 = 12$,  
$12 \div 2 = 6$,  
$6 \div 2 = 3$,  
$3-1 = 2$, 
$2 \div 2 = 1$.

Since we've reached $1$, it's clear that the answer should be $\boxed{\textbf{(B)}\ 9}$- $\boxed{\textbf{Javapost}}$. Because we only subtracted $1$ when we had to, this is optimal. ~Roy2020

Solution 2 (Binary)

We make two key observations. First, pressing [x2] appends a $0$ to the end of a number's binary representation. Second, pressing [x2] and then pressing [+1] appends $1$ to the end of a number's binary representation.

The base-ten number $200$ is represented as $11001000_2$ in binary. Therefore, the five $0$s contribute $5$ button presses. Similarly, each of the three $1$s each contribute $2$ button presses, although we do not count one of them as the calculator initially starts with the number $1.$ Thus, the answer is $5 + 2 \cdot 2 = \boxed{\textbf{(B)}\ 9}$

See Also

2005 AMC 8 (Problems • Answer Key • Resources)
Preceded by
Problem 23 		Followed by
Problem 25
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AJHSME/AMC 8 Problems and Solutions

These problems are copyrighted © by the Mathematical Association of America, as part of the American Mathematics Competitions. AMC Logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2005_AMC_8_Problems/Problem_24&oldid=248370"