Fewest number of steps to reach 200 using special calculatorchoosing $5$ non consecutive books from a shelve of $12$A calculator is broken so that the only keys that still work are the basic trigonometric and inverse trigonometric functionsKnight returning to corner on chessboard — average number of stepsOptimization of English Braille: Using the fewest dotsWhen can we quit a game of War?Shortest number of steps to reach a positionReaching a destination with random steps: is the time $2^x - 1$?integrating a line with a changing slopeA set of integersDoubt regarding William Feller's combinatorics problem of indistinguishable objects
Hausdorff dimension of the boundary of fibres of Lipschitz maps
What is the term when voters “dishonestly” choose something that they do not want to choose?
Why is there so much iron?
PTIJ: Do Irish Jews have "the luck of the Irish"?
Is there a term for accumulated dirt on the outside of your hands and feet?
Loading the leaflet Map in Lightning Web Component
Would it be believable to defy demographics in a story?
How are passwords stolen from companies if they only store hashes?
Is honey really a supersaturated solution? Does heating to un-crystalize redissolve it or melt it?
How to define limit operations in general topological spaces? Are nets able to do this?
In what cases must I use 了 and in what cases not?
World War I as a war of liberals against authoritarians?
Using Past-Perfect interchangeably with the Past Continuous
Can a medieval gyroplane be built?
What is the relationship between relativity and the Doppler effect?
Writing in a Christian voice
Is it insecure to send a password in a `curl` command?
What is the significance behind "40 days" that often appears in the Bible?
Violin - Can double stops be played when the strings are not next to each other?
What does "Four-F." mean?
How can an organ that provides biological immortality be unable to regenerate?
Is it possible to stack the damage done by the Absorb Elements spell?
Geography in 3D perspective
Why is indicated airspeed rather than ground speed used during the takeoff roll?
Fewest number of steps to reach 200 using special calculator
choosing $5$ non consecutive books from a shelve of $12$A calculator is broken so that the only keys that still work are the basic trigonometric and inverse trigonometric functionsKnight returning to corner on chessboard — average number of stepsOptimization of English Braille: Using the fewest dotsWhen can we quit a game of War?Shortest number of steps to reach a positionReaching a destination with random steps: is the time $2^x - 1$?integrating a line with a changing slopeA set of integersDoubt regarding William Feller's combinatorics problem of indistinguishable objects
$begingroup$
This is a problem from the AMC 8 (math contest):
A certain calculator has only two keys $[+1]$ and $[times 2]$. 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 $[times 2]$, it would display “$20$”. Starting with the display “$1$”, what is the fewest number of keystrokes you would need to reach “$200$”?
Intuitively I worked back from $200$, dividing by $2$ until I reached an odd number, subtracting $1$ when I did, etc..to reach the correct answer of $9$ steps.
However, I can't figure out how to convince myself beyond any doubt that it is the optimal solution. In other words, I can't prove it mathematically.
The best I can come up with is that beyond the first step from $1$ to $2$, multiplication by $2$ is always going to yield a larger step than addition by $1$ and therefore I should take as many $[times 2]$ steps as I can. This doesn't feel rigorous enough, though.
EDIT: Just to be clear, I am asking for a proof or at least more rigorous explanation of why this is the optimal solution.
combinatorics algebra-precalculus contest-math
$endgroup$
add a comment |
$begingroup$
This is a problem from the AMC 8 (math contest):
A certain calculator has only two keys $[+1]$ and $[times 2]$. 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 $[times 2]$, it would display “$20$”. Starting with the display “$1$”, what is the fewest number of keystrokes you would need to reach “$200$”?
Intuitively I worked back from $200$, dividing by $2$ until I reached an odd number, subtracting $1$ when I did, etc..to reach the correct answer of $9$ steps.
However, I can't figure out how to convince myself beyond any doubt that it is the optimal solution. In other words, I can't prove it mathematically.
The best I can come up with is that beyond the first step from $1$ to $2$, multiplication by $2$ is always going to yield a larger step than addition by $1$ and therefore I should take as many $[times 2]$ steps as I can. This doesn't feel rigorous enough, though.
EDIT: Just to be clear, I am asking for a proof or at least more rigorous explanation of why this is the optimal solution.
combinatorics algebra-precalculus contest-math
$endgroup$
$begingroup$
Do you want the fewest steps to get to exactly $200$ or at least $200$?
$endgroup$
– John Douma
9 hours ago
$begingroup$
@JohnDouma: Exactly $200$, obviously. Otherwise eight steps would suffice.
$endgroup$
– TonyK
9 hours ago
$begingroup$
@TonyK That is not obvious. In fact, the last paragraph before the EDIT implies otherwise.
$endgroup$
– John Douma
9 hours ago
2
$begingroup$
@JohnDouma It's exactly $200$, but I disagree with your comment that the last paragraph implies otherwise. I can try to take as many X2 steps as I can and still intend to not get past $200$.
$endgroup$
– jeremy radcliff
9 hours ago
add a comment |
$begingroup$
This is a problem from the AMC 8 (math contest):
A certain calculator has only two keys $[+1]$ and $[times 2]$. 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 $[times 2]$, it would display “$20$”. Starting with the display “$1$”, what is the fewest number of keystrokes you would need to reach “$200$”?
Intuitively I worked back from $200$, dividing by $2$ until I reached an odd number, subtracting $1$ when I did, etc..to reach the correct answer of $9$ steps.
However, I can't figure out how to convince myself beyond any doubt that it is the optimal solution. In other words, I can't prove it mathematically.
The best I can come up with is that beyond the first step from $1$ to $2$, multiplication by $2$ is always going to yield a larger step than addition by $1$ and therefore I should take as many $[times 2]$ steps as I can. This doesn't feel rigorous enough, though.
EDIT: Just to be clear, I am asking for a proof or at least more rigorous explanation of why this is the optimal solution.
combinatorics algebra-precalculus contest-math
$endgroup$
This is a problem from the AMC 8 (math contest):
A certain calculator has only two keys $[+1]$ and $[times 2]$. 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 $[times 2]$, it would display “$20$”. Starting with the display “$1$”, what is the fewest number of keystrokes you would need to reach “$200$”?
Intuitively I worked back from $200$, dividing by $2$ until I reached an odd number, subtracting $1$ when I did, etc..to reach the correct answer of $9$ steps.
However, I can't figure out how to convince myself beyond any doubt that it is the optimal solution. In other words, I can't prove it mathematically.
The best I can come up with is that beyond the first step from $1$ to $2$, multiplication by $2$ is always going to yield a larger step than addition by $1$ and therefore I should take as many $[times 2]$ steps as I can. This doesn't feel rigorous enough, though.
EDIT: Just to be clear, I am asking for a proof or at least more rigorous explanation of why this is the optimal solution.
combinatorics algebra-precalculus contest-math
combinatorics algebra-precalculus contest-math
asked 10 hours ago
jeremy radcliffjeremy radcliff
2,18112241
2,18112241
$begingroup$
Do you want the fewest steps to get to exactly $200$ or at least $200$?
$endgroup$
– John Douma
9 hours ago
$begingroup$
@JohnDouma: Exactly $200$, obviously. Otherwise eight steps would suffice.
$endgroup$
– TonyK
9 hours ago
$begingroup$
@TonyK That is not obvious. In fact, the last paragraph before the EDIT implies otherwise.
$endgroup$
– John Douma
9 hours ago
2
$begingroup$
@JohnDouma It's exactly $200$, but I disagree with your comment that the last paragraph implies otherwise. I can try to take as many X2 steps as I can and still intend to not get past $200$.
$endgroup$
– jeremy radcliff
9 hours ago
add a comment |
$begingroup$
Do you want the fewest steps to get to exactly $200$ or at least $200$?
$endgroup$
– John Douma
9 hours ago
$begingroup$
@JohnDouma: Exactly $200$, obviously. Otherwise eight steps would suffice.
$endgroup$
– TonyK
9 hours ago
$begingroup$
@TonyK That is not obvious. In fact, the last paragraph before the EDIT implies otherwise.
$endgroup$
– John Douma
9 hours ago
2
$begingroup$
@JohnDouma It's exactly $200$, but I disagree with your comment that the last paragraph implies otherwise. I can try to take as many X2 steps as I can and still intend to not get past $200$.
$endgroup$
– jeremy radcliff
9 hours ago
$begingroup$
Do you want the fewest steps to get to exactly $200$ or at least $200$?
$endgroup$
– John Douma
9 hours ago
$begingroup$
Do you want the fewest steps to get to exactly $200$ or at least $200$?
$endgroup$
– John Douma
9 hours ago
$begingroup$
@JohnDouma: Exactly $200$, obviously. Otherwise eight steps would suffice.
$endgroup$
– TonyK
9 hours ago
$begingroup$
@JohnDouma: Exactly $200$, obviously. Otherwise eight steps would suffice.
$endgroup$
– TonyK
9 hours ago
$begingroup$
@TonyK That is not obvious. In fact, the last paragraph before the EDIT implies otherwise.
$endgroup$
– John Douma
9 hours ago
$begingroup$
@TonyK That is not obvious. In fact, the last paragraph before the EDIT implies otherwise.
$endgroup$
– John Douma
9 hours ago
2
2
$begingroup$
@JohnDouma It's exactly $200$, but I disagree with your comment that the last paragraph implies otherwise. I can try to take as many X2 steps as I can and still intend to not get past $200$.
$endgroup$
– jeremy radcliff
9 hours ago
$begingroup$
@JohnDouma It's exactly $200$, but I disagree with your comment that the last paragraph implies otherwise. I can try to take as many X2 steps as I can and still intend to not get past $200$.
$endgroup$
– jeremy radcliff
9 hours ago
add a comment |
4 Answers
4
active
oldest
votes
$begingroup$
Look at what the operations $+$ and $times$ do to the binary expansion of a number:
$times$ appends a $0$, and increases the length by one, leaving the total number of $1$'s unchanged;- if the final digit is $0$, then $+$ increases the number of $1$'s by one, but doesn't change the length;
- if the final digit is $1$, then $+$ doesn't increase the total number of $1$'s (it may in fact decrease it), and doesn't increase the total length by more than $1$.
Therefore, with a single key press:
- you can increase the length by one, but this won't increase the number of $1$'s;
- you can increase the number of $1$'s by one, but this won't increase the length.
The binary expansion of $200$ is $200_10=11001000_2$. This has three $1$'s, and a length of eight. Starting from $1$, we must increase the length by seven, and increase the number of $1$'s by two. So this requires at least nine steps.
$endgroup$
$begingroup$
Beautiful, this allows you to determine the optimal solution and path for an arbitrary number from it's binary representation.
$endgroup$
– Jared Goguen
3 hours ago
$begingroup$
There actually exist two ways of getting $200$ using nine steps. $$1+1+1times2times2times2+1times2times2times2=200\ 1times2+1times2times2times2+1times2times2times2=200$$
$endgroup$
– Kay K.
3 hours ago
add a comment |
$begingroup$
You can proceed by induction on $n$, showing that the quickest way to reach any even number $2n$ involves doubling on the last step, which is clearly true for the base case $n=1$ (where doubling and adding $1$ have a tomato-tomahto relationship).
Now if the last step to reach $2n+2$ isn't doubling, it can only be adding $1$ from $2n+1$. But $2n+1$ can only be reached by adding $1$ from $2n$, at which point the inductive hypothesis says the next previous number was $n$. But you can get from $n$ to $2n+2$ more quickly in two steps: add $1$, then double. So the last step in the quickest route to $2n+2$ is doubling from $n+1$.
$endgroup$
$begingroup$
This is nice as it formalizes the OPs intuition, whereas the binary representation answer (which is super slick) might feel a little out of the blue.
$endgroup$
– jacob1729
6 hours ago
add a comment |
$begingroup$
Setting the display to binary base, $[times2]$ inserts a $0$ to the right and $[+1]$ increments; if the rightmost digit is a zero, it just turns it to a $1$.
Using these rules you build a number of $o$ ones and $z$ zeroes in $o-1+z$ keystrokes, starting from $1$. This seems close to optimal.
$endgroup$
$begingroup$
you just exactly reproduces the binary 200, why should we think it is not optimal?
$endgroup$
– dEmigOd
9 hours ago
$begingroup$
@dEmigOd: I didn't prove that inserting the bits one by one with $times2$ or $times2+1$ is optimal.
$endgroup$
– Yves Daoust
9 hours ago
add a comment |
$begingroup$
I'll make a try
Since $200=2^7+2^6+2^3$ you will need at least $8$ steps to reach $200$ (since we start from $1$ and we get a number of the form $2^a+...+2^l$) so it remains to show that $8$ steps are not enough.
Maybe you could try to show that if there was a solution with $8$ steps then it would contain only one $+1$ which contradicts the fact that in $200=2^7+2^6+2^3$ we have two $+$
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3151946%2ffewest-number-of-steps-to-reach-200-using-special-calculator%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Look at what the operations $+$ and $times$ do to the binary expansion of a number:
$times$ appends a $0$, and increases the length by one, leaving the total number of $1$'s unchanged;- if the final digit is $0$, then $+$ increases the number of $1$'s by one, but doesn't change the length;
- if the final digit is $1$, then $+$ doesn't increase the total number of $1$'s (it may in fact decrease it), and doesn't increase the total length by more than $1$.
Therefore, with a single key press:
- you can increase the length by one, but this won't increase the number of $1$'s;
- you can increase the number of $1$'s by one, but this won't increase the length.
The binary expansion of $200$ is $200_10=11001000_2$. This has three $1$'s, and a length of eight. Starting from $1$, we must increase the length by seven, and increase the number of $1$'s by two. So this requires at least nine steps.
$endgroup$
$begingroup$
Beautiful, this allows you to determine the optimal solution and path for an arbitrary number from it's binary representation.
$endgroup$
– Jared Goguen
3 hours ago
$begingroup$
There actually exist two ways of getting $200$ using nine steps. $$1+1+1times2times2times2+1times2times2times2=200\ 1times2+1times2times2times2+1times2times2times2=200$$
$endgroup$
– Kay K.
3 hours ago
add a comment |
$begingroup$
Look at what the operations $+$ and $times$ do to the binary expansion of a number:
$times$ appends a $0$, and increases the length by one, leaving the total number of $1$'s unchanged;- if the final digit is $0$, then $+$ increases the number of $1$'s by one, but doesn't change the length;
- if the final digit is $1$, then $+$ doesn't increase the total number of $1$'s (it may in fact decrease it), and doesn't increase the total length by more than $1$.
Therefore, with a single key press:
- you can increase the length by one, but this won't increase the number of $1$'s;
- you can increase the number of $1$'s by one, but this won't increase the length.
The binary expansion of $200$ is $200_10=11001000_2$. This has three $1$'s, and a length of eight. Starting from $1$, we must increase the length by seven, and increase the number of $1$'s by two. So this requires at least nine steps.
$endgroup$
$begingroup$
Beautiful, this allows you to determine the optimal solution and path for an arbitrary number from it's binary representation.
$endgroup$
– Jared Goguen
3 hours ago
$begingroup$
There actually exist two ways of getting $200$ using nine steps. $$1+1+1times2times2times2+1times2times2times2=200\ 1times2+1times2times2times2+1times2times2times2=200$$
$endgroup$
– Kay K.
3 hours ago
add a comment |
$begingroup$
Look at what the operations $+$ and $times$ do to the binary expansion of a number:
$times$ appends a $0$, and increases the length by one, leaving the total number of $1$'s unchanged;- if the final digit is $0$, then $+$ increases the number of $1$'s by one, but doesn't change the length;
- if the final digit is $1$, then $+$ doesn't increase the total number of $1$'s (it may in fact decrease it), and doesn't increase the total length by more than $1$.
Therefore, with a single key press:
- you can increase the length by one, but this won't increase the number of $1$'s;
- you can increase the number of $1$'s by one, but this won't increase the length.
The binary expansion of $200$ is $200_10=11001000_2$. This has three $1$'s, and a length of eight. Starting from $1$, we must increase the length by seven, and increase the number of $1$'s by two. So this requires at least nine steps.
$endgroup$
Look at what the operations $+$ and $times$ do to the binary expansion of a number:
$times$ appends a $0$, and increases the length by one, leaving the total number of $1$'s unchanged;- if the final digit is $0$, then $+$ increases the number of $1$'s by one, but doesn't change the length;
- if the final digit is $1$, then $+$ doesn't increase the total number of $1$'s (it may in fact decrease it), and doesn't increase the total length by more than $1$.
Therefore, with a single key press:
- you can increase the length by one, but this won't increase the number of $1$'s;
- you can increase the number of $1$'s by one, but this won't increase the length.
The binary expansion of $200$ is $200_10=11001000_2$. This has three $1$'s, and a length of eight. Starting from $1$, we must increase the length by seven, and increase the number of $1$'s by two. So this requires at least nine steps.
edited 6 hours ago
answered 9 hours ago
TonyKTonyK
43.4k357136
43.4k357136
$begingroup$
Beautiful, this allows you to determine the optimal solution and path for an arbitrary number from it's binary representation.
$endgroup$
– Jared Goguen
3 hours ago
$begingroup$
There actually exist two ways of getting $200$ using nine steps. $$1+1+1times2times2times2+1times2times2times2=200\ 1times2+1times2times2times2+1times2times2times2=200$$
$endgroup$
– Kay K.
3 hours ago
add a comment |
$begingroup$
Beautiful, this allows you to determine the optimal solution and path for an arbitrary number from it's binary representation.
$endgroup$
– Jared Goguen
3 hours ago
$begingroup$
There actually exist two ways of getting $200$ using nine steps. $$1+1+1times2times2times2+1times2times2times2=200\ 1times2+1times2times2times2+1times2times2times2=200$$
$endgroup$
– Kay K.
3 hours ago
$begingroup$
Beautiful, this allows you to determine the optimal solution and path for an arbitrary number from it's binary representation.
$endgroup$
– Jared Goguen
3 hours ago
$begingroup$
Beautiful, this allows you to determine the optimal solution and path for an arbitrary number from it's binary representation.
$endgroup$
– Jared Goguen
3 hours ago
$begingroup$
There actually exist two ways of getting $200$ using nine steps. $$1+1+1times2times2times2+1times2times2times2=200\ 1times2+1times2times2times2+1times2times2times2=200$$
$endgroup$
– Kay K.
3 hours ago
$begingroup$
There actually exist two ways of getting $200$ using nine steps. $$1+1+1times2times2times2+1times2times2times2=200\ 1times2+1times2times2times2+1times2times2times2=200$$
$endgroup$
– Kay K.
3 hours ago
add a comment |
$begingroup$
You can proceed by induction on $n$, showing that the quickest way to reach any even number $2n$ involves doubling on the last step, which is clearly true for the base case $n=1$ (where doubling and adding $1$ have a tomato-tomahto relationship).
Now if the last step to reach $2n+2$ isn't doubling, it can only be adding $1$ from $2n+1$. But $2n+1$ can only be reached by adding $1$ from $2n$, at which point the inductive hypothesis says the next previous number was $n$. But you can get from $n$ to $2n+2$ more quickly in two steps: add $1$, then double. So the last step in the quickest route to $2n+2$ is doubling from $n+1$.
$endgroup$
$begingroup$
This is nice as it formalizes the OPs intuition, whereas the binary representation answer (which is super slick) might feel a little out of the blue.
$endgroup$
– jacob1729
6 hours ago
add a comment |
$begingroup$
You can proceed by induction on $n$, showing that the quickest way to reach any even number $2n$ involves doubling on the last step, which is clearly true for the base case $n=1$ (where doubling and adding $1$ have a tomato-tomahto relationship).
Now if the last step to reach $2n+2$ isn't doubling, it can only be adding $1$ from $2n+1$. But $2n+1$ can only be reached by adding $1$ from $2n$, at which point the inductive hypothesis says the next previous number was $n$. But you can get from $n$ to $2n+2$ more quickly in two steps: add $1$, then double. So the last step in the quickest route to $2n+2$ is doubling from $n+1$.
$endgroup$
$begingroup$
This is nice as it formalizes the OPs intuition, whereas the binary representation answer (which is super slick) might feel a little out of the blue.
$endgroup$
– jacob1729
6 hours ago
add a comment |
$begingroup$
You can proceed by induction on $n$, showing that the quickest way to reach any even number $2n$ involves doubling on the last step, which is clearly true for the base case $n=1$ (where doubling and adding $1$ have a tomato-tomahto relationship).
Now if the last step to reach $2n+2$ isn't doubling, it can only be adding $1$ from $2n+1$. But $2n+1$ can only be reached by adding $1$ from $2n$, at which point the inductive hypothesis says the next previous number was $n$. But you can get from $n$ to $2n+2$ more quickly in two steps: add $1$, then double. So the last step in the quickest route to $2n+2$ is doubling from $n+1$.
$endgroup$
You can proceed by induction on $n$, showing that the quickest way to reach any even number $2n$ involves doubling on the last step, which is clearly true for the base case $n=1$ (where doubling and adding $1$ have a tomato-tomahto relationship).
Now if the last step to reach $2n+2$ isn't doubling, it can only be adding $1$ from $2n+1$. But $2n+1$ can only be reached by adding $1$ from $2n$, at which point the inductive hypothesis says the next previous number was $n$. But you can get from $n$ to $2n+2$ more quickly in two steps: add $1$, then double. So the last step in the quickest route to $2n+2$ is doubling from $n+1$.
edited 8 hours ago
answered 8 hours ago
Barry CipraBarry Cipra
60.3k654126
60.3k654126
$begingroup$
This is nice as it formalizes the OPs intuition, whereas the binary representation answer (which is super slick) might feel a little out of the blue.
$endgroup$
– jacob1729
6 hours ago
add a comment |
$begingroup$
This is nice as it formalizes the OPs intuition, whereas the binary representation answer (which is super slick) might feel a little out of the blue.
$endgroup$
– jacob1729
6 hours ago
$begingroup$
This is nice as it formalizes the OPs intuition, whereas the binary representation answer (which is super slick) might feel a little out of the blue.
$endgroup$
– jacob1729
6 hours ago
$begingroup$
This is nice as it formalizes the OPs intuition, whereas the binary representation answer (which is super slick) might feel a little out of the blue.
$endgroup$
– jacob1729
6 hours ago
add a comment |
$begingroup$
Setting the display to binary base, $[times2]$ inserts a $0$ to the right and $[+1]$ increments; if the rightmost digit is a zero, it just turns it to a $1$.
Using these rules you build a number of $o$ ones and $z$ zeroes in $o-1+z$ keystrokes, starting from $1$. This seems close to optimal.
$endgroup$
$begingroup$
you just exactly reproduces the binary 200, why should we think it is not optimal?
$endgroup$
– dEmigOd
9 hours ago
$begingroup$
@dEmigOd: I didn't prove that inserting the bits one by one with $times2$ or $times2+1$ is optimal.
$endgroup$
– Yves Daoust
9 hours ago
add a comment |
$begingroup$
Setting the display to binary base, $[times2]$ inserts a $0$ to the right and $[+1]$ increments; if the rightmost digit is a zero, it just turns it to a $1$.
Using these rules you build a number of $o$ ones and $z$ zeroes in $o-1+z$ keystrokes, starting from $1$. This seems close to optimal.
$endgroup$
$begingroup$
you just exactly reproduces the binary 200, why should we think it is not optimal?
$endgroup$
– dEmigOd
9 hours ago
$begingroup$
@dEmigOd: I didn't prove that inserting the bits one by one with $times2$ or $times2+1$ is optimal.
$endgroup$
– Yves Daoust
9 hours ago
add a comment |
$begingroup$
Setting the display to binary base, $[times2]$ inserts a $0$ to the right and $[+1]$ increments; if the rightmost digit is a zero, it just turns it to a $1$.
Using these rules you build a number of $o$ ones and $z$ zeroes in $o-1+z$ keystrokes, starting from $1$. This seems close to optimal.
$endgroup$
Setting the display to binary base, $[times2]$ inserts a $0$ to the right and $[+1]$ increments; if the rightmost digit is a zero, it just turns it to a $1$.
Using these rules you build a number of $o$ ones and $z$ zeroes in $o-1+z$ keystrokes, starting from $1$. This seems close to optimal.
answered 9 hours ago
Yves DaoustYves Daoust
130k676229
130k676229
$begingroup$
you just exactly reproduces the binary 200, why should we think it is not optimal?
$endgroup$
– dEmigOd
9 hours ago
$begingroup$
@dEmigOd: I didn't prove that inserting the bits one by one with $times2$ or $times2+1$ is optimal.
$endgroup$
– Yves Daoust
9 hours ago
add a comment |
$begingroup$
you just exactly reproduces the binary 200, why should we think it is not optimal?
$endgroup$
– dEmigOd
9 hours ago
$begingroup$
@dEmigOd: I didn't prove that inserting the bits one by one with $times2$ or $times2+1$ is optimal.
$endgroup$
– Yves Daoust
9 hours ago
$begingroup$
you just exactly reproduces the binary 200, why should we think it is not optimal?
$endgroup$
– dEmigOd
9 hours ago
$begingroup$
you just exactly reproduces the binary 200, why should we think it is not optimal?
$endgroup$
– dEmigOd
9 hours ago
$begingroup$
@dEmigOd: I didn't prove that inserting the bits one by one with $times2$ or $times2+1$ is optimal.
$endgroup$
– Yves Daoust
9 hours ago
$begingroup$
@dEmigOd: I didn't prove that inserting the bits one by one with $times2$ or $times2+1$ is optimal.
$endgroup$
– Yves Daoust
9 hours ago
add a comment |
$begingroup$
I'll make a try
Since $200=2^7+2^6+2^3$ you will need at least $8$ steps to reach $200$ (since we start from $1$ and we get a number of the form $2^a+...+2^l$) so it remains to show that $8$ steps are not enough.
Maybe you could try to show that if there was a solution with $8$ steps then it would contain only one $+1$ which contradicts the fact that in $200=2^7+2^6+2^3$ we have two $+$
$endgroup$
add a comment |
$begingroup$
I'll make a try
Since $200=2^7+2^6+2^3$ you will need at least $8$ steps to reach $200$ (since we start from $1$ and we get a number of the form $2^a+...+2^l$) so it remains to show that $8$ steps are not enough.
Maybe you could try to show that if there was a solution with $8$ steps then it would contain only one $+1$ which contradicts the fact that in $200=2^7+2^6+2^3$ we have two $+$
$endgroup$
add a comment |
$begingroup$
I'll make a try
Since $200=2^7+2^6+2^3$ you will need at least $8$ steps to reach $200$ (since we start from $1$ and we get a number of the form $2^a+...+2^l$) so it remains to show that $8$ steps are not enough.
Maybe you could try to show that if there was a solution with $8$ steps then it would contain only one $+1$ which contradicts the fact that in $200=2^7+2^6+2^3$ we have two $+$
$endgroup$
I'll make a try
Since $200=2^7+2^6+2^3$ you will need at least $8$ steps to reach $200$ (since we start from $1$ and we get a number of the form $2^a+...+2^l$) so it remains to show that $8$ steps are not enough.
Maybe you could try to show that if there was a solution with $8$ steps then it would contain only one $+1$ which contradicts the fact that in $200=2^7+2^6+2^3$ we have two $+$
answered 9 hours ago
giannispapavgiannispapav
1,826325
1,826325
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3151946%2ffewest-number-of-steps-to-reach-200-using-special-calculator%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
Do you want the fewest steps to get to exactly $200$ or at least $200$?
$endgroup$
– John Douma
9 hours ago
$begingroup$
@JohnDouma: Exactly $200$, obviously. Otherwise eight steps would suffice.
$endgroup$
– TonyK
9 hours ago
$begingroup$
@TonyK That is not obvious. In fact, the last paragraph before the EDIT implies otherwise.
$endgroup$
– John Douma
9 hours ago
2
$begingroup$
@JohnDouma It's exactly $200$, but I disagree with your comment that the last paragraph implies otherwise. I can try to take as many X2 steps as I can and still intend to not get past $200$.
$endgroup$
– jeremy radcliff
9 hours ago