Getting to 17

Starting with 1:

• $\times 3 = 3$
• $+ 1 = 4$
• $+ 1 = 5$
• $\times 3 = 15$
• $+ 1 = 16$
• $+ 1 = 17$

6 steps!

This is more intuitive if you think in base 3, where multiplying by 3 is the same as adding a 0 to the end.

$17_{10} = 122_3$

The biggest constraint is that we should include $5 \times 3$ since that is the biggest step. The fastest way to get to $5$ is $1 \times 3 + 1 + 1 = 5$ . After $5 \times 3 = 15$ , the only way to $17$ from here is $1 + 1$ , giving a total of $\boxed{6}$ turns

Apply reverse thinking in finding the answer.

It is equivalent to find how to get to 1 from 17, using -1 and ÷3.

The advantage is that you can easily determine if ÷3 can be used, by checking the divisibility of 3.

Hence,

17-1=16

16-1=15, which is divisible by 3.

15÷3=5

5-1=4

4-1=3, which is divisible by 3.

3÷3=1

Therefore, 6 steps are required at least.

General solution

Write the final number in ternary (base 3) notation. Let $N$ be the number of ternary digits and $S$ the sum of the digits. Then the minimum number of steps is $X = S + N - 2.$ In this case, $17_{10} = 122_3$ , so that $N = 3$ , $S = 1 + 2 + 2 = 5$ and $X = 3 + 5 - 2 = \boxed{6}$ .

Reasoning

In ternary notation, the two operations we are allowed are:

• adding one to the final digit

• shifting all digits left (i.e. add a zero to the end)

We build the number digit by digit. The number of additions we must perform is one less than the digit sum, $A = S - 1$ . (One less, because we are given 1 at the beginning.)

The number of multiplications is one less than the number of digits, $M = N - 1$ . (One less, because we start with one digit.)

Adding gives $A + M = S + N - 2$ .

The only thing missing in this approach is the proof that this is indeed the minimum. The basic idea of this proof is that any sequence of three or more additions can be replaced by something more efficient. Thus, $MAAA \mapsto AM$ .

Let's reason backwards and consider every possible case:

Let $A_n$ be the set of numbers from which you can reach $17$ in $n$ moves:

• $A_0 = \left\{ 17 \right\}$ (duh!)

• $A_1 = \left\{ 16 \right\}$ (17 is reachable only from 16)

• $A_2 = \left\{ 15 \right\}$ (16 is reachable only from 15)

• $A_3 = \left\{ 5, 14 \right\}$ (15 is reachable from either 5 or 14, because it's a multiple of 3)

• $A_4 = \left\{ 4, 13 \right\}$ (5 is reachable from 4; 14 from 13)

• $A_5 = \left\{ 3, 12 \right\}$ (4 is reachable from 3; 13 from 12)

• $A_6 = \left\{ 1, 2, 4, 11 \right\}$ (3 is reachable from either 1 (yay!) or 2; 12 from either 4 or 11)

So the minimum number of moves is $6$ .

We let $A(n)$ to be the minimum number of actions needed. If we think intuitively, the recursive form of $A(n)$ is $A(n)= \begin{cases} A(n-1)+1 & \text{if } n>1 \text{ and is indivisible by 3}\\ \text{min}(A(n/3)+1, A(n-1)+1) & \text{if } n>1 \text{ and is divisible by 3}\\ 0 & \text{if } n=1 \end{cases}$ Of course, $A(n/3)$ might be a greater choice for the value to be minimum than $A(n-1)$ , but you also want to know why it's true. An important observation here is that, for any three consecutive integers there must exists a number among them which is divisible by $3$ . That can be proven by induction.

Then, if $n/3$ (assuming $n$ is divisible by $3$ ) is an another integer indivisible by three then either $n/3-1$ or $n/3-2$ must be divisible by three, in this case it seems like this is a great case for minimizing the number of actions by doing either $A((n/3-1)/3)$ or $A((n/3-2)/3)$ . If $n/3$ is also divisible by three (which is another luck), we can just do $A((n/3)/3)$ . (In fact, this is more likely a "greedy approach".)

From this observation, we transform $A(n)$ to be $A(n)= \begin{cases} A(n-1)+1 & \text{if } n>1 \text{ and is indivisible by 3}\\ A(n/3)+1 & \text{if } n>1 \text{ and is divisible by 3}\\ 0 & \text{if } n=1 \end{cases}$

and the result is $A(17) = A(16) + 1 = A(15) + 2 = A(5) + 3 = A(4) + 4 = A(3) + 5 = A(1) + 6 = \boxed{6}.$ Backtracking always helps.

I started from 17 and turned it into 1. The rules would be "subtract 1" and "divide by 3". Since division is more 'stricter' than multiply, I would be forced to reach a multiple of 3 by subtracting first.

• subtract 1 $(17-1 = 16)$
• subtract 1 $(17-1 = 15)$
• divide by 3 $(15/3 = 5)$
• subtract 1 $(5-1 = 4)$
• subtract 1 $(4-1 = 3)$
• divide by 3 $(3/3 = 1)$

The best way I could see approaching this problem is by thinking of it as a graph problem. The root node is 1 and every child child is reached by either multiplying by 3 or adding 1 to the previous node. So that the $v_{i+1}$ -th node is either $3 v_{i}$ or $v_{i}+1$ . The easiest way to traverse the tree and determine bad paths is by either reaching a node which could have otherwise been traversed faster, or by taking the biggest step possible at each iteration.

We can formulate a similar problem by thinking of $3n+1=17$ which yields 5R1. This gives us an idea of how close we can get by multiplication alone. The idea then is to get to 5 in the least amount of moves as possible, then to 15, then to 17.

((1×3)+1+1)×3+1+1=17. So the total is 6 turns.

why just not thinking that a number obtained on multiplying by 3 must be a multiple of 3! So all you need to do is generate multiples of 3 by reducing 17 by one which would yield 15! now divide by 3 to get 5 subtract 1 two times n divide by 3

the problem appears easy here but I think the smart mathematicians must try for 6565 this might outsmart you;)

