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
    Commented 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
    Commented 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
    Commented 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
    Commented Nov 12, 2019 at 17:02
  • $\begingroup$ I updated my answer to include the remaining 5 solutions requiring 11 presses. $\endgroup$
    – user63738
    Commented 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
    Commented 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 ♦
    Commented 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$

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