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













12












$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.










share|cite|improve this question









$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















12












$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.










share|cite|improve this question









$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













12












12








12


4



$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.










share|cite|improve this question









$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






share|cite|improve this question













share|cite|improve this question











share|cite|improve this question




share|cite|improve this question










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
















  • $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










4 Answers
4






active

oldest

votes


















30












$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.






share|cite|improve this answer











$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



















7












$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$.






share|cite|improve this answer











$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


















4












$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.






share|cite|improve this answer









$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


















3












$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 $+$






share|cite|improve this answer









$endgroup$












    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
    );



    );













    draft saved

    draft discarded


















    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









    30












    $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.






    share|cite|improve this answer











    $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
















    30












    $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.






    share|cite|improve this answer











    $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














    30












    30








    30





    $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.






    share|cite|improve this answer











    $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.







    share|cite|improve this answer














    share|cite|improve this answer



    share|cite|improve this answer








    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

















    • $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












    7












    $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$.






    share|cite|improve this answer











    $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















    7












    $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$.






    share|cite|improve this answer











    $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













    7












    7








    7





    $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$.






    share|cite|improve this answer











    $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$.







    share|cite|improve this answer














    share|cite|improve this answer



    share|cite|improve this answer








    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
















    • $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











    4












    $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.






    share|cite|improve this answer









    $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















    4












    $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.






    share|cite|improve this answer









    $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













    4












    4








    4





    $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.






    share|cite|improve this answer









    $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.







    share|cite|improve this answer












    share|cite|improve this answer



    share|cite|improve this answer










    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
















    • $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











    3












    $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 $+$






    share|cite|improve this answer









    $endgroup$

















      3












      $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 $+$






      share|cite|improve this answer









      $endgroup$















        3












        3








        3





        $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 $+$






        share|cite|improve this answer









        $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 $+$







        share|cite|improve this answer












        share|cite|improve this answer



        share|cite|improve this answer










        answered 9 hours ago









        giannispapavgiannispapav

        1,826325




        1,826325



























            draft saved

            draft discarded
















































            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.




            draft saved


            draft discarded














            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





















































            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







            Popular posts from this blog

            Францішак Багушэвіч Змест Сям'я | Біяграфія | Творчасць | Мова Багушэвіча | Ацэнкі дзейнасці | Цікавыя факты | Спадчына | Выбраная бібліяграфія | Ушанаванне памяці | У філатэліі | Зноскі | Літаратура | Спасылкі | НавігацыяЛяхоўскі У. Рупіўся дзеля Бога і людзей: Жыццёвы шлях Лявона Вітан-Дубейкаўскага // Вольскі і Памідораў з песняй пра немца Адвакат, паэт, народны заступнік Ашмянскі веснікВ Минске появится площадь Богушевича и улица Сырокомли, Белорусская деловая газета, 19 июля 2001 г.Айцец беларускай нацыянальнай ідэі паўстаў у бронзе Сяргей Аляксандравіч Адашкевіч (1918, Мінск). 80-я гады. Бюст «Францішак Багушэвіч».Яўген Мікалаевіч Ціхановіч. «Партрэт Францішка Багушэвіча»Мікола Мікалаевіч Купава. «Партрэт зачынальніка новай беларускай літаратуры Францішка Багушэвіча»Уладзімір Іванавіч Мелехаў. На помніку «Змагарам за родную мову» Барэльеф «Францішак Багушэвіч»Памяць пра Багушэвіча на Віленшчыне Страчаная сталіца. Беларускія шыльды на вуліцах Вільні«Krynica». Ideologia i przywódcy białoruskiego katolicyzmuФранцішак БагушэвічТворы на knihi.comТворы Францішка Багушэвіча на bellib.byСодаль Уладзімір. Францішак Багушэвіч на Лідчыне;Луцкевіч Антон. Жыцьцё і творчасьць Фр. Багушэвіча ў успамінах ягоных сучасьнікаў // Запісы Беларускага Навуковага таварыства. Вільня, 1938. Сшытак 1. С. 16-34.Большая российская1188761710000 0000 5537 633Xn9209310021619551927869394п

            Беларусь Змест Назва Гісторыя Геаграфія Сімволіка Дзяржаўны лад Палітычныя партыі Міжнароднае становішча і знешняя палітыка Адміністрацыйны падзел Насельніцтва Эканоміка Культура і грамадства Сацыяльная сфера Узброеныя сілы Заўвагі Літаратура Спасылкі НавігацыяHGЯOiТоп-2011 г. (па версіі ej.by)Топ-2013 г. (па версіі ej.by)Топ-2016 г. (па версіі ej.by)Топ-2017 г. (па версіі ej.by)Нацыянальны статыстычны камітэт Рэспублікі БеларусьШчыльнасць насельніцтва па краінахhttp://naviny.by/rubrics/society/2011/09/16/ic_articles_116_175144/А. Калечыц, У. Ксяндзоў. Спробы засялення краю неандэртальскім чалавекам.І ў Менску былі мамантыА. Калечыц, У. Ксяндзоў. Старажытны каменны век (палеаліт). Першапачатковае засяленне тэрыторыіГ. Штыхаў. Балты і славяне ў VI—VIII стст.М. Клімаў. Полацкае княства ў IX—XI стст.Г. Штыхаў, В. Ляўко. Палітычная гісторыя Полацкай зямліГ. Штыхаў. Дзяржаўны лад у землях-княствахГ. Штыхаў. Дзяржаўны лад у землях-княствахБеларускія землі ў складзе Вялікага Княства ЛітоўскагаЛюблінская унія 1569 г."The Early Stages of Independence"Zapomniane prawdy25 гадоў таму было аб'яўлена, што Язэп Пілсудскі — беларус (фота)Наша вадаДакументы ЧАЭС: Забруджванне тэрыторыі Беларусі « ЧАЭС Зона адчужэнняСведения о политических партиях, зарегистрированных в Республике Беларусь // Министерство юстиции Республики БеларусьСтатыстычны бюлетэнь „Полаўзроставая структура насельніцтва Рэспублікі Беларусь на 1 студзеня 2012 года і сярэднегадовая колькасць насельніцтва за 2011 год“Индекс человеческого развития Беларуси — не было бы нижеБеларусь занимает первое место в СНГ по индексу развития с учетом гендерного факцёраНацыянальны статыстычны камітэт Рэспублікі БеларусьКанстытуцыя РБ. Артыкул 17Трансфармацыйныя задачы БеларусіВыйсце з крызісу — далейшае рэфармаванне Беларускі рубель — сусветны лідар па дэвальвацыяхПра змену коштаў у кастрычніку 2011 г.Бядней за беларусаў у СНД толькі таджыкіСярэдні заробак у верасні дасягнуў 2,26 мільёна рублёўЭканомікаГаласуем за ТОП-100 беларускай прозыСучасныя беларускія мастакіАрхитектура Беларуси BELARUS.BYА. Каханоўскі. Культура Беларусі ўсярэдзіне XVII—XVIII ст.Анталогія беларускай народнай песні, гуказапісы спеваўБеларускія Музычныя IнструментыБеларускі рок, які мы страцілі. Топ-10 гуртоў«Мясцовы час» — нязгаслая легенда беларускай рок-музыкіСЯРГЕЙ БУДКІН. МЫ НЯ ЗНАЕМ СВАЁЙ МУЗЫКІМ. А. Каладзінскі. НАРОДНЫ ТЭАТРМагнацкія культурныя цэнтрыПублічная дыскусія «Беларуская новая пьеса: без беларускай мовы ці беларуская?»Беларускія драматургі па-ранейшаму лепш ставяцца за мяжой, чым на радзіме«Працэс незалежнага кіно пайшоў, і дзяржаву турбуе яго непадкантрольнасць»Беларускія філосафы ў пошуках прасторыВсе идём в библиотекуАрхіваванаАб Нацыянальнай праграме даследавання і выкарыстання касмічнай прасторы ў мірных мэтах на 2008—2012 гадыУ космас — разам.У суседнім з Барысаўскім раёне пабудуюць Камандна-вымяральны пунктСвяты і абрады беларусаў«Мірныя бульбашы з малой краіны» — 5 непраўдзівых стэрэатыпаў пра БеларусьМ. Раманюк. Беларускае народнае адзеннеУ Беларусі скарачаецца колькасць злачынстваўЛукашэнка незадаволены мінскімі ўладамі Крадзяжы складаюць у Мінску каля 70% злачынстваў Узровень злачыннасці ў Мінскай вобласці — адзін з самых высокіх у краіне Генпракуратура аналізуе стан са злачыннасцю ў Беларусі па каэфіцыенце злачыннасці У Беларусі стабілізавалася крымінагеннае становішча, лічыць генпракурорЗамежнікі сталі здзяйсняць у Беларусі больш злачынстваўМУС Беларусі турбуе рост рэцыдыўнай злачыннасціЯ з ЖЭСа. Дазволіце вас абкрасці! Рэйтынг усіх службаў і падраздзяленняў ГУУС Мінгарвыканкама вырасАб КДБ РБГісторыя Аператыўна-аналітычнага цэнтра РБГісторыя ДКФРТаможняagentura.ruБеларусьBelarus.by — Афіцыйны сайт Рэспублікі БеларусьСайт урада БеларусіRadzima.org — Збор архітэктурных помнікаў, гісторыя Беларусі«Глобус Беларуси»Гербы и флаги БеларусиАсаблівасці каменнага веку на БеларусіА. Калечыц, У. Ксяндзоў. Старажытны каменны век (палеаліт). Першапачатковае засяленне тэрыторыіУ. Ксяндзоў. Сярэдні каменны век (мезаліт). Засяленне краю плямёнамі паляўнічых, рыбакоў і збіральнікаўА. Калечыц, М. Чарняўскі. Плямёны на тэрыторыі Беларусі ў новым каменным веку (неаліце)А. Калечыц, У. Ксяндзоў, М. Чарняўскі. Гаспадарчыя заняткі ў каменным векуЭ. Зайкоўскі. Духоўная культура ў каменным векуАсаблівасці бронзавага веку на БеларусіФарміраванне супольнасцей ранняга перыяду бронзавага векуФотографии БеларусиРоля беларускіх зямель ва ўтварэнні і ўмацаванні ВКЛВ. Фадзеева. З гісторыі развіцця беларускай народнай вышыўкіDMOZGran catalanaБольшая российскаяBritannica (анлайн)Швейцарскі гістарычны15325917611952699xDA123282154079143-90000 0001 2171 2080n9112870100577502ge128882171858027501086026362074122714179пппппп

            Герб Смалявічаў Апісанне | Спасылкі | НавігацыяГерб города Смолевичип