The closer number to 17 which you can multiply by 3 is 15.

Equivalent problem: starting at $17$ , make way to $1$ using one of two operations: $n \rightarrow n-1$ or $n \rightarrow n/3$ . In this case, division can only be used at multiples of $3$ , so the first two steps have to be subtraction. Next, observe that a greedy strategy is optimal, since it's faster to divide by $3$ and subtract $1$ (two steps) than subtract $3$ and then divide by $3$ (four steps).

Thus the optimal path is $17 \rightarrow 16 \rightarrow 15 \rightarrow 5 \rightarrow 4 \rightarrow 3 \rightarrow 1$

I found it helpful to work backwards from 17. Since 17 and 16 are not divisible by 3, you will not reach those values directly by multiplying by 3. This means that that the last two steps are going to be adding 1 to some number. When we get to 15, that is thankfully divisible by 3, so we can get to the number 5 by dividing 15 by 3. Following the same logic, we subtract one to get to 4, then 3. Dividing 3 by 3, we get back to 1 which was the starting point. Counting the steps here, it is six steps.

I tried to come up with another solution that would give a smaller amount but nothing worked lol.

You can do this, it is very simple if you think about it. Starting with 1: - 1 x 3 = 3 (Step 1) - 3 + 1 = 4 (Step 2) - 4 + 1 = 5 (Step 3) - 5 x 3 = 15 (Step 4) - 15 + 1 = 16 (Step 5) - 16 + 1 = 17 (Step 6) 6 Steps in total! don't make it too confusing but don't make it too easy for yourself.

This is really easy to figure out if you solve the problem backward. Start at 17 and try to reach 1 with the actions reversed (subtract 1, or divide by 3). Since the goal now is to reach 1 in the fewest # of actions, you should simply divide by 3 whenever you can, which is when your current number is divisible by 3, and subtract by 1 when it is not:

Start at 17 (not divisible by 3)

1. Subtract 1 = 16 (not divisible by 3)
2. Subtract 1 = 15 (divisible by 3)
3. Divide by 3 = 5 (not divisible by 3)
4. Subtract 1 = 4 (not divisible by 3)
5. Subtract 1 = 3 (divisible by 3)
6. Divide by 3 = 1

So the minimum # of actions is 6!

Think about the biggest number you can multiply by 3 and get under 17. Then figure out the fastest way to get to that number. 5X3=15 but 6X3=18 so you choose 5 and figure out that you can get to 3 in one step by 1X3 then add 2, multiply by 3, and add 2!

First :1+1=2, 2*3 =6

We can work backwards, reducing the total either by subtracting one (which we can always do) or by dividing by three (which we can do only if our current total is a multiple of three).

We must start off

$17 \rightarrow 16 \rightarrow 15$

now we have a choice. *.The obvious thing to do is to divide by three, and continue

$17 \rightarrow 16 \rightarrow 15 \rightarrow 5 \rightarrow 4 \rightarrow 3 \rightarrow 1$

Running this backwards exhibits a solution in $\boxed{\text{6 steps}}$ . (Obviously we reject the continuation $3 \rightarrow 2 \rightarrow 1$ as inferior to $3 \rightarrow 1$ )

To complete our solution we must show that this is the best possible chain of operations. It is just possible that if we had taken the other choice at * it would have switched us onto a better track. Let's check it out and see

$17 \rightarrow 16 \rightarrow 15 \rightarrow 14 \rightarrow 13 \rightarrow 12 \rightarrow 11 \text{ or } 4$

At this point we already have six steps, but we have not reached 1 yet, so we cannot find a better solution by this route.

I easily completed it by doing it in reverse order counting the steps:

• 17 – 1
• 16 – 1
• 15 ÷ 3
• 5 – 1
• 4 – 1
• 3 ÷ 3
• 1

Total steps: 6.

1 X 3 3+1 4+1 5 X 3 15 +1 16 + 1 = 17 Six steps