6
$\begingroup$

A calculator only has 2 buttons. The buttons are, however, very powerful: they are programmable buttons, i.e. you can pre-set them to be any function (meaning any map from $\mathbb{Z}$ to $\mathbb{Z}$).

The calculator always starts with $1$. After you pre-set the buttons, a target number will be announced, and you need to get to that number by pressing as few buttons as possible.

Given that the target number is between $1$ and $10000$ (both inclusive), and that you want to minimize the number of button presses in the worst case, what is your strategy of setting the buttons?

Give as answer:

  • a description of the button settings;
  • a proof of the minimum number of presses needed (or an upper bound of that) with your settings.

In case optimality cannot be proved, the answer with the smallest provable bound wins. If an answer proves that itself is optimal, then of course it automatically wins.

Improve this question
$\endgroup$
8
  • 3
    $\begingroup$ "In case optimality cannot be proved, the answer with the smallest provable bound wins." -1: This seems like a game rather than a puzzle. It has the exact problems with 'answer invalidation' that I talked about here. $\endgroup$
    – Deusovi ♦
    Nov 12, 2019 at 18:18
  • 1
    $\begingroup$ @Deusovi As a mathematical question, it is a priori not always possible to get a provably optimal answer. So you think in that case it should't be posted as a puzzle? $\endgroup$
    – WhatsUp
    Nov 12, 2019 at 20:34
  • 3
    $\begingroup$ -1 too, for a different reason: there are too many trivial mappings from numbers from 1 to 10000 to nodes of a binary tree of depth 13. In fact you can just enumerate your mapping and it'll automatically be a solution. Or in other words, it's not even a puzzle. $\endgroup$
    – Voile
    Nov 14, 2019 at 4:00
  • 2
    $\begingroup$ @Voile I disagree with your argument. The definition of "triviality" is totally subjective. You are basically saying that "easy" puzzles shouldn't be posted (whatever easy means). And keep in mind that I was preparing a "super-button calculator II" question, of which this one could be a preliminary. Now you are discouraging me so much that I'd leave this unfriendly community. $\endgroup$
    – WhatsUp
    Nov 14, 2019 at 9:32
  • 2
    $\begingroup$ Have to be honest, I originally voted to close this question as too broad due to the potential open-ended nature of it, but seeing @hexomino's very elegant solution made me change my mind entirely and I then voted to reopen it. I think this is a good example of a question where a gut reaction can turn out to be wrong (in my case certainly) - the answer is really very satisfying. WhatsUp - don't give up! Negative feedback is all part of the process of learning how to improve (or how to grow thicker skin!). Keep at it! :) $\endgroup$
    – Stiv
    Nov 14, 2019 at 11:00

1 Answer 1

Reset to default
16
$\begingroup$

The 2 buttons can do the following

Button 1: Multiply by 2
Button 2: Multiply by 2, then add 1

With these settings we can reach any target in at most

13 steps

Proof that this is minimal

If we represent each number in binary, then the actions are equivalent to appending a 0 or appending a 1. This means that there is a distinct path to each number using these buttons. Hence, we have maximised the range acheieved from combinations of our two buttons. Since $10000 < 2^{14} - 1$, it will have 14 digits in its binary expansion and each smaller number can be reached by appending at most 13 1s or 0s to 1.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Great answer (: Note that the optimality proof can be done with $2^{12} + 2^{11} + \cdots + 1 < 10000$. $\endgroup$
    – WhatsUp
    Nov 12, 2019 at 21:22
  • $\begingroup$ Hmm does the proof prove that button 2 must add, rather than subtract? (I know that's more oblique than it needs to be, but I'm trying to respect the spoiler blocks.) $\endgroup$
    – Roger
    Nov 14, 2019 at 22:18
  • $\begingroup$ @Roger the proof shows that the solution is optimal. There can still be other optimal solutions. $\endgroup$
    – Bass
    Nov 16, 2019 at 7:11
  • $\begingroup$ Great answer. Optimality can also proved via numbering the nodes of a binary( 2 operations) tree in which each node has 2 children - the results of both operations with root 1. $\endgroup$
    – sudhackar
    Dec 3, 2019 at 10:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.