Arithmetic Puzzle

Question

The problem is as follows:

We start with the number $\mathbf 1$. The puzzle consists of $6$ steps. At each step, we can choose to do an operation on the resulting number we have at that step. The goal of the puzzle is to somehow reach the number $\mathbf{49}$. Each operation must be used exactly once. Here are the permitted operations we can do:

$\bullet \times 2$

$\bullet \times 3$

$\bullet \times 5$

$\bullet +2$

$\bullet +3$

$\bullet +5$

Now this might seem like an easy problem to you (maybe it is), but I haven’t been able to do any good. I tried wildly guessing ways to do this in vain. I certainly don’t intend to check all $6!$ ways (lesser than that, but still too many).

Here is a valid combination as an example:

$$1 \overset{\times 5}{\longrightarrow} 5 \overset{+2}{\longrightarrow} 7 \overset{\times 3}{\longrightarrow} 21 \overset{\times 2}{\longrightarrow} 42 \overset{+5}{\longrightarrow} 47 \overset{+3}{\longrightarrow} 50$$

Can anyone spot a solution to this puzzle? And more importantly, is there an analytical way to go about this?

Answer 1

The last step must be an addition because $49$ is not divisible by $2,3,5$. If we perform several additions or several multiplications in sequence, we may agree to perform them as one (e.g., as $+5,+3$ as $+8$ or $\times 2,\times 3$ as $\times 6$)

So we end with one of $+2,+3,+5,+7,+8,+10$, i.e., we cam by multiplication to one of $47,46,44,42,41,39$. By looking at feasible factors (in particular, ruling out the primes), the only possible paths are $$ 49\stackrel{+3}\leftarrow 46\stackrel{\times 2}\leftarrow 23\\ 49\stackrel{+5}\leftarrow 44\stackrel{\times 2}\leftarrow 22\\ 49\stackrel{+7}\leftarrow 42\stackrel{\times 6}\leftarrow 7\\ 49\stackrel{+7}\leftarrow 42\stackrel{\times 3}\leftarrow 14\\ 49\stackrel{+7}\leftarrow 42\stackrel{\times 2}\leftarrow 21\\ 49\stackrel{+10}\leftarrow 39\stackrel{\times 3}\leftarrow 13 $$ In the last case, we used up all additions and have lost. In rows three to five, the only addition left is $+3$, but $4, 11, 18$ are out of reach by multiplication alone. So prepending the next (cluster of) additions, we only need to deal with (more forced operations also prepended) $$ 49\stackrel{+3}\leftarrow 46\stackrel{\times 2}\leftarrow 23\stackrel{+2}\leftarrow21\stackrel{\times3}\leftarrow7\stackrel{+5}\leftarrow2\\ 49\stackrel{+3}\leftarrow 46\stackrel{\times 2}\leftarrow 23\stackrel{+5}\leftarrow18\stackrel{\times3}\leftarrow6\stackrel{+2}\leftarrow4\\ 49\stackrel{+3}\leftarrow 46\stackrel{\times 2}\leftarrow 23\stackrel{+7}\leftarrow16\\ 49\stackrel{+5}\leftarrow 44\stackrel{\times 2}\leftarrow 22\stackrel{+2}\leftarrow 20\stackrel{\times 5}\leftarrow 4\stackrel{+3}\leftarrow1\\ 49\stackrel{+5}\leftarrow 44\stackrel{\times 2}\leftarrow 22\stackrel{+3}\leftarrow 19\\ 49\stackrel{+5}\leftarrow 44\stackrel{\times 2}\leftarrow 22\stackrel{+5}\leftarrow 17\\ $$ All dead ends ...

Answer 2

Hagen von Eitzen manually searches all steps in their answer, but

I wrote a quick python script to automate this for any number and any set of operations:

def solve(goal,ops,end=0,moves=[]):
    if len(ops)>end:
        for op in ops:
            # we apply "/" operation only if result is integer
            if (op[1] == "/" and goal%op[0]==0) or op[1] != "/":
                ops_ = set(ops)
                ops_.remove(op)
                goal_ = eval(f"{goal}{op[1]}{op[0]}")
                case = solve(goal_,ops_,end,moves[:]+[op])
                # print path only if path is valid and we reached 1
                if case != [] and case != None and case[0]==1:
                    print(case)
    else:
        return (goal,ops,moves)

Our problem is defined as: (we search in reverse)

goal = 49
ops = set([(2,"-"),(3,"-"),(5,"-"),(2,"/"),(3,"/"),(5,"/")])

---

When we try to use all $6$ out of $6$ operations:

solve(goal,ops,end=0)

We get no solutions are possible.

---

When we try to use $5$ out of $6$ operations:

solve(goal,ops,end=1)

We get a unique solution:

[(5, '-'), (2, '/'), (2, '-'), (5, '/'), (3, '-')]

That uses every operation exactly once except $(\times 3)$.

Which translates to $1(+3)\to 4 (\times 5)\to 20 (+ 2 )\to 22 (\times 2 )\to 44 (+ 5 )\to 49$.

Answer 3

I couldn't resist to write a MiniZinc model:

include "globals.mzn";

int: steps = 6;
set of int: Steps = 1..steps;

%  operations comprise a factor and an increment
array[Steps] of int: factors    = [2, 3, 5, 1, 1, 1];
array[Steps] of int: increments = [0, 0, 0, 2, 3, 5];

%  order of operations
array[Steps] of var Steps: op;

int: StartValue = 1;
int: EndValue = 49;

function var int: f(0..steps: step) = 
  if step == 0 then 
    StartValue
  else
    increments[op[step]] + factors[op[step]] * f(step-1)
  endif;

constraint
  all_different(op);

constraint
  EndValue == f(steps);

output [if factors[fix(op[i])] == 1 then " +" ++ show(increments[op[i]]) 
                                    else " *" ++ show(factors[op[i]]) 
        endif | i in Steps];

My model constructs operations by composing a factor and an increment. The factor may be $1$. The increment may be $0$.

As described in other answers, $49$ cannot be reached in $6$ unique operations.

Example solution for $53$:

*5 +2 *3 +3 *2 +5

Answer 4

There is a much simpler solution than the other existing answers. Performing ${}×2×3×5$ before ${}+2+3+5$ yields $40$, which is $9$ short. Shifting any ${}+k$ before any two multiplication operations increases the result by at least $k·(2×3-1) ≥ 10$. Thus additions must all come after the first two multiplications. But changing $x×k+y$ to $(x+y)×k$ yields an increase of $y·(k-1)$, so to get an increase of $9$ we need $(k,y) = (2,9)$ since $3-1 \nmid 9$ and $5-1 \nmid 9$, which is impossible since $9$ is not the sum of any subset of $\{2,3,5\}$.