8
$\begingroup$

A calculator has only 2 buttons. The first multiplies the current value by 2, the second divides it by 3 without a remainder (so 8 becomes 2). Starting with 1 what is the least number of presses you need to reach 9?

Here is a similar question: Three button calculator

Improve this question
$\endgroup$

3 Answers 3

Reset to default
5
$\begingroup$

I found the fewest number of button presses as

11 presses.

We get

9 by multiplying 1 by 2 eight times, giving 256, and then dividing by 3 three times. 256 -> 85 -> 28 -> 9.

I don't see a possibility to do it in fewer, but I'll try to prove it.

EDIT:

Following the comment below, I continued searching and found another five solutions for n = 11.

These are:

1 -> 2 -> 4 -> 8 -> 16 -> 32 -> 64 -> 128 -> 42 -> 84 -> 28 -> 9
1 -> 2 -> 4 -> 8 -> 16 -> 32 -> 64 -> 128 -> 42 -> 14 -> 28 -> 9
1 -> 2 -> 4 -> 8 -> 16 -> 32 -> 64 -> 21 -> 42 -> 84 -> 28 -> 9
1 -> 2 -> 4 -> 8 -> 16 -> 32 -> 64 -> 21 -> 42 -> 14 -> 28 -> 9
1 -> 2 -> 4 -> 8 -> 16 -> 32 -> 64 -> 21 -> 7 -> 14 -> 28 -> 9

Improve this answer
$\endgroup$
6
  • $\begingroup$ My intended answer also uses 11 presses, but arrives there very differently. Fascinating. $\endgroup$
    – Dmitry Kamenetsky
    Nov 12, 2019 at 16:54
  • 1
    $\begingroup$ Using a computer, I can verify that it is indeed the minimun number of presses needed. $\endgroup$
    – WhatsUp
    Nov 12, 2019 at 16:59
  • $\begingroup$ There's only a thousand ($2^{10}$) possibilities to rule out, so checking with brute force should be pretty trivial. $\endgroup$
    – Bass
    Nov 12, 2019 at 16:59
  • 1
    $\begingroup$ But note that changing the number $9$ to something like $121$ or $127$ would indeed make the puzzle more challenging. $\endgroup$
    – WhatsUp
    Nov 12, 2019 at 17:02
  • $\begingroup$ I updated my answer to include the remaining 5 solutions requiring 11 presses. $\endgroup$
    – user63738
    Nov 12, 2019 at 17:05
3
$\begingroup$

Computerless proof that CDJB's solution is best possible (which also finds all possible solutions in that many steps, though I haven't filled in the details of that part since you can see the explicit solutions in CDJB's answer):

We can get to 9 only from 27, 28, or 29. (One step.) We can get to those from anything in [81,89] -- this notation denotes a closed interval, including its endpoints -- or by doubling 14. (Two steps.) We can get to those from anything in [243,269], or anything in [41,44], or by doubling 7. (Three steps.) We can already see a solution by doubling 8 times to reach 256. We don't have enough doublings available to get into [243,269] in fewer than 8 more steps, so if there's a solution that uses fewer than 11 in total it must go via [41,44] or 7. We can get to those from anything in [123,134] or [21,23] or by doubling 21 or 22 -- note that those last two don't add anything to the [21,23] we already had. (Four steps.) Again we can see that we could go via 128 in 11 steps; if we use fewer steps we can't reach [123,134] with the number of doublings available, so we'd have to go via [21,23]. We can get to those from anything in [63,71] or by doubling 11. (Five steps.) Again we could use 64, and now everything that's left is out of range if we use <=5 more steps, since that can't take us above 32. Done.

Credit where due: isaacg pointed out, in comments, a couple of bugs in my analysis, and while fixing those I found another one. Thanks, isaacg!

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ You left out a couple posibilities, making this proof not quite rigorous. For instance, the sequence 41 -> 82 -> 27 -> 9 is a possibility you omit. Likewise, 11 -> 22 -> 7 -> 14 -> 28 -> 9. If you fix these couple of bugs, the proof should be fine. $\endgroup$
    – isaacg
    Nov 13, 2019 at 17:27
  • 2
    $\begingroup$ Yup, those are bugs. (One was an arithmetic error, one was actually overlooking a possibility.) I found another little bug too. I think I've fixed them all now. $\endgroup$
    – Gareth McCaughan ♦
    Nov 14, 2019 at 0:08
2
$\begingroup$

This is very straightforward. The only rule is not continuing to lower level in case there would be a number repeat.

enter image description here

Improve this answer
$\endgroup$

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.